Алгоритм в thrust / cudpp для поиска k-го наименьшего элемента

Question

Я ищу реализацию алгоритма k-го наименьшего элемента в thrust / cudapp.Я гуглил за это, но, похоже, не нашел его.Кто-нибудь знает, существует ли такой алгоритм?

Я видел, что есть переупорядочение, но оно не говорит kth наименьшее.

Answer 1

Тяга в настоящее время не обеспечивает алгоритм выбора (т. Е. std::nth_element в STL), хотя он находится на нашем радаре и есть убедительные доказательства , что выбор может быть сделан быстро на GPU. Ваш единственный выход прямо сейчас - отсортировать данные по thrust::sort или thrust::sort_by_key (или их stable_ вариантам), а затем выбрать соответствующий элемент (ы). Сортировка примитивных типов (например, int, float, char, double) в Thrust реализована с очень быстрым кодом сортировки по основанию, поэтому абсолютная производительность все равно будет достаточно хорошей, хотя и не такой эффективной, как специализированный метод выбора .