Быстрая сортировка в GLSL?
Это
if n not in memo:
memo[n] = func(n)
return memo[n]
не то же самое, что
return func(n) if n not in memo else memo[n]
Однострочник не изменяет содержание заметки. Если вы хотите сравнить яблоки с яблоками, попробуйте:
if n not in memo:
return func(n)
return memo[n]
Для оптимизации вашего однострочного и сохранения значения словаря, вы должны изменить однострочное на:
return memo[n] if n in memo else memo.setdefault(n, func(n))
Помимо изучения того, как работает memize, вы должны изучить использование functools lru_cache memoize, которое «написано на C и будет намного быстрее, чем все, что вы можете воспроизвести в Python».
meowgoesthedog, chepner & amp; FHTMitchell.
3 ответа
Раскрытие информации: я действительно не знаю GLSL - я занимался программированием GPGPU с помощью AMD Stream SDK, у него другой язык программирования.
Из вашего комментария к ответу Бьорна я понимаю, что вы не не заинтересованы в использовании графического процессора для сортировки огромной базы данных - например, создания обратной телефонной книги или чего-то еще, но вместо этого у вас есть небольшой набор данных, и каждый фрагмент имеет свой собственный набор данных для сортировки. Больше похоже на попытку сделать срединную пиксельную фильтрацию?
Я могу сказать только в общем:
Для небольших наборов данных алгоритм сортировки действительно не имеет значения. В то время как люди тратили карьеру, думая о том, какой алгоритм сортировки является лучшим для очень больших баз данных, для малых N действительно не имеет значения, используете ли вы быструю сортировку, сортировку по коду, сортировку по радикалу, сортировку по оболочке, оптимизированную сортировку по пузырькам, Unoptimized Bubble sort и т. Д. По крайней мере, это не имеет большого значения для CPU.
GPU являются SIMD-устройствами, поэтому им нравится, когда каждое ядро выполняет одинаковые операции на этапе блокировки. Вычисления дешевы, но ветки дорогие, и ветки, зависящие от данных, где каждое ядро ветвится по-своему, очень, очень, очень, дороги.
Так что, если у каждого ядра есть свой небольшой набор данных для сортировки и количество данных для сортировки зависит от данных, и это может быть разное число для каждого ядра, лучше выбрать максимальный размер (если вы можете), заполнить массивы бесконечностью или большим числом и заставить каждое ядро выполнять одинаковую сортировку, это была бы неоптимизированная пузырьковая сортировка без ветвей, что-то вроде этого:
псевдокод (поскольку я не знаю GLSL), сортировка по 9 точкам
#define TwoSort(a,b) { tmp = min (a, b); b = a + b - tmp; a = tmp; }
for (size_t n = 8; n ; --n) {
for (size_t i = 0; i < n; ++i) {
TwoSort (A[i], A[i+1]);
}
}
Вы видели эту статью? https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter46.html
Я не был уверен, что Вы искали алгоритм Quicksort или быстрый алгоритм сортировки. Алгоритм в статье использует сортировку слиянием...
У меня нет никаких знаний о программировании на GPU.
Я бы использовал heapsort, а не quicksort, потому что вы сказали, что вам нужно взглянуть только на несколько верхних значений. Куча может быть построена за время O (n) , но получение максимального значения составляет log (n) . Поэтому, если количество необходимых вам значений значительно меньше, чем общее количество элементов, вы можете получить некоторую производительность.