1
我有一個值的數組和索引的鏈表。現在,我只想保留與LL中索引對應的數組中的那些值。有沒有一個標準的算法來做到這一點。請給出例子,如果可能的cuda中的流過濾器
因此,假設我有一個數組1,2,5,6,7,9 和我有一個鏈表2-> 3
所以,我想保留值在索引2和3.這就是保留5和6. 因此,我的函數應該返回5和6
我有一個值的數組和索引的鏈表。現在,我只想保留與LL中索引對應的數組中的那些值。有沒有一個標準的算法來做到這一點。請給出例子,如果可能的cuda中的流過濾器
因此,假設我有一個數組1,2,5,6,7,9 和我有一個鏈表2-> 3
所以,我想保留值在索引2和3.這就是保留5和6. 因此,我的函數應該返回5和6
一般來說,鏈表是固有的串行。使用並行機器不會加快遍歷列表的速度,因此問題的步數不能低於O(n),其中n是列表的大小。
但是,如果您有其他方法可以訪問列表,您可以使用它進行操作。例如,列表中的所有元素都可以存儲在一個固定大小的數組中(儘管不是以連續的方式需要)。列表成員可以使用下面的結構體表示在一個數組中。
struct ListNode {
bool isValid;
T data;
int next;
}
值isValid
套如果在一個陣列給定小區是由一個有效列表構件佔據,或它僅僅是一個空單元格。
現在,一個並行算法會一次讀取所有單元格,檢查它是否代表有效數據,如果是,請對其執行一些操作。
第二部分:每個線程的輸入數組A
的有效索引idx
必須標記爲A[idx]
才能被刪除。一旦我們知道A
的哪些元素應該被移除,哪些不是 - 可以應用並行壓縮算法。
不清楚你想要做什麼 - 你應該在C中發佈一些正常的標量代碼,做你想做的事情,然後有可能告訴你如何在CUDA中實現它。 –
鏈表中的條目是否保證以某種可預測的方式排序(如排序)? – talonmies
@talonmies:是的,索引是排序的。 – Programmer