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

Если бы минут за 10, а за 3 часа, это же что-то очень крутое нужно, нет не справлюсь.

sudo cast procoder99

Сортировка слиянием:

Промежуточные сортированные файлы (<=512М) + merge

10 тысяч

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

Т.е. сортировать тупо как строки? Не по имени, серверу или дате?

1. «сжать»: имена повторяющиеся в список, собаку выкинуть, серверы закодировать IP или просто список в памяти держать, время в целое. Получится ок. 4 000 000 000/40=100млн. записей по 8байт. 2. блоками, через промежуточные файлы.

индекс? какая должна быть структура у индекса?

1. «сжать»

А в худшем могут не повторяться, что тогда?

Вектор (массив) указателей (смещений в файле со строками).

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

Думаю, три часа им хватит с лихвой. Детали алгоритма влезут в пару-тройку предложений.

Деревом кодировать

И как сортировать такой индекс? куеву тучу reads делать с произвольным доступом по входному файлу?

Про эффективность ничего не сказано: тогда тупо читаем n*log(n) раз файл в поисках очередной строки и пишем ее в выходной файл и ведем в памяти таблицу «использованных» строк из входного файла.

3 часа - время реализации алгоритма

по какому критерию надо сортировать-то?

Кстати, если дату перевести в unix timestamp,а id в int то датасет ужмётся в два раза.

Два чая мне за это.

по какому критерию надо сортировать-то?

Сорри, я хз. Это дословное описание задания. В принципе, как я понял, данные можно сортировать просто как строки.

втупую:

1. Проходим весь файл, ищем минимальную строку. Пишем в выходной файл. Читаем исходный снова, ищем строку, бОльшую предыдущей, но меньшую остальных. Пишем. Смыть, повторить до тех пор, пока размеры файлов в строках не сравняются.

2. Играемся со свопом и флагами mmap-a, mmap-им файл, сортируем хоть qsort-ом. За 3 часа, вероятно, отсортирует.

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

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

Файл содержит строки в кодировке UTF-8 средней длины 20 символов

Вообще гонево какое-то. Только дата занимает 20 символов. И критерий сортировки не указан и необходимая эффективность алгоритма.

Сейчас на любой предложенный алгоритм ТС будет вводить доп. ограничения.

Давай все параметры сразу, а то начнешь юлить.

втупую:

там 214млн записей, ты хоть представляешь кол-во проходов?

Trie чтоле? А много он будет занимать в памяти для случайных строк в ~20 символов?

опс, не 214млн, поменьше т.к. юникод может занимать более одного байта на символ...

Почему в два? время 18 => 2 байта. Целое 5 => 2 байта же

*случайных _неповторяющихся_ строк

Почему в два?

потому что ТС написал что длина строки 20символов в среднем, а индекс и timestamp занимают очень дофига... Ну да, из предложенных примеров этого не следует.

там 214млн записей, ты хоть представляешь кол-во проходов?

представляю. ТС о непосредственно требованиях ко времени исполнения алгоритма и недопустимости решений в лоб ничего не говорил.

Кстати, я надеюсь, ты не из яндекса щас нам пишешь?

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

Ну не 4 ГБ. К тому же части дерева можно хранить во временных файлах

Если можно создавать промежуточные файлы, то mergesort решает

3. Берем латинский алфавит/коды символов. Перебираем в цикле, проходами по файлу выбираем масивы строк с соответствующим началом, потом сортируем, пишем в выходной файл.

Лучше исходный файл читать один раз

Не, свое решение я потом кину по ссылке на гитхаб в тред.

4. Берем латинский алфавит/коды символов. Проходим этот самый один раз по исходному файлу, пишем строки в кучку соответствующих файлов. Потом читаем сии файлы, сортируем, пишем в выходной.

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

Только при ублюдочном критерии 20символов на строку в 4Гб файле и неизвестно можно ли создавать промежуточные файлы, 512Мб не хватит для ведения >200,000,000 индексов.

Ну да. Для ускорения можно писать не по первым буквам, а по первым буквам и длине. Тогда слияние ещё быстрее будет

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

спамер?
(база адрессов на 4 гига...)

512Мб не хватит для ведения >200,000,000 индексов.

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

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

В чём смысл сего действия? Это одноразовая операция? Зачем программу-то писать? Где 4-гиговый файл нужно скачать для проверки?

Вариант решения: Подключить дополнительный swap файл к имеющимся 512MB. Запустить

$ ./sort.sh input.txt output.txt
$ cat sort.sh 
#!/bin/sh
sort $1 > $2

сколько памяти на винче можно использовать?

грубо говоря:

1). разбиение на блоки <256Mb (информация об отступах в отдельный файл)

на выходе: файл с информацией об оступах

2). для каждого блока отступы сортировать через qsort потом в группироваь в отдельном блоке памяти и обратно в файл

на выходе: частично сортированный файл

3). мерже сортом объединять частично сортированные блоки по 2. тут в зависимости от ответа на 1 вопрос могут быть разные подходы.

P.S. жаль не выходной можно было бы поиграться.

сначала решение в лоб, пока считается - нормальное пишешь :)

Я бы так сделал: время в time_t, id в short(?) int, имя @-сервера в словарь; наверное short-ключа хватит. При необходимости и имя юзера можно неплохо захаффманить. Дальше максимальными блоками quick-sort и во временный файл, по пути запоминая границы. Потом слиянием с каждой границы в результат (заодно распаковав).

с учетом того, что это адреса почт и цифры, которые составляют самую нижнюю часть юникода-8, то >1-байтными случаями можно пренебречь.

так тут же будет сложность n^2, что при таком кол-ве записей, имхо, обречено очень долго считать...

да что уж там, сразу man sort, оно умеет выгружать промежуточные данные на диск.

Слияние лучше наверное так:
1. первый раз читаем с каждой границы элемент в массив/список, сортируем, запоминая какой откуда пришел
2. пишем в результат первый элемент массива
3. из его границы получаем следующий (если есть) и вставляем в сортированную позицию
4. повторяем п.2.

во-первых N log N, т.к. сортировка по умолчанию это вызов quicksort. ну у тебя есть 3 часа, пока пишешь нормальное :)

P.S. дерево индексы и т.п. тут нафиг не нужно, для начала нужно поделить и выбрать правильную стратегию объединения, (на это и так эти 3 часа уйдут), а всякие «красивости» приделывать потом.