8

次の問題に対するよく知られた解決策はありますか？

  • あなたはたくさんの文字列のベクトルを持っています

  • あなたはそれを数十万の文字列で喜んで埋めます、そしてそれは速いです

  • 文字列は任意の方法で操作します。人生は素晴らしい。

  • ベクトルはこれで完了です。ベクトルが範囲外になり、各文字列が1つずつ破壊される間、コーヒーを飲みに座って腰を下ろす必要があります。

編集：問題は解決しました！

同じコンピューターのLinuxで以下のコードを実行したところ、問題はなかったので、解決策を見つけました。それは私のシステムにあることが判明しました-ずっと前に私が自分自身に引き起こしたものですが、私はそれを忘れていました。
問題を修正すると、時間は劇的に減少し、GCCよりもさらに良くなりました！

良いパズルですが、答えを投稿する代わりに、別のことをします。
現在、この質問に賞金をかけることは許可されていませんが、原因がわかっていると思われる場合は、試してみてください。それが正しければ、私はそれを受け入れて、あなたに素晴らしい報奨金を与えます。（私があなたに賞金を与えるのを忘れたら私に思い出させてください！）
誰も知らないなら、私はしばらくしてからそれを自分で投稿します。

サンプルコード：

以前は誰よりも懐疑的でしたが、今ではSTLが遅いという点もあると思います。
これは私のラップトップでは3.95秒かかりました:(シャッフルは重要です）

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <string>
#include <vector>

int main()
{
    using namespace std;
    srand((unsigned)time(NULL));
    clock_t start;
    {
        vector<string> v(400000);
        for (size_t i = 0; i < v.size(); i++)
        {
            v[i].resize(16 + rand() % 32);  // some variation
        }

        // shuffle
        for (size_t i = 0; i < (size_t)pow((double)v.size(), 1.15); i++)
        {
            size_t j = rand() * (RAND_MAX + 1) + rand();
            swap(v[i % v.size()], v[j % v.size()]);
        }
        
        printf("Going out of scope...\n"); fflush(stdout);
        start = clock();
    }
    clock_t end = clock();
    printf("%u ms\n", (end - start) * 1000 / CLOCKS_PER_SEC);
    return 0;
}

このプログラムは、Visual C ++またはWindowsのいずれかで、内部的にO（n 2 ）アルゴリズムを使用しているように見えます。何が起こっているのかわかりませんが、興味深いです...

4

3 に答える 3

8

一括割り当て解除でカスタムアロケータを使用します。

于 2012-07-18T01:08:47.343 に答える
5

さて、誰もそれを理解していなかったので...

これは、私のシステムでヒープテールチェックがオンになっているためです。削除すると、コードはすぐに終了しました。

于 2012-07-27T07:05:09.363 に答える
0

ベクトル自体を動的に作成して、参照カウントスマートポインターで管理できるようにしてみませんか。次に、最後に参照したスレッドがUIスレッドではないことを確認できるため、スコープ外になったときにUIスレッドが処理を実行するスレッドではありません。

処理を行うスレッドの優先度を操作して、優先度を下げ、残りのスレッドに悪影響を与えないようにすることもできます。これにより、UIスレッドが優先度の低いスレッドの前にスケジュールされるようになります。

注：私はそれを試したことがありませんが、なぜそれが機能しないのかわかりません-しかし、あなた自身の責任でそれに時間を費やしてください！:)

于 2012-07-18T01:40:20.870 に答える