0

比較的多数の要素 (~100k) を処理するプログラムを作成しているときに、std::listとQListの間に奇妙な違いがあることに気付きました。最初は、うまく機能するstd::vectorを使用しました。しかし、プログラムはベクトル内のランダムな位置に要素を挿入する必要があることが多いため、イテレータが目的の位置にあるときに、挿入に一定の時間がかかるstd::listに切り替えました。

問題は、std::list のパフォーマンスが、insert() メソッドと push_back() メソッドの両方で std::vector よりも悪いことです。私が得た100kの要素を持つリストに100の連続した要素を追加するために測定：

  • std::vector の場合は ~25ms (最初に追加する場合の最悪のケース)
  • std::list で 600ms(!) 以上 (push_back() または insert(list.begin() を使用しても、任意の位置))。

要素を挿入する時間には、イテレータで位置に到達する時間は含まれないことに注意してください。

リストの原因となるキャッシュミスによるリストのパフォーマンスの問題は知っていますが、これはキャッシュミスの限界をはるかに超えているようです。また、要素 (5 つの定数長の変数を持つ単純な構造体) を挿入する時間は、リストのサイズとともに増加します。リストのサイズを取得する操作でさえ、より多くの時間がかかります。これは、リストの両方の操作で保証されている時間の複雑さとは完全に対照的です:定数。

参照:こちら

好奇心から、std::listからQListおよび viola に変更されました。挿入時間は一定で、0 ミリ秒から 1 ミリ秒の間です。

挿入時間を測定するために使用されるコードを次に示します。

2 つの時点の間に他の操作は実行されません: 誤り: size() メソッドを使用しました

std::リスト:

    QTime time;
    time.start();

    for (int a = 1; a <= lineChange; a++)
    {
        listData.insert(listIterator, newElement); 
    }        
    int elapsed = time.restart();
    qDebug() << "elapsed: " << elapsed << "ms";

結果: 経過時間: 662ms

Qリスト:

    QTime time;
    time.start();

    for (int a = 1; a <= lineChange; a++)
    {
        QListData.insert(iteratorPos, newElement);
        position++;
    } 

    int elapsed = time.restart();
    qDebug() << "elapsed: " << elapsed << "ms";

結果: 経過: 1ms

std::ベクトル:

    QTime time;
    time.start();

    for (int a = 1; a <= lineChange; a++)
    {
        vectorData.insert(vectorIterator, newElement);

        /*update of the iterator when it was 
        invalidated due to resize of the vector*/
    }    

    int elapsed = time.restart();
    qDebug() << "elapsed: " << elapsed << "ms";

結果: 経過時間: 27ms

では、なぜ QList と std::list の間に大きな違いがあるのでしょうか? またはそれ以上: std::listの場合、パフォーマンスが非常に悲惨なのはなぜですか?

補足情報として：フラグをc++ 11に設定して、Linux（Mint）でgccでQtEditorを使用しています

編集：

データ型と宣言:

typedef struct TOKELEMENT {
    unsigned int column;
    unsigned int lenght;
    unsigned int tType;
    std::string value;
} tokElement;

// the three lists
std::vector<okElement> vectorData;
std::list<tokElement> listData;
QList<tokElement> QListData;

tokElement newElement;

unsigned int iteratorPos;
std::vector<std::vector<tokElement> >::iterator vectorIterator;
std::list<std::vector<tokElement> >::iterator listIterator;

//lineChange is an unsigned int, given as function parameter
unsigned int lineChange;
4

1 に答える 1

3

質問で言及したこととは対照的に（恥ずかしい）、リストでinsert（）またはpush_back（）を使用するかどうかを判断するために、forループのstd :: listのサイズをもう一度チェックしました。この関数の時間の複雑さは O(1) ではなく O(n) であるため、挿入全体が大幅に遅くなりました。これを指摘してくれたLeeorに感謝します。

このチェックをfor ループから移動した後、std::list は期待どおりに実行され、QList よりもさらに高速になりました。

于 2014-03-16T03:44:11.513 に答える