Написать сортировку файла за 3 часа (брутал-собес)

во-первых N log N, т.к. сортировка по умолчанию это вызов quicksort

разве quicksort сможет работать при 512М памяти и 4Gb данных?

а). в свопе сидеть будет :)

б). сортировать ты будешь не сами строки, а отсупы до начала строк, так что весить это будет 4GB/20b*sizeof(void *), сам считай, но в этом случае будет много лишних fread, обращения к диску можно кешировать, но это надо смотреть.

в). автор вопроса поленился ответить сколько можно использовать «лишнего места».

Пункт б). возникает из «свойств» qsort.

от блин, все равно много.

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

Из примера видно, что строка порядка 50 байт, это порядка 80млн смещений. Если файл и правда меньше 4г, то индекс влезает в память, но толку от этого мало.

возможно, но как я уже сказал лучше смотреть в сторону разбиваний на чанки по <256Mb сортировать их и дальше думать над объединением :)

Сортировать надо индекс, а потом создать новый сортированный файл.

Если средняя строка ~ 50 байт, то места для индекса хватит (~320Мб); нужно сделать inplace_merge_sort индексов. Но при этом получим O(n log n) операций чтения с диска, причём с очень приличным множителем.

Если действовать похитрее можно сделать (вроде бы) O (n) операций чтения с небольшим множителем.

Судя по тэгу «Яндех» это актуально.

Ну, а если средняя длина строки больше 75 байт (например, волшебные кириллические домены), то сортировка индексов вообще не прокатит - не хватит на них места.

возможно, но как я уже сказал лучше смотреть в сторону разбиваний на чанки по <256Mb сортировать их и дальше думать над объединением

Вы делаете мне смешно. Это было предложено в 3-ем комментарии. И что там думать mergesort известен, ничего придумывать не надо.

Ну, а если средняя длина строки больше 75 байт (например, волшебные кириллические домены), то сортировка индексов вообще не прокатит - не хватит на них места.

я думал над этим. Я думаю достаточно отсортировать только по первым n байт. Скажем n=10 более чем достаточно. А дальше на финальном этапе сделать второй прогон по файлу и досортировать если что-то не по порядку.

O (n) операций чтения с небольшим множителем

Это как интересно?

сортировать ты будешь не сами строки, а отсупы до начала строк

не понимаю, ты о каких отступах говоришь? Я думал каждая строка начинается с e-mail.

Это было предложено в 3-ем комментарии.

и?

И что там думать mergesort известен, ничего придумывать не надо.

mergesort не inplace, так что если нельзя использовать лишние 4 GB дискового пространства, то не прокатит и придётся делать доп. обвязку.

отступах от начала файла до начала строки.

Сами строки перемещать в файле нереально, поэтому массив в памяти будет содержать только указатели на начала строк в файле. Это и то, что все называют «индекс».

bucket sort? (правда он тут не к месту)

s/Это и то/Это и есть то/

mergesort не inplace

Да? Правда? В merge_sort, внезапно, вызывается merge, и он может быть и inplace. Причём, этот inplace_merge может быть O(n) [но обычно реализуется O(n log n)].

А какая разница по скольким первым байтам сортировать? Количество записей от этого не уменьшится же.

Проверяй.

$ ./sort_via_fs.sh input.txt output.txt
$ cat sort_via_fs.sh 
#!/bin/sh

if [ ! $# == 2 ]; then
  echo "Attention! Need 2 arguments."
  echo "Usage: $0 input.txt output.txt"
  exit
fi

file1=$1
file2=$2
tmp_dir=./tmp

mkdir $tmp_dir
awk '{system("touch '${tmp_dir}'/\""$0"\"")}' $file1
ls -1 $tmp_dir > $file2

1. Прочитать строки.
2. Создать файлы.
3. Сохранить отсортированный список файлов.

> O (n) операций чтения с небольшим множителем

Это как интересно?

Гнать не буду, я написал «вроде бы». Мне кажется, если применить принципы inplace_merge c O(n), то можно добиться такого результата, но не уверен. Это может оказаться не проверкой на 10 минут. Подумаю на досуге. Разумеется, в оперативке log, а то и его квадрат никуда не денутся.

Да, мне тоже только что подумалось, что inplace просто перемещает проблему с диска в память. А вообще задачка экономически нецелесообразна после трех часов изучения, за немалой ценой часа программиста дешевле купить и смонтировать флешку USB 2.0 на 8 гигов. И дальше обычным merge.

Я думаю на собеседовании ожидают увидеть разумное решение, а не влоб.

Дешевое и сердитое.

ааа, смещение, понял

Сами строки перемещать в файле нереально

реально, если не надо при этом остальные записи сдвигать.

А какая разница по скольким первым байтам сортировать?

размер индекса

Так-то да :)

а с чего бы это не надо? в задаче длина строки неизвестна.

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

Такой детсад был ну нас на первом курсе универа

Не понял. Всего индексов будет столько, сколько записей же. Размер одного индекса зависит от схемы позиционирования в данных (тут смещения внутри 4г). 80млн записей — 80млн индексов по 4 байта — 320Мб как ни крути.

задачка экономически нецелесообразна

Задача [для Яндекса] экономически очень целесообразна: «Найти программиста, который может оценивать и решать (желательно сторонними средствами), подобные проблемы.» )))

Думаю, после обсуждения вариантов решения этой задачи на собеседовании Яндекса, соискатель не будет писать 3 часа код. Либо собеседование продолжится другим вопросом, либо «мы очень ценим опыт общения с вами и обязательно свяжемся!».

если ты сортируешь строки только по первым n символам то есть шанс что файл будет отсортирован не до конца. Но для того чтобы досортировать его достаточно просто менять местами соседние строки без изменения смещения остальных.

