当前位置：文江博客话题详情

cuda中的流过滤器

发布于 2024-12-11 13:12:27 字数 178 浏览 0 评论 0原文

我有一个值数组和一个索引链接列表。现在，我只想保留数组中与 LL 中的索引相对应的值。有一个标准算法可以做到这一点吗？如果可能的话请举例

所以，假设我有一个数组 1,2,5,6,7,9 我有一个链表 2->3

所以，我想保留索引 2 和 3 处的值。即保留 5 和 6。因此我的函数应该返回 5 和 6

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

君勿笑 2024-12-18 13:12:27

一般来说，链表本质上是串行的。拥有并行机器不会加快列表的遍历速度，因此问题的步骤数不能低于 O(n)，其中 n 是列表的大小。

但是，如果您有其他方法来访问该列表，您可以用它做一些事情。
例如，列表的所有元素都可以存储在固定大小的数组中（尽管不一定以连续的方式存储）。列表成员可以使用以下结构在数组中表示。

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

值 isValid 设置数组中的给定单元格是否被有效列表成员占用，或者它只是一个空单元格。

现在，并行算法将立即读取所有单元格，检查它是否代表有效数据，如果是，则对其执行某些操作。

第二部分：每个线程，如果输入数组 A 具有有效索引 idx，则必须标记 A[idx] 不被删除。一旦我们知道 A 的哪些元素应该被删除，哪些不应该被删除，就可以应用并行压缩算法。

In general, linked list is inherently serial. Having a parallel machine will not speed up the traversal of your list, hence the number of steps of your problem cannot go below O(n), where n is the size of the list.

However, if you have some additional way to access the list you can do something with it.
For example, all elements of the list could be stored in a fixed-size array (although, not necesairly in a consecutive way). List member could be represented in an array using the following struct.

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

The value isValid sets if given cell in an array is occupied by a valid list member, or it is just an empty cell.

Now, a parallel algorithm would read all cells at once, check if it represents a valid data, and if so, do something with it.

Second part: Each thread, having a valid index idx of your input array A would have to mark A[idx] not to be deleted. Once we know which elements of A should be removed and which not - a parallel compaction algorithm can be applied.

回复收藏 0 原文

~没有更多了~