Сортировка по месту
Это длинный текст. Пожалуйста, потерпите меня. Вопрос сводится к следующему: существует ли работоспособный алгоритм сортировки по основанию?
предварительный
У меня есть огромное количество маленьких строк фиксированной длины, которые используют только буквы "A", "C", "G" и "T" (да, вы уже догадались: ДНК), которые я хочу отсортировать.
На данный момент пользуюсь std::sort который использует интросорт во всех распространенных реализациях STL. Это работает довольно хорошо. Тем не менее, я убежден, что радикальная сортировка идеально подходит для моей задачи и должна работать намного лучше на практике.
подробности
Я проверил это предположение с очень наивной реализацией, и для относительно небольших входных данных (порядка 10000) это было правдой (ну, по крайней мере, более чем в два раза быстрее). Тем не менее, время выполнения ужасно ухудшается, когда размер проблемы становится больше (N > 5 000 000).
Причина очевидна: радикальная сортировка требует копирования всех данных (на самом деле, не раз в моей наивной реализации). Это означает, что я поместил ~ 4 ГиБ в мою основную память, что, очевидно, снижает производительность. Даже если это не так, я не могу позволить себе использовать столько памяти, поскольку размеры проблем на самом деле становятся еще больше.
Случаи применения
В идеале этот алгоритм должен работать с любой длиной строки от 2 до 100, для ДНК, а также для ДНК5 (которая допускает дополнительный подстановочный знак "N"), или даже для ДНК с кодами неоднозначности IUPAC (в результате получается 16 различных значений). Тем не менее, я понимаю, что все эти случаи не могут быть охвачены, поэтому я доволен любым улучшением скорости, которое я получаю. Код может динамически решать, какой алгоритм отправить.
Исследование
К сожалению, статья в Википедии о радикальной сортировке бесполезна. Раздел о варианте на месте - полная чушь. Раздел NIST-DADS для сортировки по основанию почти отсутствует. Есть многообещающая статья под названием " Эффективная адаптивная сортировка по месту нахождения радиксов", в которой описывается алгоритм "MSL". К сожалению, эта статья тоже разочаровывает.
В частности, есть следующие вещи.
Во-первых, алгоритм содержит несколько ошибок и оставляет много необъяснимых. В частности, он не детализирует рекурсивный вызов (я просто предполагаю, что он увеличивает или уменьшает некоторый указатель для вычисления текущих значений сдвига и маски). Кроме того, он использует функции dest_group а также dest_address без определения. Я не вижу, как реализовать их эффективно (то есть в O(1); по крайней мере, dest_address не тривиально).
Наконец, что не менее важно, алгоритм достигает на месте, меняя индексы массива с элементами внутри входного массива. Это очевидно работает только на числовых массивах. Мне нужно использовать его на строки. Конечно, я мог бы просто прокрутить строгую типизацию и продолжить, предполагая, что память будет терпеть мое хранение индекса там, где он не принадлежит. Но это работает только до тех пор, пока я могу сжать свои строки в 32-битной памяти (при условии 32-битных целых). Это всего 16 символов (на данный момент давайте игнорируем 16 > log(5 000 000)).
Другая статья одного из авторов не дает точного описания вообще, но она дает время выполнения MSL как сублинейное, что совершенно неверно.
Напомним: есть ли надежда найти работающую эталонную реализацию или, по крайней мере, хороший псевдокод / описание работающей радикальной сортировки на месте, которая работает на цепочках ДНК?
15 ответов
Ну, вот простая реализация радикальной сортировки MSD для ДНК. Он написан на D, потому что это язык, которым я больше всего пользуюсь, и поэтому он менее всего допускает глупые ошибки, но его легко перевести на другой язык. Это на месте, но требует 2 * seq.length проходит через массив.
void radixSort(string[] seqs, size_t base = 0) {
if(seqs.length == 0)
return;
size_t TPos = seqs.length, APos = 0;
size_t i = 0;
while(i < TPos) {
if(seqs[i][base] == 'A') {
swap(seqs[i], seqs[APos++]);
i++;
}
else if(seqs[i][base] == 'T') {
swap(seqs[i], seqs[--TPos]);
} else i++;
}
i = APos;
size_t CPos = APos;
while(i < TPos) {
if(seqs[i][base] == 'C') {
swap(seqs[i], seqs[CPos++]);
}
i++;
}
if(base < seqs[0].length - 1) {
radixSort(seqs[0..APos], base + 1);
radixSort(seqs[APos..CPos], base + 1);
radixSort(seqs[CPos..TPos], base + 1);
radixSort(seqs[TPos..seqs.length], base + 1);
}
}
Очевидно, что это специфично для ДНК, в отличие от общего, но оно должно быть быстрым.
Редактировать:
Мне стало любопытно, работает ли этот код на самом деле, поэтому я протестировал / отладил его, ожидая запуска собственного кода биоинформатики. Версия выше теперь на самом деле протестирована и работает. Для 10 миллионов последовательностей по 5 оснований это примерно в 3 раза быстрее, чем оптимизированный интросорт.
Я никогда не видел сортировку по основанию на месте, и из-за природы сортировки по знаку я сомневаюсь, что это намного быстрее, чем сортировка по месту, если временный массив помещается в память.
Причина:
Сортировка выполняет линейное чтение входного массива, но все записи будут почти случайными. От определенного N и выше это сводится к пропуску кэша за запись. Это промах кэша замедляет ваш алгоритм. Если он на месте или нет, это не изменит этот эффект.
Я знаю, что это не даст прямого ответа на ваш вопрос, но если сортировка является узким местом, вы можете рассмотреть алгоритмы сортировки, близкие к сортировке, в качестве шага предварительной обработки (вики-страница на мягкой куче может помочь вам начать работу).
Это может дать очень хороший прирост локальности кэша. Сортировка осциллограмм вне учебника будет эффективнее. Записи будут по-прежнему почти случайными, но, по крайней мере, они будут группироваться вокруг одинаковых кусков памяти и, как таковые, увеличивают коэффициент попадания в кэш.
Я понятия не имею, работает ли это на практике все же.
Кстати: если вы имеете дело только со строками ДНК: вы можете сжать символ в два бита и упаковать свои данные довольно много. Это сократит требования к памяти в четыре раза по сравнению с простым представлением. Адресация становится более сложной, но ALU вашего ЦП все равно тратит много времени на все пропуски кэша.
Основываясь на коде dsimcha, я реализовал более общую версию, которая хорошо вписывается в структуру, которую мы используем (SeqAn). На самом деле, перенос кода был совершенно простым. Только после этого я обнаружил, что на самом деле есть публикации по этой теме. Самое замечательное: они в основном говорят то же, что и вы, ребята. Документ Андерссона и Нильссона о внедрении Radixsort определенно стоит прочитать. Если вы знаете немецкий, обязательно прочитайте дипломную работу Дэвида Виза, в которой он реализует общий подстроковой индекс. Большая часть диссертации посвящена детальному анализу затрат на построение индекса с учетом вторичной памяти и чрезвычайно больших файлов. Результаты его работы фактически были реализованы в SeqAn, но не в тех частях, где мне это было нужно.
Просто для забавы, вот код, который я написал (я не думаю, что кто-то, кто не использует SeqAn, будет его использовать). Обратите внимание, что он все еще не рассматривает радиусы больше 4. Я ожидаю, что это окажет огромное влияние на производительность, но, к сожалению, у меня сейчас просто нет времени, чтобы реализовать это.
Код выполняет более чем в два раза быстрее, чем Introsort для коротких строк. Точка безубыточности имеет длину около 12–13. Тип строки (например, имеет ли она 4, 5 или 16 различных значений) сравнительно не важен. Сортировка> 6 000 000 считываний ДНК из хромосомы 2 человеческого генома занимает чуть более 2 секунд на моем ПК. Просто для записи, это быстро! Особенно учитывая, что я не использую SIMD или любое другое аппаратное ускорение. Кроме того, Вальгринд показывает мне, что основным узким местом является operator new в строковых назначениях. Он вызывается около 65 000 000 раз - по десять раз для каждой строки! Это мертвая распродажа swap можно оптимизировать под эти строки: вместо копирования можно просто поменять местами все символы. Я не пробовал это, но я уверен, что это будет иметь огромное значение. И, чтобы еще раз сказать, на случай, если кто-то не слушал: размер радиуса почти не влияет на время выполнения - это означает, что я должен определенно попытаться реализовать предложение, сделанное FryGuy, Stephan и EvilTeach.
Ах да, кстати: локальность кэша является заметным фактором: начиная со строк 1М, время выполнения больше не увеличивается линейно. Однако это можно исправить довольно легко: я использую сортировку вставкой для небольших подмножеств (<= 20 строк) - вместо сортировки слиянием, как это было предложено случайным хакером. Очевидно, что для таких небольших списков это работает даже лучше, чем сортировка слиянием (см. Первую статью, которую я связал).
namespace seqan {
template <typename It, typename F, typename T>
inline void prescan(It front, It back, F op, T const& id) {
using namespace std;
if (front == back) return;
typename iterator_traits<It>::value_type accu = *front;
*front++ = id;
for (; front != back; ++front) {
swap(*front, accu);
accu = op(accu, *front);
}
}
template <typename TIter, typename TSize, unsigned int RADIX>
inline void radix_permute(TIter front, TIter back, TSize (& bounds)[RADIX], TSize base) {
for (TIter i = front; i != back; ++i)
++bounds[static_cast<unsigned int>((*i)[base])];
TSize fronts[RADIX];
std::copy(bounds, bounds + RADIX, fronts);
prescan(fronts, fronts + RADIX, std::plus<TSize>(), 0);
std::transform(bounds, bounds + RADIX, fronts, bounds, plus<TSize>());
TSize active_base = 0;
for (TIter i = front; i != back; ) {
if (active_base == RADIX - 1)
return;
while (fronts[active_base] >= bounds[active_base])
if (++active_base == RADIX - 1)
return;
TSize current_base = static_cast<unsigned int>((*i)[base]);
if (current_base <= active_base)
++i;
else
std::iter_swap(i, front + fronts[current_base]);
++fronts[current_base];
}
}
template <typename TIter, typename TSize>
inline void insertion_sort(TIter front, TIter back, TSize base) {
typedef typename Value<TIter>::Type T;
struct {
TSize base, len;
bool operator ()(T const& a, T const& b) {
for (TSize i = base; i < len; ++i)
if (a[i] < b[i]) return true;
else if (a[i] > b[i]) return false;
return false;
}
} cmp = { base, length(*front) }; // No closures yet. :-(
for (TIter i = front + 1; i != back; ++i) {
T value = *i;
TIter j = i;
for ( ; j != front && cmp(value, *(j - 1)); --j)
*j = *(j - 1);
if (j != i)
*j = value;
}
}
template <typename TIter, typename TSize, unsigned int RADIX>
inline void radix(TIter top, TIter front, TIter back, TSize base, TSize (& parent_bounds)[RADIX], TSize next) {
if (back - front > 20) {
TSize bounds[RADIX] = { 0 };
radix_permute(front, back, bounds, base);
// Sort current bucket recursively by suffix.
if (base < length(*front) - 1)
radix(front, front, front + bounds[0], base + 1, bounds, static_cast<TSize>(0));
}
else if (back - front > 1)
insertion_sort(front, back, base);
// Sort next buckets on same level recursively.
if (next == RADIX - 1) return;
radix(top, top + parent_bounds[next], top + parent_bounds[next + 1], base, parent_bounds, next + 1);
}
template <typename TIter>
inline void radix_sort(TIter front, TIter back) {
typedef typename Container<TIter>::Type TStringSet;
typedef typename Value<TStringSet>::Type TString;
typedef typename Value<TString>::Type TChar;
typedef typename Size<TStringSet>::Type TSize;
TSize const RADIX = ValueSize<TChar>::VALUE;
TSize bounds[RADIX];
radix(front, front, back, static_cast<TSize>(0), bounds, RADIX - 1);
}
} // namespace seqan
Вы, конечно, можете отказаться от требований к памяти, кодируя последовательность в битах. Вы смотрите на перестановки, поэтому для длины 2 с "ACGT" это 16 состояний или 4 бита. Для длины 3 это 64 состояния, которые могут быть закодированы в 6 битах. Таким образом, это выглядит как 2 бита для каждой буквы в последовательности, или около 32 бит для 16 символов, как вы сказали.
Если есть способ уменьшить количество допустимых "слов", дальнейшее сжатие может быть возможным.
Таким образом, для последовательностей длиной 3 можно создать 64 сегмента, возможно, размера uint32 или uint64. Инициализируйте их до нуля. Переберите свой очень большой список из 3 последовательностей символов и закодируйте их, как указано выше. Используйте это как индекс, и увеличивайте этот сегмент.
Повторяйте это, пока все ваши последовательности не будут обработаны.
Затем обновите свой список.
Итерация по 64 сегментам по порядку, для счетчика, найденного в этом сегменте, генерирует столько экземпляров последовательности, представленных этим сегментом.
когда все сегменты были повторены, у вас есть отсортированный массив.
Последовательность из 4 добавляет 2 бита, поэтому будет 256 блоков. Последовательность из 5 добавляет 2 бита, поэтому будет 1024 сегмента.
В какой-то момент количество ведер приблизится к вашим пределам. Если вы читаете последовательности из файла, вместо того, чтобы хранить их в памяти, для сегментов памяти будет больше памяти.
Я думаю, что это будет быстрее, чем выполнять сортировку на месте, так как ведра, скорее всего, будут соответствовать вашему рабочему набору.
Вот взлом, который показывает технику
#include <iostream>
#include <iomanip>
#include <math.h>
using namespace std;
const int width = 3;
const int bucketCount = exp(width * log(4)) + 1;
int *bucket = NULL;
const char charMap[4] = {'A', 'C', 'G', 'T'};
void setup
(
void
)
{
bucket = new int[bucketCount];
memset(bucket, '\0', bucketCount * sizeof(bucket[0]));
}
void teardown
(
void
)
{
delete[] bucket;
}
void show
(
int encoded
)
{
int z;
int y;
int j;
for (z = width - 1; z >= 0; z--)
{
int n = 1;
for (y = 0; y < z; y++)
n *= 4;
j = encoded % n;
encoded -= j;
encoded /= n;
cout << charMap[encoded];
encoded = j;
}
cout << endl;
}
int main(void)
{
// Sort this sequence
const char *testSequence = "CAGCCCAAAGGGTTTAGACTTGGTGCGCAGCAGTTAAGATTGTTT";
size_t testSequenceLength = strlen(testSequence);
setup();
// load the sequences into the buckets
size_t z;
for (z = 0; z < testSequenceLength; z += width)
{
int encoding = 0;
size_t y;
for (y = 0; y < width; y++)
{
encoding *= 4;
switch (*(testSequence + z + y))
{
case 'A' : encoding += 0; break;
case 'C' : encoding += 1; break;
case 'G' : encoding += 2; break;
case 'T' : encoding += 3; break;
default : abort();
};
}
bucket[encoding]++;
}
/* show the sorted sequences */
for (z = 0; z < bucketCount; z++)
{
while (bucket[z] > 0)
{
show(z);
bucket[z]--;
}
}
teardown();
return 0;
}
Если ваш набор данных настолько велик, то я думаю, что дисковый буферный подход будет лучше:
sort(List<string> elements, int prefix)
if (elements.Count < THRESHOLD)
return InMemoryRadixSort(elements, prefix)
else
return DiskBackedRadixSort(elements, prefix)
DiskBackedRadixSort(elements, prefix)
DiskBackedBuffer<string>[] buckets
foreach (element in elements)
buckets[element.MSB(prefix)].Add(element);
List<string> ret
foreach (bucket in buckets)
ret.Add(sort(bucket, prefix + 1))
return ret
Я бы также экспериментировал с группировкой в большее количество сегментов, например, если ваша строка была:
GATTACA
первый вызов MSB вернул бы корзину для GATT (всего 256 блоков), таким образом вы делаете меньше ветвей дискового буфера. Это может или не может улучшить производительность, поэтому экспериментируйте с этим.
Я собираюсь выйти на конечность и предложить вам переключиться на реализацию heap / heapsort. Это предложение приходит с некоторыми предположениями:
- Вы контролируете чтение данных
- Вы можете сделать что-то значимое с отсортированными данными, как только вы начнете сортировать их.
Прелесть кучи / сортировки кучи заключается в том, что вы можете построить кучу во время чтения данных, и вы можете начать получать результаты, как только построите кучу.
Давайте сделаем шаг назад. Если вам так повезло, что вы можете читать данные асинхронно (то есть вы можете опубликовать какой-то запрос на чтение и получить уведомление, когда некоторые данные будут готовы), а затем вы можете построить кусок кучи, пока вы ожидаете следующая порция данных для входа - даже с диска. Часто такой подход может похоронить большую часть затрат на половину вашей сортировки за время, потраченное на получение данных.
После прочтения данных первый элемент уже доступен. В зависимости от того, куда вы отправляете данные, это может быть здорово. Если вы отправляете его другому асинхронному считывающему устройству или какой-либо параллельной модели "события" или пользовательскому интерфейсу, вы можете отправлять куски и куски по ходу работы.
Тем не менее, если у вас нет контроля над тем, как данные считываются, и они читаются синхронно, и вы не пользуетесь отсортированными данными до тех пор, пока они полностью не будут записаны, - игнорируйте все это.:(
Смотрите статьи в Википедии:
" Radix sorting без лишних пробелов" - это документ, посвященный вашей проблеме.
С точки зрения производительности вы можете захотеть взглянуть на более общие алгоритмы сортировки сравнения строк.
В настоящее время вы касаетесь каждого элемента каждой струны, но вы можете добиться большего!
В частности, пакетная сортировка очень подходит для этого случая. В качестве бонуса, поскольку пакетная сортировка основана на попытках, она работает смехотворно хорошо для небольших размеров алфавита, используемых в ДНК / РНК, так как вам не нужно встраивать какие-либо схемы троичного поискового узла, хеша или другого трехэлементного сжатия в Три реализации. Попытки также могут быть полезны для вашей конечной цели, подобной массиву суффиксов.
Достойная реализация общего назначения для burstsort доступна в Source Forge по адресу http://sourceforge.net/projects/burstsort/ но она не на месте.
В целях сравнения реализация C-burstsort описана по адресу http://www.cs.mu.oz.au/~rsinha/papers/SinhaRingZobel-2006.pdf Тесты в 4-5 раз быстрее, чем сортировка по быстродействию и радикальная сортировка для некоторых типичных рабочих нагрузок.
Вы захотите взглянуть на крупномасштабную обработку последовательности генома от доктора. Касахара и Моришита.
Строки, состоящие из четырех нуклеотидных букв A, C, G и T, могут быть специально закодированы в целые числа для гораздо более быстрой обработки. Radix sort является одним из многих алгоритмов, обсуждаемых в книге; Вы должны быть в состоянии адаптировать принятый ответ на этот вопрос и увидеть значительное улучшение производительности.
Я бы рассортировал упакованное битовое представление строк. Утверждается, что Burstsort имеет гораздо лучшую локальность, чем сортировки по основанию, что позволяет сократить использование дополнительного пространства при использовании серийных попыток вместо классических попыток. Оригинальная статья имеет размеры.
Вы можете попробовать использовать Trie. Сортировка данных - это просто повторение набора данных и вставка его; структура естественно отсортирована, и вы можете думать о ней как о B-дереве (за исключением того, что вместо сравнения вы всегда используете указатели).
Поведение кэширования будет благоприятствовать всем внутренним узлам, поэтому вы, вероятно, не улучшите это; но вы также можете использовать фактор ветвления вашего дерева (убедитесь, что каждый узел помещается в одну строку кэша, выделите узлы дерева, похожие на кучу, в виде непрерывного массива, представляющего обход уровня порядка). Поскольку попытки также являются цифровыми структурами (O(k) вставка / поиск / удаление для элементов длины k), вы должны иметь конкурентоспособную производительность по сравнению с сортировкой по основанию.
Radix-Sort не учитывает кеш и не является самым быстрым алгоритмом сортировки для больших наборов. Вы можете посмотреть на:
- ti7qsort. ti7qsort - это самая быстрая сортировка для целых чисел (может использоваться для строк малого фиксированного размера).
- Встроенный QSORT
- Сортировка строк
Вы также можете использовать сжатие и кодировать каждую букву вашей ДНК в 2 бита перед сохранением в массиве сортировки.
Похоже, что вы решили проблему, но, к сведению, похоже, что одной из версий работоспособной сортировки по осям радиуса является "сортировка по американскому флагу". Это описано здесь: Инженерная сортировка Radix. Общая идея состоит в том, чтобы сделать 2 прохода для каждого символа - сначала посчитайте, сколько у вас каждого, чтобы вы могли разделить входной массив на ячейки. Затем пройдите снова, переставляя каждый элемент в нужную корзину. Теперь рекурсивно сортируйте каждую ячейку в следующей позиции символа.
Сначала подумайте о кодировании вашей проблемы. Избавьтесь от строк, замените их двоичным представлением. Используйте первый байт, чтобы указать длину + кодировку. В качестве альтернативы используйте представление фиксированной длины на границе в четыре байта. Тогда радикальная сортировка станет намного проще. Для радикальной сортировки самое важное - не обрабатывать исключения в горячей точке внутреннего цикла.
Хорошо, я подумал немного больше о 4-х проблема. Вы хотите решение, как дерево Джуди для этого. Следующее решение может обрабатывать строки переменной длины; для фиксированной длины просто удалите биты длины, что на самом деле делает это проще.
Выделите блоки по 16 указателей. Наименее значимый бит указателей можно использовать повторно, поскольку ваши блоки всегда будут выровнены. Возможно, вам понадобится специальный распределитель памяти (разбивая большое хранилище на более мелкие блоки). Существует несколько видов блоков:
- Кодирование с 7 битами длины строк переменной длины. Когда они заполняются, вы заменяете их:
- Позиция кодирует следующие два символа, у вас есть 16 указателей на следующие блоки, заканчивающиеся:
- Растровое кодирование последних трех символов строки.
Для каждого вида блока вам нужно хранить различную информацию в младших блоках. Поскольку у вас есть строки переменной длины, вам также необходимо хранить конец строки, а последний тип блока может использоваться только для самых длинных строк. Биты длиной 7 должны быть заменены на меньшие по мере углубления в структуру.
Это обеспечивает вам достаточно быстрое и очень эффективное использование памяти для хранения отсортированных строк. Это будет вести себя как три. Чтобы это работало, убедитесь, что вы собрали достаточно модульных тестов. Вы хотите охватить все переходы блоков. Вы хотите начать только со второго вида блока.
Для еще большей производительности вы можете захотеть добавить различные типы блоков и больший размер блока. Если блоки всегда одинакового размера и достаточно велики, вы можете использовать еще меньше битов для указателей. С размером блока в 16 указателей у вас уже есть свободный байт в 32-битном адресном пространстве. Посмотрите на документацию по дереву Джуди для интересных типов блоков. По сути, вы добавляете код и время разработки для компромисса между пространством (и временем выполнения)
Возможно, вы захотите начать с прямого радиуса 256 для первых четырех символов. Это обеспечивает достойный компромисс между временем и пространством. В этой реализации вы получаете гораздо меньше памяти, чем при простом использовании; это примерно в три раза меньше (я не измерял). O(n) не проблема, если константа достаточно мала, как вы заметили, сравнивая с быстрой сортировкой O(n log n).
Вы заинтересованы в обработке двойников? С короткими последовательностями они будут. Адаптировать блоки для обработки счетчиков довольно сложно, но это может быть очень экономно.
Сортировка MSB radix в dsimcha выглядит неплохо, но Нильс становится ближе к сути проблемы, наблюдая, что локальность кэша убивает вас при больших размерах проблем.
Я предлагаю очень простой подход:
- Эмпирически оценить самый большой размер
mдля которого эффективная сортировка эффективна. - Читать блоки
mэлементы по очереди, основательно сортируют их и записывают их (в буфер памяти, если у вас достаточно памяти, но не для хранения файлов), пока вы не исчерпаете свой ввод. - Объединить полученные отсортированные блоки.
Mergesort - это самый удобный для сортировки алгоритм сортировки, который мне известен: "Считать следующий элемент из массива A или B, а затем записать элемент в выходной буфер". Он эффективно работает на ленточных накопителях. Это требует 2n пространство для сортировки n Предметы, но я держу пари, что значительно улучшенная локальность кэша, которую вы увидите, сделает это неважным - и если вы использовали сортировку по методу "не на месте", вам все равно понадобится это дополнительное пространство.
Наконец, обратите внимание, что сортировка слиянием может быть реализована без рекурсии, и на самом деле, делая это таким образом, вы понимаете истинную линейную модель доступа к памяти.
Хотя принятый ответ полностью отвечает описанию проблемы, я дошел до этого места, тщетно пытаясь найти алгоритм для разделения встроенного массива на N частей. Я сам написал одну, вот она.
Предупреждение: это нестабильный алгоритм разбиения, поэтому для многоуровневого разбиения необходимо переразбивать каждый результирующий раздел, а не весь массив. Преимущество в том, что он встроенный.
Способ, которым это помогает с поставленным вопросом, заключается в том, что вы можете многократно разбивать встроенные разделы на основе буквы в строке, а затем сортировать разделы, когда они достаточно малы, с помощью алгоритма по вашему выбору.
function partitionInPlace(input, partitionFunction, numPartitions, startIndex=0, endIndex=-1) {
if (endIndex===-1) endIndex=input.length;
const starts = Array.from({ length: numPartitions + 1 }, () => 0);
for (let i = startIndex; i < endIndex; i++) {
const val = input[i];
const partByte = partitionFunction(val);
starts[partByte]++;
}
let prev = startIndex;
for (let i = 0; i < numPartitions; i++) {
const p = prev;
prev += starts[i];
starts[i] = p;
}
const indexes = [...starts];
starts[numPartitions] = prev;
let bucket = 0;
while (bucket < numPartitions) {
const start = starts[bucket];
const end = starts[bucket + 1];
if (end - start < 1) {
bucket++;
continue;
}
let index = indexes[bucket];
if (index === end) {
bucket++;
continue;
}
let val = input[index];
let destBucket = partitionFunction(val);
if (destBucket === bucket) {
indexes[bucket] = index + 1;
continue;
}
let dest;
do {
dest = indexes[destBucket] - 1;
let destVal;
let destValBucket = destBucket;
while (destValBucket === destBucket) {
dest++;
destVal = input[dest];
destValBucket = partitionFunction(destVal);
}
input[dest] = val;
indexes[destBucket] = dest + 1;
val = destVal;
destBucket = destValBucket;
} while (dest !== index)
}
return starts;
}