Эффективная по кешу случайная перестановка элементов массива

Если вычисление этой твоей MPHF для всех элементов много быстрее их линейной записи и чтения на диск, то можешь выделить окно в 8гб для левой половины результата, переставить с записью в RAM, отбрасывая промахи, а потом линейной слить на диск. Повторить для всех окон.

Хочется как в анекдоте про чайник свети к уже решённой задаче. По сути это внешняя сортировка массива, где искомый порядок определяется a<b <=> MPHF(a) < MPHF(b).

Хм, кстати да, интересно что выиграет – сортировка n*logn, но с последовательным доступом, или линейная перестановка в памяти со случайным доступом блоками в 3 прохода, 3 = log log 10^9, например.

Вычисление MPHF медленнее, конечно. Но оно состоит из похожих операций, правда не перестановки, а группировки элементов по хешу. Я не записал время операций в блокнотик прежде чем рефакторить всё это, но ирония была в том, что однопоточное построение MPHF (сложный алгоритм) по времени, кажется, получалось сравнимо с тупой перестановкой 17GB из-за cache miss. Т.е. 2х кратно увеличивалось время обработки на банальной перестановке элементов.

Собственно спрашиваю «исследована ли эта тема» ещё потому, что может я зря упарываюсь делать это всё руками на C++ (ещё и через страшный Apache Arrow C++ API), и в каком-нибудь clickhouse всё это можно сделать эффективно из коробки правильным sql.

Но чуйка подсказыает, что для такой простой задачи должен быть 10 раз исследован оптимальный классический подход в базах данных. Гугл что-то молчит.

Гугл скрывает :-)

супер алгоритм называется ПЕРЕСТАНОВКА (частный случай СОРТИРОВКИ, когда вместо веса позиционный индекс), потому-что это она и есть, просто на собесе вам запудрили мозг кривой постановкой задачи.

Не взрывая мозг теорией графов/парасочетаний и деревьями диапазонов - просто возьмите подходящий по оценке память/скорость алгоритм "сортировка на внешнем носителе", ваша функция MPHF - это вес.

Транзитивность выполняется? Многие алгоритмы сортировки не могут работать со странными правилами сравнения.

Кэп не читатель. Я же написал, где ваши цифры. Совсем не очевидно, что будет быстрее – сортировка где «log n == 20» или разбиение на блоки и случайный доступ. Вероятно можно совместить.

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

И это, кстати, не собес, а вполне реальный набор данных. Хочу переделать хеш таблицу в кучу на arrow + perfect hash + mmap.

Не занимайтесь хернёй, читайте основополагающие книги. Ключевые слова Сортировка и реиндекс (иногда ребейз), там всё написано.

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

Совсем не очевидно, что будет быстрее – сортировка где «log n == 20» или разбиение на блоки и случайный доступ.

Напиши да проверь на маленьком подмножестве. Тут кода вроде не слишком много выходит.

Транзитивность выполняется? Многие алгоритмы сортировки не могут работать со странными правилами сравнения.

Как ты можешь задавать такие вопросы?! :) Конечно же выполняется:

a<b, b<c   =>   MPHF(a) < MPHF(b), MPHF(b) < MPHF(c)   = >   MPHF(a) < MPHF(c)   =>   a<c

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

Если нужно менять порядок на месте, разделил бы весь массив на блоки, для каждого блока завёл бы текущий индекс, дальше последовательно искал бы в каждом блоке первый элемент, этому блоку не принадлежащий, после чего устраивал бы обмены этих элементов. По завершении этого шага у меня были бы блоки, в которых только те элементы, которые должны находиться в этих блоках. Дальше уже тривиально, переставить элементы внутри одного гигабайтного блока несложно. Минус - потенциально двойная перезапись файла, но при этом и чтения и записи последовательно внутри каждого блока.