Как я могу отсортировать 128-битные целые числа без знака в Python?
У меня огромное количество 128-битных целых чисел без знака, которые нужно отсортировать для анализа (около триллиона из них!).
Исследования, проведенные мной по 128-битным целым числам, привели меня в тупик, кажется, что numpy не поддерживает их полностью, а внутренние функции сортировки требуют большого объема памяти (используя списки).
Я хотел бы, например, загрузить в память миллиард 128-битных целых чисел без знака (16 ГБ, если это просто двоичные данные) и отсортировать их. У рассматриваемой машины есть 48 ГБ ОЗУ, поэтому все в порядке, чтобы использовать 32 ГБ для этой операции. Если это нужно сделать небольшими порциями, это нормально, но лучше использовать как можно большую порцию. Есть ли в Python алгоритм сортировки, который может принимать такие данные, не требуя огромных накладных расходов?
Я могу отсортировать 128-битные целые числа, используя метод.sort для списков, и это работает, но не может масштабироваться до необходимого мне уровня. У меня есть версия C++, которая была написана специально для этого и работает невероятно быстро, но я хотел бы воспроизвести ее на Python, чтобы ускорить время разработки (и я не писал C++, и я не привык к этому языку),
Извинения, если для описания проблемы требуется больше информации, пожалуйста, спросите что-нибудь.
2 ответа
NumPy не поддерживает 128-битные целые числа, но если вы используете структурированный d-тип, состоящий из 64-битных кусков без знака с высоким и низким значениями, они будут отсортированы в том же порядке, что и 128-битные целые числа:
arr.sort(order=['high', 'low'])
Что касается того, как вы собираетесь получить массив с этим dtype, это зависит от того, как вы загружаете ваши данные в первую очередь. Я полагаю, это может быть связано с вызовом ndarray.viewпереосмыслить байты другого массива. Например, если у вас есть массив dtype uint8, байты которого следует интерпретировать как 128-разрядные целые числа без знака с прямым порядком байтов на машине с прямым порядком байтов:
arr_structured = arr_uint8.view([('low', 'uint64'), ('high', 'uint64')])
Так что это может быть разумно для миллиарда целых, но вы говорите, что у вас есть около триллиона таких. Это намного больше, чем может обрабатывать оперативная память на компьютере с 48 ГБ ОЗУ. Вы не просили что-то для одновременной обработки всего набора данных с триллионами элементов, поэтому я надеюсь, что у вас уже есть хорошее решение для объединения отсортированных кусков или для предварительного разбиения набора данных.
Я, вероятно, ожидал слишком многого от Python, но я не разочарован. Несколько минут кодирования позволили мне создать что-то (используя встроенные списки), которое может обработать сортировку сотен миллионов элементов uint128 на ноутбуке 8 ГБ за пару минут.
Учитывая большое количество сортируемых элементов (1 триллион), ясно, что размещение их в более мелкие корзины / файлы при создании имеет больше смысла, чем сортировка огромных чисел в памяти. Потенциальные проблемы, возникающие при добавлении данных в тысячи файлов кусками по 1 МБ (фрагментация на вращающихся дисках), меньше беспокоят из-за сортировки каждого из этих фрагментированных файлов, создавая последовательный файл, который будет прочитан много раз (фрагментированный файл написал один раз и прочитал один раз).
Преимущества скорости разработки Python, похоже, перевешивают снижение производительности по сравнению с C/C++, тем более что сортировка происходит только один раз.