概念线程问题

我在某些线程中生成从1到N的数字散列（MD5）。根据散列的第一个字母，生成它的数字被存储在一个数组中。例如，数字1的结果为c4ca4238a0b923820dcc509a6f75849b，数字2的结果为c81e728d9d4c2f636f067f89cc14862c，因此它们存储在以“c”开头的特定散列数组中。概念线程问题

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

我不能简单地验证数组上的最后一个数字，因为只要线程正在运行，它们可能会非常远离彼此。

有没有解决这个线程问题的方法？任何比在所有线程完成后排列数组都快的解决方案会很好。

我正在C中执行此操作。

谢谢！

来源

2012-10-02 Frederico Schardong

我不能按照你的要求。你有16个东西（不知道它们是整数还是什么）。你是否试图制作一个基于MD5哈希的哈希表？ – CrazyCasta

至此，我有16个数组，每个数组都有很多整数。数组中的每个整数点的散列将被存储，正如我在我的问题中所解释的。 –

@CrazyCasta，是的，基于MD5哈希的哈希表类型 –

代替具有用于每个前缀一个阵列的（例如，“C”。），具有每个线程一个阵列，用于每个前缀。每个线程只能插入到它自己的数组中，所以它总是以增加的顺序插入数字，并且单独的线程数组将保持排序。

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

来源

2012-10-02 05:39:40 caf

这是一个好主意！谢谢@caf –

@FredericoSchardong：更好的是，你可以预先分配输入数字在线程间散列（例如线程1哈希数字0-1023，线程2哈希数字1024-2047 ...），以便你可以只需将它们连接起来即可组合数组。 – caf

既然你提到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-02 05:00:41 CrazyCasta

概念线程问题

回答

相关问题