【vector】vector.erase()を高速化したい

Question

解決済みですが、まだまだこんなのあるよ！という方のコメントを随時募集してます！

###前提・実現したいこと
タイトルの通り、C++のSTLコンテナの一つvectorクラスの"vector.erase()"の高速化をしたいです。

前提条件として、以下のようなものがあります。
なにか良い案があれば教えてください。

• ランダムアクセスが必要
• データが連続して配置されている

(この二つによりvectorクラスを採用)

• 削除するインデックスは事前にわかっている
• vectorのサイズは100000～程度のサイズ
• vectorの中身の順番は不動

サンプルコード(今現在の実装)は以下に記載してあります。また追加してほしい情報等あれば記述してもらえれば追記します。

よろしくお願いします。

# (include文は省略)

int main(){
  int vector_size = 100000;

  # eraseを施すvector. 2で初期化しているのに特に意味はないです
  vector<unsigned char> target_vector(vector_size, 2);

  # erase_index_listに入っている要素のインデックス(target_vector[erase_index_list[i]])を削除する.
  # erase_index_listの要素は比較的ランダム
  vector<int> erase_index_list{2,5,7,9,32,44,...,90032};

  # 正しく削除するため、erase_index_listの後ろからtarget_vectorの要素を削除する
  for(int i = erase_index_list.size() ; i != 0 ; --i){
    target_vector.erase(target_vector.begin() + erase_index_list[i]);
  }

}

Answer 1

#include <vector>
#include <utility>

template <typename T, typename N>
void sliding_erace_vector(std::vector<T> &target, const std::vector<N> &indexes)
{
    if(indexes.empty()) return;

    auto skip = indexes.begin();
    auto dest = target.begin() + *skip;
    auto src = dest;

    for(auto i = *skip; skip != indexes.end(); i++, src++){
        if(i != *skip){
            *dest = std::move(*src);
            dest++;
        }
        else{
            skip++;
        }
    }
    for(; src != target.end(); src++, dest++){
        *dest = std::move(*src);
    }
    target.resize(target.size() - indexes.size());
}

私はこんな感じで、元の配列の内部でスライドさせていくことを考えました。削除する要素のindexがソート済みで、かつ範囲内に入っていないと暴走しますが、コピーするよりちょこっとだけ速いと思います(キャッシュとかの関係で)。

Comments

[raccy]

最初の部分をコピーして無い分だけ、こっちの方が早いですね。

Answer 2

iはerase_index_list.size() - 1から始めなきゃ行けないのではと思いましたが、それは置いといて、考えました。まずはベンチマークも含めたソースコードを張ります。

#include <algorithm>
#include <chrono>
#include <climits>
#include <functional>
#include <iostream>
#include <random>
#include <utility>
#include <vector>

using namespace std;

// https://qiita.com/hmito/items/9f4bdc8442b6f6b3c7bc sort & unique
vector<int> make_rand_array_unique(const size_t size, int rand_min,
				   int rand_max, mt19937 engine)
{
	if (rand_min > rand_max) swap(rand_min, rand_max);
	const size_t max_min_diff =
	    static_cast<size_t>(rand_max - rand_min + 1);
	if (max_min_diff < size) throw runtime_error("引数が異常です");

	vector<int> tmp;
	uniform_int_distribution<int> distribution(rand_min, rand_max);

	const size_t make_size = static_cast<size_t>(size * 1.2);

	while (tmp.size() < size) {
		while (tmp.size() < make_size)
			tmp.push_back(distribution(engine));
		sort(tmp.begin(), tmp.end());
		auto unique_end = unique(tmp.begin(), tmp.end());

		if (size < distance(tmp.begin(), unique_end)) {
			unique_end = next(tmp.begin(), size);
		}
		tmp.erase(unique_end, tmp.end());
	}

	shuffle(tmp.begin(), tmp.end(), engine);
	return tmp;
}

chrono::microseconds mesure_time(function<void(void)> func)
{
	auto start = chrono::system_clock::now();
	func();
	auto end = chrono::system_clock::now();
	auto dur = end - start;
	return chrono::duration_cast<chrono::microseconds>(dur);
}

void original_erace_vector(vector<unsigned char> &target_vector,
			   const vector<int> &erase_index_list)
{
	for (int i = erase_index_list.size() - 1; i >= 0; --i) {
		target_vector.erase(target_vector.begin() +
				    erase_index_list[i]);
	}
}

void making_erace_vector(vector<unsigned char> &target_vector,
			 const vector<int> &erase_index_list)
{
	// 新たなvector
	vector<unsigned char> new_vector;
	// あらかじめ領域を予約しておく。
	new_vector.reserve(target_vector.size() - erase_index_list.size());

	auto erase_index_p = erase_index_list.begin();
	int target_index = 0;
	while (target_index < target_vector.size()) {
		if (erase_index_p != erase_index_list.end() &&
		    target_index == *erase_index_p) {
			++target_index;
			++erase_index_p;
		} else {
			new_vector.push_back(target_vector[target_index]);
			++target_index;
		}
	}
	target_vector = move(new_vector);
}

int main()
{
	// int vector_size = 100;
	int vector_size = 100000;
	vector<unsigned char> target_vector(vector_size, 2);

	// 乱数で初期化
	random_device seed_gen;
	mt19937 engine(seed_gen());
	uniform_int_distribution<unsigned char> dist(0, UCHAR_MAX);
	for (auto &c : target_vector) {
		c = dist(engine);
	}

	auto target_vector1 = target_vector;
	auto target_vector2 = target_vector;

	// ランダムな削除リスト
	int erace_size = vector_size / 10; // 1/10の想定
	vector<int> erase_index_list =
	    make_rand_array_unique(erace_size, 0, vector_size - 1, engine);
	sort(erase_index_list.begin(), erase_index_list.end());

	// cout << "target_vector: ";
	// for (auto &c : target_vector) {
	// 	cout << static_cast<int>(c) << ',';
	// }
	// cout << " => size: " << target_vector.size() << endl;
	// cout << "erase_index_list: ";
	// for (auto &c : erase_index_list) {
	// 	cout << static_cast<int>(c) << ',';
	// }
	// cout << " => size: " << erase_index_list.size() << endl;

	auto msec1 = mesure_time(
	    [&]() { original_erace_vector(target_vector1, erase_index_list); });
	cout << "original: " << msec1.count() << " us" << endl;

	auto msec2 = mesure_time(
	    [&]() { making_erace_vector(target_vector2, erase_index_list); });
	cout << "making: " << msec2.count() << " us" << endl;

	// cout << "target_vector1: ";
	// for (auto &c : target_vector1) {
	// 	cout << static_cast<int>(c) << ',';
	// }
	// cout << " => size: " << target_vector1.size() << endl;
	// cout << "target_vector2: ";
	// for (auto &c : target_vector2) {
	// 	cout << static_cast<int>(c) << ',';
	// }
	// cout << " => size: " << target_vector2.size() << endl;
}

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)です。削除対象が多くても処理時間がほとんど変わりません。

ということで、

1. 新たなvectorの器を用意する。
2. 削除リストにある番号を除いて、新たなvectorに入れていく。
3. 新たなvectorの中身を元々のvectorに移動。

というのが、making_erace_vectorの処理です。やっつけて作ったので、細かいところはまだ最適化する余地はあるかと思います。

多分これが一番早いと思います

Comments

[RyuSA]

新しい器を作る、その発想はなかったです！ありがとうございます！????

もう許してやれよ……