Алгоритм в 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 реализован с очень быстрым кодом сортировки по основанию, поэтому абсолютная производительность все равно будет достаточно хорошей, хотя и не такой эффективной, как специализированный метод выбора.