概念線程問題

我在某些線程中生成從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

概念線程問題

回答

相關問題