Я ищу реализацию алгоритма k-го наименьшего элемента в thrust/cudapp. Я Googled для этого, но, похоже, не нашел его. Кто-нибудь знает, существует ли такой алгоритм?Алгоритм в thrust/cudpp для поиска k-го наименьшего элемента
Я видел, что существует переупорядочение, но оно не говорит kth наименьшее.
В настоящее время Thrust не предоставляет алгоритм выбора (т. Е. std::nth_element в STL), хотя он находится на нашем радаре, и есть good evidence, что выбор можно сделать быстро на графическом процессоре. Ваш единственный ресурс прямо сейчас состоит в сортировке данных с thrust::sort или thrust::sort_by_key (или их вариантах stable_), а затем выберите соответствующий элемент (ы). Сортировка примитивных типов (например, int, float, , double) в Thrust реализована с очень быстрым кодом сортировки радикса, поэтому абсолютная производительность будет по-прежнему неплохой, хотя и не такой эффективный, как specialized selection method.
@MrFooz, sheesh, Quickselect - это O (N) в среднем. – ArchaeaSoftware
См. [Этот ответ] (http://stackoverflow.com/questions/8660978/how-long-does-thrust-take-to-sort-1-million-floats) к вашему другому вопросу. – harrism