Сортировка по месту

Question

Это длинный текст. Пожалуйста, потерпите меня. Вопрос сводится к следующему: Есть ли работоспособный алгоритм радикальной сортировки на месте ?

---

Предварительные

У меня есть огромное количество небольших строк фиксированной длины , в которых используются только буквы «A», «C», «G» и «T» (да, вы уже догадались : DNA ), которую я хочу отсортировать.

В данный момент я использую std::sort, который использует introsort во всех распространенных реализациях STL . Это работает довольно хорошо. Однако я убежден, что radix sort идеально подходит для моей поставленной задачи и на практике должен работать намного .

Подробнее

Я проверил это предположение с очень наивной реализацией, и для относительно небольших входных данных (порядка 10000) это было правдой (ну, по крайней мере, более чем в два раза быстрее). Тем не менее, время выполнения ужасно ухудшается, когда размер проблемы становится больше ( N > 5 000 000).

Причина очевидна: радикальная сортировка требует копирования всех данных (на самом деле, не раз в моей наивной реализации). Это означает, что я поместил ~ 4 ГиБ в мою основную память, что, очевидно, снижает производительность. Даже если это не так, я не могу позволить себе использовать столько памяти, поскольку размеры проблем на самом деле становятся еще больше.

Варианты использования

В идеале этот алгоритм должен работать с любой длиной строки от 2 до 100, для ДНК, а также для ДНК5 (которая допускает дополнительный подстановочный знак «N») или даже для ДНК с IUPAC коды неоднозначности (в результате получается 16 различных значений). Тем не менее, я понимаю, что все эти случаи не могут быть охвачены, поэтому я доволен любым улучшением скорости, которое я получаю. Код может динамически решать, какой алгоритм отправить.

Research

К сожалению, статья в Википедии о радикальной сортировке бесполезна. Раздел о варианте на месте - полная чушь. Секция NIST-DADS на радикальной сортировке почти не существует. Есть многообещающая статья под названием Эффективная адаптивная сортировка по радикалам на месте , в которой описывается алгоритм «MSL». К сожалению, эта статья тоже разочаровывает.

В частности, есть следующие вещи.

Во-первых, алгоритм содержит несколько ошибок и оставляет много необъяснимых. В частности, он не детализирует рекурсивный вызов (я просто предполагаю, что он увеличивает или уменьшает некоторый указатель для вычисления текущих значений сдвига и маски). Кроме того, он использует функции dest_group и dest_address без определения. Я не вижу, как их эффективно реализовать (то есть в O (1); по крайней мере, dest_address не тривиально).

И наконец, что не менее важно, алгоритм достигает на месте, меняя индексы массива с элементами внутри входного массива. Это очевидно работает только на числовых массивах. Мне нужно использовать его на строки. Конечно, я мог бы просто прокрутить строгую типизацию и продолжить, предполагая, что память будет терпеть мое хранение индекса, которому он не принадлежит. Но это работает только до тех пор, пока я могу сжать свои строки в 32-битной памяти (при условии 32-битных целых). Это всего 16 символов (на данный момент давайте проигнорируем, что 16> log (5 000 000)).

Другой документ одного из авторов не дает точного описания вообще, но он дает время выполнения MSL как сублинейное, что совершенно неверно.

Напомним : Есть ли надежда найти работающую эталонную реализацию или хотя бы хороший псевдокод / ​​описание работающей радикальной сортировки на месте, которая работает на строках ДНК?

Answer 1

Radix-Sort не учитывает кеш и не является самым быстрым алгоритмом сортировки для больших наборов. Вы можете посмотреть на:

• ti7qsort . ti7qsort - это самая быстрая сортировка для целых чисел (может использоваться для строк малого фиксированного размера).
• Встроенный QSORT
• Сортировка строк

Вы также можете использовать сжатие и кодировать каждую букву вашей ДНК в 2 бита перед сохранением в массиве сортировки.

