Help us understand the problem. What is going on with this article?

C++でのvector.erase()は遅い

More than 3 years have passed since last update.

openFrameworksでアプリ作ってて、とある処理部分に17秒かかっててなんとか高速化できないかずっと
悩んでた。
具体的には3Dオブジェクトの全頂点をfor文回して調べてごにょごにょーってしてる箇所で、
再帰関数である事、for分ないでif分も多様しててopenCLやGPGPUなどのテクニックも使えそうになくって
どうしようかと思ってたらふとvector.erase()は遅いんではないか?と調べてみた。

ネット上の記事によるとやっぱりそうらしくって、
「最後の要素と交換してから消せば遅くならない」という記事を発見!
早速試してみた所、手持ちのプロジェクト内で再帰関数内で計23418回vector.erase()が
実行されて処理に17sec掛かっていた箇所がなんと9.3secに軽減された!
ありゃ、びっくり、、
こんな最適化方法があったんですね、、
これからはもうvector.erase()は使いません

※配列の一番最後にあるべき値が途中に移動してシャッフルされてしまうわけなので、配列内の要素の順番が
重要なプログラムの時にに使うときは注意ですね!

    //Test1
    {
        vector<ofVec3f> list;
        list.resize(40000);

        float startTime = ofGetElapsedTimef();

        int l = list.size();
        for(int i = 0; i < l; i++) {
            if(i % 2 == 0) {
                //途中の要素を消すと遅い事がある
                list.erase(list.begin() + i);

                l--;
            }
        }

        cout << "erase    = " << ofGetElapsedTimef() - startTime << endl;
    }

    //Test2
    {
        vector<ofVec3f> list;
        list.resize(40000);

        float startTime = ofGetElapsedTimef();

        int l = list.size();
        for(int i = 0; i < l; i++) {
            if(i % 2 == 0) {
                //最後の要素と交換してから消せば遅くならない
                list[i] = list.back(); //std::swap(list[100], list.back())だとコピー1回多い
                list.pop_back();

                l--;
            }
        }

        cout << "pop_back = " << ofGetElapsedTimef() - startTime << endl;
    }

    //出力結果
    //erase    = 0.119303
    //pop_back = 0.00086391

[参考URL]
[C++]ゲームのオブジェクト管理システムが遅い場合
http://qiita.com/mrdagon/items/009dfad2413faee2a827

「追記 11/17 21:38]
Twitterでこんなご指摘を受けました。

「状況に応じてvector以外の最適化コンテナを使った方がよいのでは?」といったご指摘


「まとめて削除する様に実装を見直してみては?」といったご指摘


selflash
labs.1-10.com/blog/author/yokoda
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away