質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.77%

  • C++

    3256questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • STL

    13questions

    STL(Standard Template Library)は、ジェネティックコンテイナー、イテレーター、アルゴリズム、そして関数オブジェクトのC++ライブラリーです。

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

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 570

RyuSuzuki

score 113

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

前提・実現したいこと

タイトルの通り、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]);
  }

}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

+4

#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がソート済みで、かつ範囲内に入っていないと暴走しますが、コピーするよりちょこっとだけ速いと思います(キャッシュとかの関係で)。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/10/15 08:18

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

    キャンセル

checkベストアンサー

+2

ierase_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の処理です。やっつけて作ったので、細かいところはまだ最適化する余地はあるかと思います。

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/10/14 22:02 編集

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

    もう許してやれよ……

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.77%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 解決済

    Listを逆順にループしたい

    javaで、あるListの中身を格納されたのと逆順に繰り返し処理したいのですが、 なるべくシンプルなコードで書けたらと思っています。 こういった場合に便利なAPIはあるのでしょう

  • 解決済

    数列の検索について

    プログラミング初心者です。 036132567... のようなファイル(または配列)に対して検索をかけたいです。 036を検索したら0 361を検索したら1

  • 解決済

    要素数が同じ2つの配列を同じ添え字同士で掛け算したい

    要素数が同じ2つの配列を、同じ添え字同士で掛け算したいのですが、プログラムではどう書けばいいでしょうか? 求めるものは N[0]*M[0]+N[1]*M[1]+N[2]*M[2

  • 受付中

    vectorの値の参照

    前提・実現したいこと <int,int>型のvectorで値を参照したいのですがどうすればいいですか? 該当のソースコード ここにご自身が実行したソースコードを書いてくだ

  • 解決済

    ArrayList データの削除

    前提・実現したいこと ArrayListで一番最後に追加されたデータを削除したいです。 発生している問題・エラーメッセージ 該当のソースコード ここに言語を入力 p

  • 解決済

    JAVA 指定した配列のキーを削除することはできるのか? phpで言うところのunset()

    <?php /*削除ボタンを押すたびにサブ画像だけを削除したい。 流れとして、例えばユーザーが持つ画像をDBから4つ取得してそれは配列に詰めている。 ImageViewも配列に

  • 解決済

    【C++】【vectorクラス】高速なベクトル足し算

    C++のstd::vectorクラスにおいての足し算実装 初歩的なものですが、C++を用いてベクトル同士の足し算を実装中です。 今現在、以下のような単純なもの浮かばないのですが

  • 受付中

    C++の配列の関数定義と呼び出し方について

    C++のヘッダーで c.h class bun { void erase(vector<float> pp); vector<float> num; } があったとき、c.

同じタグがついた質問を見る

  • C++

    3256questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • STL

    13questions

    STL(Standard Template Library)は、ジェネティックコンテイナー、イテレーター、アルゴリズム、そして関数オブジェクトのC++ライブラリーです。