1

我正在某些线程中生成从 1 到 N 的数字的哈希值 (MD5)。根据散列的第一个字母，生成它的数字存储在一个数组中。例如，数字 1 生成 c4ca4238a0b923820dcc509a6f75849b，数字 2 生成 c81e728d9d4c2f636f067f89cc14862c，因此它们存储在以“c”开头的特定哈希数组中。

问题是我需要生成从低到高排序的它们。序列完成后对它们进行排序非常昂贵，N 可以大到 2^40。当我使用线程时，排序永远不会自然发生。例如，一个线程可以生成数字 12 的哈希 (c20ad4d76fe97759aa27a0c99bff6710) 并将其存储在 "c" 数组中，然后其他线程生成数字 8 的哈希 (c9f0f895fb98ab9159f51fd0297e236d) 并将其存储在数字 12 之后的 "c" 数组中。

我不能简单地验证数组上的最后一个数字，因为就线程运行而言，它们可能彼此相距很远。

这个线程问题有什么解决方案吗？任何比在所有线程完成后排序数组更快的解决方案都会很棒。

我在 C 中实现这个。

谢谢！

4

2 回答 2

2

不是为每个前缀（例如“c”）设置一个数组，而是为每个前缀在每个线程中设置一个数组。每个线程只插入自己的数组，所以它总是以递增的顺序插入数字，并且各个线程数组将保持排序。

然后，您可以O(N)在过程结束时快速 ( ) 合并数组，因为各个数组都将被排序。这也将加快创建过程，因为您不需要对数组进行任何锁定。

于 2012-10-02T05:39:40.770 回答
0

既然您提到了 pthreads，我将假设您正在使用 gcc（不一定是这种情况，但可能是这种情况）。您可以使用__sync_fetch_and_add来获取数组末尾的值，并在一次原子操作中将其加一。它会像下面这样：

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

您会遇到的唯一问题是您是否需要调整数组大小（不确定您是否事先知道数组大小）。为此，您将需要一个锁（最有效的是每个数组一个锁），您在重新分配数组时独占锁定，在插入时非独占锁定。特别是这可以通过以下函数来完成（假设程序员没有释放解锁的锁）：

// 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 回答