2011-10-21 114 views
1

我有一個值的數組和索引的鏈表。現在,我只想保留與LL中索引對應的數組中的那些值。有沒有一個標準的算法來做到這一點。請給出例子,如果可能的cuda中的流過濾器

因此,假設我有一個數組1,2,5,6,7,9 和我有一個鏈表2-> 3

所以,我想保留值在索引2和3.這就是保留5和6. 因此,我的函數應該返回5和6

+2

不清楚你想要做什麼 - 你應該在C中發佈一些正常的標量代碼,做你想做的事情,然後有可能告訴你如何在CUDA中實現它。 –

+0

鏈表中的條目是否保證以某種可預測的方式排序(如排序)? – talonmies

+0

@talonmies:是的,索引是排序的。 – Programmer

回答

1

一般來說,鏈表是固有的串行。使用並行機器不會加快遍歷列表的速度,因此問題的步數不能低於O(n),其中n是列表的大小。

但是,如果您有其他方法可以訪問列表,您可以使用它進行操作。例如,列表中的所有元素都可以存儲在一個固定大小的數組中(儘管不是以連續的方式需要)。列表成員可以使用下面的結構體表示在一個數組中。

struct ListNode { 
    bool isValid; 
    T data; 
    int next; 
} 

isValid套如果在一個陣列給定小區是由一個有效列表構件佔據,或它僅僅是一個空單元格。

現在,一個並行算法會一次讀取所有單元格,檢查它是否代表有效數據,如果是,請對其執行一些操作。

第二部分:每個線程的輸入數組A的有效索引idx必須標記爲A[idx]才能被刪除。一旦我們知道A的哪些元素應該被移除,哪些不是 - 可以應用並行壓縮算法。