Pushing Radix Sort (и python) до его пределов

Question

Я был очень расстроен тем, что многие из реализаций python radix сортировались там в Интернете.

Они последовательно используют радиус 10 и получают цифры номеров, которые они перебирают, делясь на мощность 10 или принимая log10 номера. Это невероятно неэффективно, поскольку log10 не является особенно быстрой операцией по сравнению с сдвигом бит, что почти в 100 раз быстрее!

В гораздо более эффективной реализации используется радиус 256 и сортируется побайтовый байт. Это позволяет выполнить все «байтовую обработку» с использованием смехотворно быстрых операторов бит. К сожалению, кажется, что абсолютно никто там не реализовал сортировку radix в python, которая использует битовые операторы вместо логарифмов.

Итак, я взял дело в свои руки и придумал этот зверь, который проходит около половины скорости сортируется на небольших массивов и работает почти так же быстро, на более крупных (например, len вокруг 10000000):

import itertools 

def radix_sort(unsorted): 
    "Fast implementation of radix sort for any size num." 
    maximum, minimum = max(unsorted), min(unsorted) 

    max_bits = maximum.bit_length() 
    highest_byte = max_bits // 8 if max_bits % 8 == 0 else (max_bits // 8) + 1 

    min_bits = minimum.bit_length() 
    lowest_byte = min_bits // 8 if min_bits % 8 == 0 else (min_bits // 8) + 1 

    sorted_list = unsorted 
    for offset in xrange(lowest_byte, highest_byte): 
     sorted_list = radix_sort_offset(sorted_list, offset) 

    return sorted_list 

def radix_sort_offset(unsorted, offset): 
    "Helper function for radix sort, sorts each offset." 
    byte_check = (0xFF << offset*8) 

    buckets = [[] for _ in xrange(256)] 

    for num in unsorted: 
     byte_at_offset = (num & byte_check) >> offset*8 
     buckets[byte_at_offset].append(num) 

    return list(itertools.chain.from_iterable(buckets)) 

Эта версия сортировки radix работает путем определения того, какие байты она должна сортировать (если вы передадите ей только целые числа ниже 256, она будет сортировать только один байт и т. Д.), А затем сортировать каждый байт из LSB, сбросив их в ковши для того, чтобы просто соединить ведра вместе. Повторите это для каждого байта, который нужно отсортировать, и у вас есть хороший отсортированный массив в O (n) времени.

Однако это не так быстро, как могло бы быть, и я хотел бы сделать это быстрее, прежде чем писать об этом как о лучшем радисе, чем все остальные радики.

Запуск cProfile на это говорит мне, что много времени тратится на методе append для списков, что заставляет меня думать, что этот блок:

for num in unsorted: 
     byte_at_offset = (num & byte_check) >> offset*8 
     buckets[byte_at_offset].append(num) 

в radix_sort_offset ест много времени. Это также блок, который, если вы действительно смотрите на него, выполняет 90% работы для всего вида. Этот код выглядит так, как будто это может быть numpy -ized, что, я думаю, приведет к значительному повышению производительности. К сожалению, я не очень хорош с более сложными функциями numpy, поэтому не смог понять это. Помощь будет очень оценена.

В настоящее время я использую itertools.chain.from_iterable, чтобы сгладить buckets, но если у кого есть более быстрое предложение, я уверен, что это тоже поможет.

Первоначально у меня была функция get_byte, которая вернула n-й байт числа, но вставка кода дала мне огромное ускорение скорости, поэтому я сделал это.

Любые другие комментарии к реализации или способы выжать больше производительности также приветствуются. Я хочу услышать что угодно и все, что у тебя есть.

Answer 1

Вы уже поняли, что

for num in unsorted: 
    byte_at_offset = (num & byte_check) >> offset*8 
    buckets[byte_at_offset].append(num) 

, где большую часть времени идет - хорошо ;-)

Есть два стандартных уловок для ускорения такого рода вещи, как приходится делать с движущимися инвариантов из петель:

1. Вычислить "смещение * 8" вне цикла.Храните его в локальной переменной. Сохраните умножение за итерацию.
2. Добавить bucketappender = [bucket.append for bucket in buckets] вне цикла. Сохраняет поиск метода на итерацию.

Объедините их, и цикл выглядит следующим образом:

