1

一部のスレッドで1からNまでの数のハッシュ（MD5）を生成しています。ハッシュの最初の文字によると、ハッシュを生成する番号は配列に格納されます。たとえば、番号1はc4ca4238a0b923820dcc509a6f75849bになり、番号2はc81e728d9d4c2f636f067f89cc14862cになるため、「c」で始まる特定のハッシュ配列に格納されます。

問題は、それらを低いものから高いものへとソートして生成する必要があるということです。シーケンスが終了した後にそれらをソートするのは非常に費用がかかります。Nは2^40にもなる可能性があります。私はスレッドを使用しているので、ソートが自然に行われることはありません。たとえば、1つのスレッドは番号12（c20ad4d76fe97759aa27a0c99bff6710）のハッシュを生成して「c」配列に格納し、他のスレッドは番号8（c9f0f895fb98ab9159f51fd0297e236d）のハッシュを生成して番号12の後に「c」配列に格納できます。

スレッドが実行されている限り、スレッドは互いに非常に離れている可能性があるため、配列の最後の番号を簡単に確認することはできません。

このスレッドの問題の解決策はありますか？すべてのスレッドが終了した後にアレイを注文するよりも高速なソリューションは素晴らしいでしょう。

私はこれをCで実装しています。

ありがとうございました！

4

2 に答える 2

2

プレフィックスごとに1つの配列（「c」など）を使用する代わりに、プレフィックスごとにスレッドごとに1つの配列を使用します。各スレッドは独自の配列にのみ挿入されるため、常に番号が昇順で挿入され、個々のスレッド配列は並べ替えられたままになります。

O(N)個々の配列はすべてソートされるため、プロセスの最後に配列をすばやく（）合体させることができます。これにより、アレイの周囲をロックする必要がなくなるため、作成プロセスも高速化されます。

于 2012-10-02T05:39:40.770 に答える
0

pthreadについて言及したので、gccを使用していると仮定します（これは必ずしも当てはまりませんが、おそらく当てはまります）。を使用し__sync_fetch_and_addて、配列の最後の値を取得し、1回のアトミック操作で値を追加できます。次のようになります。

insertAt = __sync_fetch_and_add(&size[hash], 1);
arrayOfInts[insertAt] = val;

遭遇する唯一の問題は、配列のサイズを変更する必要があるかどうかです（配列のサイズを事前に知っているかどうかはわかりません）。そのためには、アレイの再割り当て中に排他的にロックし、挿入時に非排他的にロックするロック（最も効率的にはアレイごとに1つのロック）が必要になります。特に、これは次の関数で実行できます（プログラマーがロック解除されたロックを解放しないことを前提としています）。

// Flag 2 indicates exclusive lock
void lockExclusive(int* lock)
{
    while(!__sync_bool_compare_and_swap(lock, 0, 2));
}

void releaseExclusive(int* lock)
{
    *lock = 0;
}

// Flag 8 indicates locking
// Flag 1 indicates non-exclusive lock
void lockNonExclusive(int* lock, int* nonExclusiveCount)
{
    while((__sync_fetch_and_or(lock, 9) & 6) != 0);
    __sync_add_and_fetch(nonExclusiveCount, 1);
    __sync_and_and_fetch(lock, ~8);
}

// Flag 4 indicates unlocking
void releaseNonExclusive(int* lock, int* nonExclusiveCount)
{
    while((__sync_fetch_and_or(lock, 4) & 8) != 0);
    if(__sync_sub_and_fetch(nonExclusiveCount) == 0);
        __sync_and_and_fetch(lock, ~1);
    __sync_and_and_fetch(lock, 4);
}
于 2012-10-02T05:00:41.853 に答える