cuda中的流過濾器

Question

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

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

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

Answer 1

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

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

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

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

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

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