解決済みですが、まだまだこんなのあるよ!という方のコメントを随時募集してます!
###前提・実現したいこと
タイトルの通り、C++のSTLコンテナの一つvectorクラスの"vector.erase()"の高速化をしたいです。
前提条件として、以下のようなものがあります。
なにか良い案があれば教えてください。
- ランダムアクセスが必要
- データが連続して配置されている
(この二つによりvectorクラスを採用)
- 削除するインデックスは事前にわかっている
- vectorのサイズは100000~程度のサイズ
- vectorの中身の順番は不動
サンプルコード(今現在の実装)は以下に記載してあります。また追加してほしい情報等あれば記述してもらえれば追記します。
よろしくお願いします。
cpp
1# (include文は省略) 2 3int main(){ 4 int vector_size = 100000; 5 6 # eraseを施すvector. 2で初期化しているのに特に意味はないです 7 vector<unsigned char> target_vector(vector_size, 2); 8 9 # erase_index_listに入っている要素のインデックス(target_vector[erase_index_list[i]])を削除する. 10 # erase_index_listの要素は比較的ランダム 11 vector<int> erase_index_list{2,5,7,9,32,44,...,90032}; 12 13 # 正しく削除するため、erase_index_listの後ろからtarget_vectorの要素を削除する 14 for(int i = erase_index_list.size() ; i != 0 ; --i){ 15 target_vector.erase(target_vector.begin() + erase_index_list[i]); 16 } 17 18} 19
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答2件
0
C++
1#include <vector> 2#include <utility> 3 4template <typename T, typename N> 5void sliding_erace_vector(std::vector<T> &target, const std::vector<N> &indexes) 6{ 7 if(indexes.empty()) return; 8 9 auto skip = indexes.begin(); 10 auto dest = target.begin() + *skip; 11 auto src = dest; 12 13 for(auto i = *skip; skip != indexes.end(); i++, src++){ 14 if(i != *skip){ 15 *dest = std::move(*src); 16 dest++; 17 } 18 else{ 19 skip++; 20 } 21 } 22 for(; src != target.end(); src++, dest++){ 23 *dest = std::move(*src); 24 } 25 target.resize(target.size() - indexes.size()); 26}
私はこんな感じで、元の配列の内部でスライドさせていくことを考えました。削除する要素のindexがソート済みで、かつ範囲内に入っていないと暴走しますが、コピーするよりちょこっとだけ速いと思います(キャッシュとかの関係で)。
投稿2017/10/14 15:04
編集2017/10/15 06:02総合スコア1720
0
ベストアンサー
i
はerase_index_list.size() - 1
から始めなきゃ行けないのではと思いましたが、それは置いといて、考えました。まずはベンチマークも含めたソースコードを張ります。
C++
1#include <algorithm> 2#include <chrono> 3#include <climits> 4#include <functional> 5#include <iostream> 6#include <random> 7#include <utility> 8#include <vector> 9 10using namespace std; 11 12// https://qiita.com/hmito/items/9f4bdc8442b6f6b3c7bc sort & unique 13vector<int> make_rand_array_unique(const size_t size, int rand_min, 14 int rand_max, mt19937 engine) 15{ 16 if (rand_min > rand_max) swap(rand_min, rand_max); 17 const size_t max_min_diff = 18 static_cast<size_t>(rand_max - rand_min + 1); 19 if (max_min_diff < size) throw runtime_error("引数が異常です"); 20 21 vector<int> tmp; 22 uniform_int_distribution<int> distribution(rand_min, rand_max); 23 24 const size_t make_size = static_cast<size_t>(size * 1.2); 25 26 while (tmp.size() < size) { 27 while (tmp.size() < make_size) 28 tmp.push_back(distribution(engine)); 29 sort(tmp.begin(), tmp.end()); 30 auto unique_end = unique(tmp.begin(), tmp.end()); 31 32 if (size < distance(tmp.begin(), unique_end)) { 33 unique_end = next(tmp.begin(), size); 34 } 35 tmp.erase(unique_end, tmp.end()); 36 } 37 38 shuffle(tmp.begin(), tmp.end(), engine); 39 return tmp; 40} 41 42chrono::microseconds mesure_time(function<void(void)> func) 43{ 44 auto start = chrono::system_clock::now(); 45 func(); 46 auto end = chrono::system_clock::now(); 47 auto dur = end - start; 48 return chrono::duration_cast<chrono::microseconds>(dur); 49} 50 51void original_erace_vector(vector<unsigned char> &target_vector, 52 const vector<int> &erase_index_list) 53{ 54 for (int i = erase_index_list.size() - 1; i >= 0; --i) { 55 target_vector.erase(target_vector.begin() + 56 erase_index_list[i]); 57 } 58} 59 60void making_erace_vector(vector<unsigned char> &target_vector, 61 const vector<int> &erase_index_list) 62{ 63 // 新たなvector 64 vector<unsigned char> new_vector; 65 // あらかじめ領域を予約しておく。 66 new_vector.reserve(target_vector.size() - erase_index_list.size()); 67 68 auto erase_index_p = erase_index_list.begin(); 69 int target_index = 0; 70 while (target_index < target_vector.size()) { 71 if (erase_index_p != erase_index_list.end() && 72 target_index == *erase_index_p) { 73 ++target_index; 74 ++erase_index_p; 75 } else { 76 new_vector.push_back(target_vector[target_index]); 77 ++target_index; 78 } 79 } 80 target_vector = move(new_vector); 81} 82 83int main() 84{ 85 // int vector_size = 100; 86 int vector_size = 100000; 87 vector<unsigned char> target_vector(vector_size, 2); 88 89 // 乱数で初期化 90 random_device seed_gen; 91 mt19937 engine(seed_gen()); 92 uniform_int_distribution<unsigned char> dist(0, UCHAR_MAX); 93 for (auto &c : target_vector) { 94 c = dist(engine); 95 } 96 97 auto target_vector1 = target_vector; 98 auto target_vector2 = target_vector; 99 100 // ランダムな削除リスト 101 int erace_size = vector_size / 10; // 1/10の想定 102 vector<int> erase_index_list = 103 make_rand_array_unique(erace_size, 0, vector_size - 1, engine); 104 sort(erase_index_list.begin(), erase_index_list.end()); 105 106 // cout << "target_vector: "; 107 // for (auto &c : target_vector) { 108 // cout << static_cast<int>(c) << ','; 109 // } 110 // cout << " => size: " << target_vector.size() << endl; 111 // cout << "erase_index_list: "; 112 // for (auto &c : erase_index_list) { 113 // cout << static_cast<int>(c) << ','; 114 // } 115 // cout << " => size: " << erase_index_list.size() << endl; 116 117 auto msec1 = mesure_time( 118 [&]() { original_erace_vector(target_vector1, erase_index_list); }); 119 cout << "original: " << msec1.count() << " us" << endl; 120 121 auto msec2 = mesure_time( 122 [&]() { making_erace_vector(target_vector2, erase_index_list); }); 123 cout << "making: " << msec2.count() << " us" << endl; 124 125 // cout << "target_vector1: "; 126 // for (auto &c : target_vector1) { 127 // cout << static_cast<int>(c) << ','; 128 // } 129 // cout << " => size: " << target_vector1.size() << endl; 130 // cout << "target_vector2: "; 131 // for (auto &c : target_vector2) { 132 // cout << static_cast<int>(c) << ','; 133 // } 134 // cout << " => size: " << target_vector2.size() << endl; 135}
original_erace_vector
が質問オリジナル、making_erace_vector
が今から説明するバージョンです。コメントはデバッグ用ですので動作確認したいときは外してください(ただ、サイズが大きいままだと辛いかも知れませんが)。手元のGCCで最適化-O2でコンパイルした場合の結果は下記の通りです。
original: 9586 us making: 298 us
**ただし、初期サイズや削除するリストのサイズによっては簡単に逆転します。実際に削除する割合に応じて調べてください。**以下、making_erace_vector
の解説です。
削除する対象が複数ある場合、一つずつ削除するよりも、削除部分を除外した新たなvectorを作成した方が高速になる場合があります。
vectorのeraseは、削除場所から後ろ全ての要素をムーブするため、平均O(n)になります。それを何度も繰り返すので単に一個ずつ削除した場合、ほぼO(nm)になります(実際はもっと複雑なのですが、ちょっと難しすぎてわからない)。削除対象がそこそこ多いとかなりの処理時間がかかってしまいます。
逆に、配列を作り直す場合は、削除する数に関わらず、ほぼO(n)です。削除対象が多くても処理時間がほとんど変わりません。
ということで、
- 新たなvectorの器を用意する。
- 削除リストにある番号を除いて、新たなvectorに入れていく。
- 新たなvectorの中身を元々のvectorに移動。
というのが、making_erace_vector
の処理です。やっつけて作ったので、細かいところはまだ最適化する余地はあるかと思います。
多分これが一番早いと思います
投稿2017/10/14 12:50
編集2017/10/14 13:13総合スコア21735
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2017/10/14 23:18