I am looking for an implemention of kth smallest element algorithm in thrust/cudapp. I Googled for it but dont seem to find it. Does any one know if there exists such an algorithm?
I saw that there is reordering but it does not say kth smallest.
Asked
Active
Viewed 1,213 times
0
-
1@MrFooz, sheesh, Quickselect is O(N) on average. – ArchaeaSoftware Dec 29 '11 at 02:22
-
See [this answer](http://stackoverflow.com/questions/8660978/how-long-does-thrust-take-to-sort-1-million-floats) to your other question. – harrism Jan 05 '12 at 06:37
1 Answers
1
Thrust does not currently provide the selection algorithm (i.e. std::nth_element in the STL) though it's on our radar and there's good evidence that selection can be done quickly on the GPU. Your only recourse right now is to sort the data with thrust::sort or thrust::sort_by_key (or their stable_ variants) and then pick the appropriate element(s). Sorting primitive types (e.g. int, float, char, double) in Thrust is implemented with a very fast radix sort code, so the absolute performance will still be quite good, albeit not as efficient as a specialized selection method.
wnbell
- 1,240
- 7
- 7