Всем доброго времени суток!
Выполнял недавно тестовое задание, в котором требовалось выполнить сортировку файла, размером 4 Гб, используя всего 512 Мб оперативной памяти. Язык — Java, время выполнения задания (НЕ время работы алгоритма) — 4 часа. В файле строки из трех столбцов, второй столбец — дата и время в формате ISO, по нему нужно сортировать.
Я сделал следующим образом: начинаем считывать из файла строки в ArrayList, пока не забьем память примерно на 250 Мб, после чего массив сортируем алгоритмом Merge Sort (выбрал его, т.к. у него хорошее время выполнения и уже имел с ним дело), и отсортированный массив записываем во временный файл. Потом продолжаем считывать строки из исходного файла, сортируя и сохраняя по этому же принципу. После считывания всего исходного файла используем тот же алгоритм слияния для сборки одного выходного файла, сохраняя промежуточные результаты в, опять же, промежуточных отсортированных файлах.
По результату задания мне сказали, что алгоритм не оптимален. Есть идеи, как оптимизировать его, но только незначительно (например, написать более шуструю операцию сравнения двух подстрок или еще что-то в этом духе). Но никаких глобальных способов оптимизации так и не придумал.
У кого есть идеи — подскажите пожалуйста.
Заранее спасибо!
Я не специалист по сортировке, но если быстро перебрать исходный (первый) файл и сделать копию только из второго столбца и номера строки — больше данных влезет в память (это второй файл).
А по окончанию сортировки создать третий файл с результатами, выдергивая номера строк и з отсортированного второго файла, и забирая соответствующую строку из первого.
Читать сроку, запоминать ее смещение от начала файла (int32), длину строки (int32), а время перевести в timestamp (int32) = ~12 байт на запись (+ оверхед явовских контейнеров)
Сортировать все скопом по timestamp в один контейнер.
И бежать по индексу выкусывая из исходного файла сроки по смещению и длине, добавляя их в новый.
В 512 Мб влезет ~44 млн. срок. (без учета оверхеда контейнеров)
В 4-10 раз медленнее, чем линейное чтение. С 1 сата винчестера можно получить до 80 мегабайт в секунду линейного чтения или около 10 мегабайт в секунду рандомного чтения. Скорее всего сортировать всё сразу будет быстрее.
Просто сделайте в своём алгоритме использование quicksort или timsort для сортировки в памяти.
А какого рода строки в файле? Может, их можно хранить в памяти компактней. Например, дату/время можно точно уместить в один long, см. Date.getTime(). Может, и с остальными столбцами так можно?
А чем вас не устроили классические алгоритмы сортировки последовательностей (см. Д. Кнут, т. 3)? Вполне себе классический случай. Ключевые слова «однофазная»/«многофазная» «однопутевая», «двухпутевая», «турнирная» сортировка.
В качестве экзотики можно сделать вариант с комбинированной сортировкой (чтение блоков, частичная сортировка, смешивание, например как здесь). Но работать будет долго.
Если есть опасение, что одна строка не влезет в ограничение по памяти — стройте индекс и сортируйте его.
«чтение блоков» + «частичная сортировка» + «стройте индекс» + «сортируйте» +… = sqlite. Всё встроено, всё из коробки, работает оптимально. Не, я понимаю что задание тестовое и, наверное, надо показать что магёшь, но блин эту задачу перерешали уже стопицот раз.
Почему комбинированная сортировка будет работать долго? Она выглядит оптимальной и по времени (N*log(N)) и по числу обращений к диску (K^2, где K — число блоков). Какая из сортировок эффективнее?
Я не до конца понял ваше решение, но если тупо взять, пройтись по файлу и отобрать топ(512мб), записать в файл. Далее опять пройтись, отобрав топ(512мб) но уже начиная от нижней границы предыдущего топа. Всего 8 проходов.
Это конечно прекрасно, но для того, чтобы забить топ 512 Мб (если учесть, что в 512 Мб порядка 40 млн строк), надо будет 40 млн. раз пробежаться по всему файлу
Для того, чтобы забить топ 512 надо ОДИН раз пробежаться по всему файлу. Для 4гб всего 8 раз. Посчитай, какое количество операций ввода-вывода ты производишь в своем решение.
Мой способ сортировки полностью совпадает с принципом внешней сортировки:
«Идея большинства методов заключается в расчленении данных на ряд последовательностей помещающихся в оперативную память. Далее применяется один из методов внутренней сортировки, после чего последовательности сливаются…
Если же объём оперативной памяти мал, то можно разделить исходные данные на несколько последовательностей, после чего непосредственно использовать процедуру слияния.»
Все, сообразил. Но ведь все равно каждый набор из этих 40 млн. строк нужно будет сортировать. Последующее слияние будет быстрее, да. Хотя и не факт, что алгоритм будет быстрее в целом.
Но все равно проверю, спасибо!
Почему сортировать, не знаю как в яве, но в дотнете есть структура SortedList, она сохраняет элементы отсортированными. Можно какой-нибудь дерево использовать. Мы просто добавляем новые элементы и где-то храним значение минимального элемента, если считываемый элемент больше минимального, выкидываем минимальный, вставляем новый. Но в любом случае лучше использовать то, что уже было придумано до нас. Можно конечно и индекс заюзать, как рекомендовали выше, но мне кажется это решение натянутым ибо оно прокатывает на ленточке(если данных очень много он не влезет в память) + random access не самая быстрая операция.
1. Сортировать данные по индексу и второму столбцу
2. MergeSort использует в 2 раза больше оперативной памяти, нежели действительно требуется. В оперативной лучше сортировать по QuickSort (сортировка по умолчанию Arrays.sort()), тогда можно сортировать в 2 раза больше данных.
3. Так как дата представляется целым числом, можно использовать поразрядную сортировку (которая производит несколько сортировок подсчетом). Она еще быстрее. То есть, если дата представляется числом < 10^18, то сортировку можно произвести всего лишь тремя сортировками подсчетом (по разряду 10^6), которые выполняются за линейное время
4. ArrayList работает долго. Используйте массив
5. Не понял, как именно вы сливаете файлы. Их надо сливать по аналогии с MergeSort. То есть не последовательно, а также логарифмически
Спасибо за развернутый ответ!
1. Да, уже понял
2. Знаю, что сортировка слиянием использует доп. память. Но время выполнения у нее порядка N*log N, так же, как и у быстрой сортировки. А т.к. я с быстрой сортировкой раньше не сталкивался, решил ее не использовать. На выполнение задания было отведено 4 часа, боялся не успеть.
3. Спасибо за совет, посмотрю.
4. По доступу по случайному индексу скорость у них одинаковая. Лист использовал, т.к. у него есть операция добавления. Массив же требует сразу задания размера.
5. Да, именно так и сливаю, как и в Merge Sort
ещё нужно рассмотреть ситуацию, когда в файле находятся всего 3 строки, каждая размером по 650МБ. вы не сможете прочитать ни одну строку целиком, и нужно делать так, как говорит rowdyro
Простой
