Как я могу отсортировать 128-битные целые числа без знака в Python?

Question

У меня огромное количество 128-битных целых чисел без знака, которые нужно отсортировать для анализа (около триллиона из них!).

Исследование, которое я провел по 128-битным целым, привело меня внизв некотором роде тупик, numpy, похоже, не полностью их поддерживает, а внутренние функции сортировки требуют большого объема памяти (используя списки).

Что я хотел бы сделать, это загрузить, например, миллиард128-разрядные целые числа без знака в памяти (16 ГБ, если только двоичные данные) и сортировка их.У рассматриваемой машины есть 48 ГБ ОЗУ, поэтому все в порядке, чтобы использовать 32 ГБ для операции.Если это нужно сделать небольшими порциями, это нормально, но лучше использовать как можно большую порцию.Есть ли в Python алгоритм сортировки, который может принимать такие данные, не требуя огромных накладных расходов?

Я могу отсортировать 128-битные целые числа, используя метод .sort для списков, и это работает, но не может масштабироваться до необходимого мне уровня.У меня есть версия C ++, которая была написана специально для этого и работает невероятно быстро, но я хотел бы воспроизвести ее на Python, чтобы ускорить время разработки (и я не писал C ++, и я не привык к этому языку).

Извините, если для описания проблемы требуется больше информации, пожалуйста, спросите что-нибудь.

Answer 1

Я, вероятно, ожидал слишком многого от Python, но я не разочарован.Несколько минут кодирования позволили мне создать что-то (используя встроенные списки), которое может обработать сортировку сотен миллионов элементов uint128 на ноутбуке 8 ГБ за пару минут.

Учитывая большое количество элементов длясортировка (1 триллион), ясно, что размещение их в более мелкие корзины / файлы при создании имеет больше смысла, чем сортировка огромных чисел в памяти.Потенциальные проблемы, возникающие при добавлении данных в тысячи файлов кусками по 1 МБ (фрагментация на вращающихся дисках), меньше беспокоят из-за сортировки каждого из этих фрагментированных файлов, создавая последовательный файл, который будет прочитан много раз (фрагментированный файлпишется один раз и читается один раз).

Преимущества скорости разработки Python, похоже, перевешивают снижение производительности по сравнению с C / C ++, тем более что сортировка происходит только один раз.

Answer 2

NumPy не поддерживает 128-битные целые числа, но если вы используете структурированный dtype, состоящий из 64-битных кусков без знака с высоким и низким значениями, они будут отсортированы в том же порядке, что и 128-битные целые числа:

arr.sort(order=['high', 'low'])

Что касается того, как вы собираетесь получить массив с этим dtype, это зависит от того, как вы загружаете свои данные в первую очередь.Я полагаю, что это может потребовать вызова ndarray.view для повторной интерпретации байтов другого массива.Например, если у вас есть массив dtype uint8, байты которого следует интерпретировать как 128-разрядные целые числа без знака с прямым порядком байтов на машине с прямым порядком байтов:

arr_structured = arr_uint8.view([('low', 'uint64'), ('high', 'uint64')])

---

Так что это может быть разумнымза миллиард, но вы говорите, что у вас есть около триллион из них.Это намного больше, чем может обрабатывать оперативная память на компьютере с 48 ГБ ОЗУ.Вы не просили что-то для одновременной обработки всего набора данных с триллионами элементов, поэтому я надеюсь, что у вас уже есть хорошее решение для объединения отсортированных кусков или для предварительного разделения набора данных.