for num in unsorted: 
    bucketappender[(num & byte_check) >> ofs8](num) 

Сворачивание его одним заявлением также сохраняет пару местного магазина vrbl/выборки опкоды за итерацию.

Но на более высоком уровне стандартным способом ускорения сортировки по методу радикса является использование большего радиуса. Что такое магическое около 256? Ничего, кроме того, это удобно для бит-сдвига. Но так же 512, 1024, 2048 ... это классический коммюник времени/пространства.

PS: для очень длинных чисел,

(num >> offset*8) & 0xff 

будет работать быстрее. Это потому, что ваш num & byte_check занимает время пропорционально log(num). Обычно ему нужно создать целое число размером num.

Answer 2

Вы можете просто использовать один из существующих C или реализаций C++, такие как например, integer_sort из Boost.Sort или u4_sort от usort. На удивление легко вызвать собственный код C или C++ из Python, см. How to sort an array of integers faster than quicksort?

Я полностью понимаю ваше разочарование. Хотя прошло более двух лет, numpy still does not have radix sort. Я дам разработчикам NumPy знать, что они могут просто захватить одну из существующих реализаций; лицензирование не должно быть проблемой.

Answer 3

Это старый поток, но я натолкнулся на это, когда смотрел на radix, сортируя массив положительных целых чисел. Я пытался понять, смогу ли я сделать что-то лучше, чем уже злобно быстрый timsort (снова шляпы к вам, Тим Петерс), который реализует сортировку и сортировку python! Либо я не понимаю некоторые аспекты вышеприведенного кода, либо, если да, то код, представленный выше, имеет некоторые проблемы ИМХО.

1. Он сортирует только байты, начиная с наивысшего байта наименьшего элемента и заканчивая самым высоким байтом самого большого предмета. Это может быть хорошо в некоторых случаях специальных данных. Но в целом подход не может отличить элементы, которые отличаются за счет младших бит. Например:

   arr=[65535,65534] 
   radix_sort(arr) 
   

   выдает неверные результаты:

   [65535, 65534] 
   

2. диапазон, используемый в цикле по функции хелперного не является правильным. Я имею в виду, что если low_byte и maximum_byte одинаковы, выполнение вспомогательной функции вообще пропущено. Кстати, мне пришлось изменить xrange на диапазон в 2-х местах.

3. С изменениями, адресованными выше 2 пунктам, я получил его на работу. Но это занимает в 10-20 раз больше времени, затраченного на сортировку или сортировку python! Я знаю, что timsort очень эффективен и использует уже отсортированные прогоны в данных. Но я пытался понять, могу ли я использовать предварительные знания о том, что мои данные - это целые положительные числа, которые могут быть полезны в моей сортировке. Почему сортировка radix делает это плохо по сравнению с timsort? Размеры массива, которые я использовал, составляют порядка 80 тыс. Единиц.Это связано с тем, что реализация timsort в дополнение к ее алгоритмической эффективности также имеет другие преимущества, связанные с возможным использованием библиотек низкого уровня? Или я чего-то не хватает? Модифицированный код, который я использовал ниже:

   import itertools 
   
   def radix_sort(unsorted): 
       "Fast implementation of radix sort for any size num." 
       maximum, minimum = max(unsorted), min(unsorted) 
   
       max_bits = maximum.bit_length() 
       highest_byte = max_bits // 8 if max_bits % 8 == 0 else (max_bits // 8) + 1 
   
   # min_bits = minimum.bit_length() 
   # lowest_byte = min_bits // 8 if min_bits % 8 == 0 else (min_bits // 8) + 1 
   
       sorted_list = unsorted 
   # xrange changed to range, lowest_byte deleted from the arguments 
       for offset in range(highest_byte): 
        sorted_list = radix_sort_offset(sorted_list, offset) 
   
       return sorted_list 
   
   def radix_sort_offset(unsorted, offset): 
       "Helper function for radix sort, sorts each offset." 
       byte_check = (0xFF << offset*8) 
   
   # xrange changed to range 
       buckets = [[] for _ in range(256)] 
   
       for num in unsorted: 
        byte_at_offset = (num & byte_check) >> offset*8 
        buckets[byte_at_offset].append(num) 
   
       return list(itertools.chain.from_iterable(buckets))