嘗める

Listに含まれる全てのitemについて、同じ処理を行いたい、と言うときに、どのようなやり方があるか、と言う話。

ここでは、QStringListをサンプルに、中身を全てトリムすると言う処理を考えてみる。(以下のソースに出てくるm_listはQStringListです)

サンプルソース

Qtのforeachキーワード

単なるdefineらしいですが。

foreach (const QString &data, m_list) {
    (void) data.trimmed();
}

嘗める、と言う意味では使えるのですが、今回のように内容を書き換えたいときには利用できません。

Qtのiterator

for (QStringList::iterator it = m_list.begin(); it != m_list.end(); it++) {
    *it = it->trimmed();
}

STLのiterator準拠です。const_iteratorもありますが、今回のように変更したい場合はiteratorを使います。

Qtのjava-style iterator

for (QMutableStringListIterator it(m_list); it.hasNext();) {
    QString &data = it.next();
    data = data.trimmed();
}

QListのindex access

for (int i = 0; i < m_list.size(); i++) {
    QString &data = m_list[i];
    data = data.trimmed();
}

QtConcurrentのblockingMap()

QtConcurrent::blockingMap(m_list, [](QString &data) {
    data = data.trimmed();
});

QtConcurrentとc++11のlambdaを使っているので、*.proに以下が必要です。

QT += concurrent
CONFIG += c++11

STLのalgorithmのfor_each

std::for_each(m_list.begin(), m_list.end(), [](QString &data) {
    data = data.trimmed();
});

c++11の拡張for

for (QString &data : m_list) {
    data = data.trimmed();
}

実行時間

試しに、OS X上のQt 5.4.0で実行時間を測ってみました。
10回実行して、平均ではなく最頻値を取っています。リストのサイズは10万件です。

やり方	実行時間(ms)
foreach	14
iterator	18
java iterator	18
index access	17
blockingMap	36
for_each	15
for	15

ビルド時の-Oオプションをつけたりしてみましたが、OS Xではほとんど変わりませんでした。(ただし、ここには結果を乗せていませんが、件数を100万件にすると少し差がでました)
foreachは、今回の要件(リスト内の文字列を全てtrimする)を満たさないので、今回は使えませんが、サンプルとして載せています。リストの要素の書き換えがない分早いと思われます。

QtConcurrentについて

実行時間を見ると、QtConcurrentのblockingMapだけ他から群を抜いて遅いことがわかります。
QtConcurrentのmap/blockingMapは、名前がmapなのでrubyのArrayのmapと同じように考えてしまうかも知れませんが、Concurrentが示す通り並列実行してくれます。
今回のように、MapFunctionの実行時間が小さいときは、並列実行のメリットよりもオーバーヘッドの方が大きくなってしまい、効果が得られませんが、MapFunctionの実行時間が大きいときには、並列実行の効果が得られます。
後述するgithubのソースをチェックアウトして、mylist.cppでEMULATE_TIME_CONSUMINGをdefineすると、その様子を見ることができます。

QtConcurrentが使える条件を以下に示します。

• 要素毎の処理の順序に意味がない
• 要素毎の処理を並列実行しても問題がない
• 要素毎の処理に一定以上の時間がかかる

結論

今回の実行時間の計測結果だけを見て、「STLのfor_eachかC++11のforを使おう」などと判断してはいけません。
環境やコンパイラ、ライブラリの実装によって、簡単に結果が変わってくるからです。
初期の実装時には、下手な最適化よりも、コードのわかりやすさを基準にアルゴリズムを選択すべきです。

今回のサンプルソースも、githubに上げてあります。
https://github.com/false-git/iteratortest