Answer 2

Похоже, что вы решили проблему, но, к сведению, похоже, что одной из версий работоспособной сортировки по осям на месте является "сортировка по американскому флагу". Здесь описано: Сортировка инженерных радиксов . Общая идея состоит в том, чтобы сделать 2 прохода для каждого символа - сначала посчитайте, сколько у вас каждого, чтобы вы могли разделить входной массив на ячейки. Затем пройдите снова, переставляя каждый элемент в нужную корзину. Теперь рекурсивно сортируйте каждую ячейку в следующей позиции символа.

Answer 3

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

Я предлагаю очень простой подход:

1. Эмпирически оцените наибольший размер m, для которого эффективна сортировка по основанию.
2. Одновременное чтение блоков m элементов, их сортировка по основанию, их запись и запись (в буфер памяти, если у вас достаточно памяти, но не для хранения файлов), пока не исчерпаны входные данные.
3. Mergesort результирующие отсортированные блоки.

Mergesort - самый удобный для сортировки алгоритм сортировки, который я знаю: «Считать следующий элемент из массива A или B, а затем записать элемент в выходной буфер». Он эффективно работает на ленточных накопителях . Для сортировки n элементов требуется 2n места, но я держу пари, что значительно улучшенная локальность кэша, которую вы увидите, сделает это неважным - и если вы использовали неортовую сортировку, вы В любом случае, нужно дополнительное пространство.

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

Answer 4

Сначала подумайте о кодировании вашей проблемы. Избавьтесь от строк, замените их двоичным представлением. Используйте первый байт, чтобы указать длину + кодировку. В качестве альтернативы используйте представление фиксированной длины на границе в четыре байта. Тогда радикальная сортировка станет намного проще. Для радикальной сортировки наиболее важным является отсутствие обработки исключений в горячей точке внутреннего цикла.

Хорошо, я немного больше подумал о 4-х сторонней проблеме. Для этого вам нужно решение типа дерева Джуди . Следующее решение может обрабатывать строки переменной длины; для фиксированной длины просто удалите биты длины, что на самом деле делает это проще.

Выделите блоки из 16 указателей. Наименее значимый бит указателей можно использовать повторно, так как ваши блоки всегда будут выровнены. Возможно, вам понадобится специальный распределитель памяти (разбивая большое хранилище на более мелкие блоки). Существует несколько видов блоков:

• Кодирование с 7 битами длины строк переменной длины. По мере их заполнения вы заменяете их на:
• Позиция кодирует следующие два символа, у вас есть 16 указателей на следующие блоки, заканчивающиеся:
• Растровое кодирование последних трех символов строки.

Для каждого типа блока вам нужно хранить различную информацию в младших блоках. Поскольку у вас есть строки переменной длины, вам также необходимо хранить конец строки, а последний тип блока может использоваться только для самых длинных строк. Биты длиной 7 должны быть заменены на меньшие по мере углубления в структуру.

Это обеспечивает вам достаточно быстрое и очень эффективное использование памяти для хранения отсортированных строк. Он будет вести себя примерно как trie . Чтобы это работало, убедитесь, что вы собрали достаточно модульных тестов. Вы хотите охватить все переходы блоков. Вы хотите начать только со второго вида блока.

Для еще большей производительности вы можете захотеть добавить различные типы блоков и больший размер блока. Если блоки всегда одинакового размера и достаточно велики, вы можете использовать еще меньше битов для указателей. С размером блока в 16 указателей у вас уже есть свободный байт в 32-битном адресном пространстве. Посмотрите на документацию по дереву Джуди для интересных типов блоков. По сути, вы добавляете код и время разработки для компромисса между пробелами (и временем выполнения)

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

Вы заинтересованы в обработке двойников? С короткими последовательностями, будут. Адаптировать блоки для обработки счетчиков довольно сложно, но это может быть очень экономно.