gpu - 推力排序的步复杂度和唯一的推力

Question

我在推力中使用排序和唯一按键功能。我只是想知道推力中排序函数的步长复杂度是多少，以及唯一按键函数的工作和步长复杂度是多少。

根据我的知识，我认为排序的工作复杂度是 O(NlogN)。但我不知道 unique_by_key 操作是什么

Answer 1

Thrust 中有两种类型的排序。有基数排序和比较排序。对于基数排序，工作复杂度为 O(kN)，其中 N 是键的数量，k 是键的长度。如您所述，对于比较排序，工作复杂度为 O(N log N)。

unique_by_key是流压缩操作，这意味着工作复杂度为 O(N)。