Вообще реально, так как обычная практика для подобных файлов - делать столбцы fixed length. Это можно уточнить, можно ли добавить такое ограничение. А вот тогда можно использовать memory mapped files чтобы не дергать диск больше чем надо

ссылки на статью, то что я нашёл http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1...

насколько я понял не будет нормально работать с данными переменной длины или требует working-zone, это впрочем не большая проблема, но это не обычный merge sort и его придется аккуратно писать, о чем я с самого начала писал, для эффективного решениея, тут нужно знать более подробные условия.

Твой подход интересен, понятен и, в принципе, не плох. Но если в файле все записи (или большая их часть) будет начинаться с одной последовательности, ты в пролёте.

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

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

чего? У тебя строки разной длины, для того, чтобы поменять дальнюю с передней тебе нужно, чтобы дальняя была по размеру меньше. В любом случае это ненужное извращение и так можно делать только на стадии объединения, т.к. там есть приятные инварианты позволяющие выделить working-zone.

Думаю, после обсуждения вариантов решения этой задачи на собеседовании Яндекса, соискатель не будет писать 3 часа код

Нет, именно написать работающий код. За 3 часа. Они ноут дают для этой задачи. С шindows(!), кстати :D

если в файле все записи (или большая их часть) будет начинаться с одной последовательности, ты в пролёте.

Если у них одинаковый префикс то его можно отсечь.

А вообще, не видя датасета и для «общего случая» оптимально не сделаешь. Поэтому сначала анализируем входные данные, а потом алгоритм. Этим и плоха эта задача что нет исходных данных.

PS я как-то для request tracker (софтина такая тикетов) обрезал индекс с 255 (если не путаю, какая там дефолтная глубина индекса у мускля?) до 6 символов. Скорость на базе в пару сотен метров видимо не упала, зато операции типа перестроения индекса итп кардинально ускорились и индекс сильно ужался.

Нет, именно написать работающий код. За 3 часа. Они ноут дают для этой задачи. С шindows(!), кстати :D

Наверное, это не ранняя стадия собеседования. На ранней слишком нерационально, там отсев приличный.

А у тебя знакомый ходил туда?

надо было приходить со своим ноутбуком...

1). если можно выделить ещё 4GB, то все просто проходим по всем недосортированным спискам - находим минимальный элемент, обновляем сдвиг в этом списке, а элемент кладем в новый файл. Можно проходить все списки сразу, в итоге будет O(N) действий.

2). если нельзя, то нужно каким либо образом решать все in-place, в этом случае

а). нужно объединять, так чтобы (a <> b) образовывали сбалансированное дерево, в предыдущем случае это не важно и можно не усложнять себе задачу.

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

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

Я парни вообще не могу допереть как частичное сравнение на диапазонах может спасти от разбросанных по разным концам файла значений. Ну и про функцию сравнения тоже ничего не сказано. Лексикографическая как минимум может айдишники неправильно расставить.

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

при частичной сортировки неотсортированные данные идут подряд, поэтому их можно менять местами.

так можно делать только на стадии объединения

при таком подходе нужно дополнительное место на внешнем носителе. С учётом того что IO очень тормозное я считаю что если можно избежать лишнего io то лучше это сделать.

> если в файле все записи (или большая их часть) будет начинаться с одной последовательности, ты в пролёте.

Если у них одинаковый префикс то его можно отсечь.

или большая их часть

У части файлов? Если в исходных данных есть разные наборы с одинаковыми префиксами разной длины? Запутаешься в эвристиках, 146%. Ты и алгоритм предварительного анализа не сможешь внятно описать, это будет выглядеть как куча костылей.

Ты далее пишешь, что для максимальной оптимизации нужно знать данные, и т.п. Это справедливо. Например, если все строки полностью одинаковые, и мы это знаем заранее можно достичь великолепных результатов.

Но нужно универсальное решение, которое будет работать достаточно быстро (не O(n^2) чтений), и будет достаточно элегантным и простым.

было:
[XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX]
сортировали кусками индексы O((N/M * log(N/M))*M).
[XXXXXX][YYYYYY][ZZZZZZ][KKKKKKK][LLLLL]
потом отсортировали данные (т.к. размер каждого куска <память/2)
теперь объединяем данные: или тупо слияние большого кол-ва
списков (требует вн-память)
или по 2:
[XYXYXYXYXYXYXY][ZKZKZKZKZKZKZKKZ][LLLLL]
[XYZKXYZKXYZKXYZKXYZKXYZKXYZKXYZK][LLLLL]
...

по последнему возникает вопрос, как это делать in-place, уважаемый анонимус, говорит, что это тривиально, я вот не уверен.

при частичной сортировки неотсортированные данные идут подряд, поэтому их можно менять местами.

то что ты предлагаешь очень сильно напоминает пузырек, есть какие-нибудь обоснования, что оно будет быстрее, чем O(N^2)?

Но нужно универсальное решение

Универсальное это, например, взять тачку помощнее и sort infile -o outfile .

будет достаточно элегантным и простым.

Чем оптимальнее код тем он более уродлив. Можно вообще дойти до того что поместить первые 8 символов в 64-битный int и сравнивать строки одной операцией сравнения...

есть какие-нибудь обоснования, что оно будет быстрее, чем O(N^2)?

да, надо найти такой n при котором 99.99% строк будет уникально идентифицироваться по этому n. Если n=10 то у нас 256^10 уникальных комбинаций. Дальше, если данные распределены равномерно, можно предположить сколько строк влезет туда с учётом парадокса дней рождения...

Можно вообще дойти до того что поместить первые 8 символов в 64-битный int

Не стоит, strncmp использует SSE3. Проблема именно в сложности O(N) алгоритма и памяти, а также в 3х часах на реализацию хотя бы прототипа %)