Как эффективно и лаконично отсортировать файл из строк не вмещающихся в память?

Question

[mkone112]

На собесе попросили написать код, сортирующий файл размером 1tb, каждая строка - число размером 2гб. Ограничение памяти 500мб, время на решение ~10 минут.
Я не очень понимаю как такое решать, есть бы хотя бы несколько строк помещалось в память - я бы разбил файл на сортированные куски и слил бы их через merge sort. Учитывая что в память целиком не помещается даже одна строка - я бы итерировался по каждой по отдельности пока не наткнулся бы на разные разряды... Но все это обрывки идей которые никак не превращаются в реализованный алгоритм. Как может выглядеть алгоритм решающий задачу, который можно реализовать на собесе за отведенные 10 минут времени?

Comments

[mayton2019]

я бы разбил файл на сортированные куски и слил бы их через merge sort.

это - правильное решение. Так эта задача и решается. Учитывая что тут каждая строка больше памяти - то делаешь все операции на диске. Сравнение строк - сравнение файлов.

[mkone112]

mayton2019,

Учитывая что тут каждая строка больше памяти - то делаешь все операции на диске.

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

Сравнение строк - сравнение файлов.

Не понял.

[mayton2019]

mkone112, вот кусок задания

аждая строка - число размером 2гб. Ограничение памяти 500мб

здесь КМК неважно сколько там мегабайтов. Тот кто выдал задание хотел сказать что ожидает
streamable-подход к сортировке. Тоесть ничего в эти 500 мб вы не положите. Даже одна строка не влезет.
Поэтому вы и можете расчитывать только на поточные дисковые операции.

[Alexandroppolus]

Чисел (элементов сортируемого массива) всего около 500?

[Alexandroppolus]

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

[Everything_is_not_so_bad]

За 1 минуту если есть мысли как реализовывать, то пытаешься уложиться во время. А если их нет, то нужно идти на ухищрения. Допустим, утилита sort в Linux.

[mkone112]

Román Mirilaczvili, ответ - рабочий код на питоне.

Answer 1

[Adamos]

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

Comments

[mayton2019]

Это - частный случай. Он базируется на предположении что первые 64Кб будут полезны для сортировки.
Но они могут полностью совпадать у всех 100% строк.

[Adamos]

mayton2019, это как раз алгоритм, ищущий такие частные случаи до самого конца строки. Но постепенно - только в том случае, если это действительно нужно.

[Alexandroppolus]

mayton2019, в худшем случае придется прочитать весь файл, от этого никуда не уйти

[res2001]

Можно читать по 512 Кб каждого числа, в этом случае части всех чисел влезут в память. Для "автоматической" сортировки можно использовать двоичное дерево.

[mayton2019]

Adamos, надо подумать. Может быть у нас будет несколько алгоритмов.

Answer 2

[Сергей Соколов]

Отдельные мысли:
1 Tb / 2 Gb = 500 чисел, не много.

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

Merge Sort, да, хорош, потому что O(n log n)

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

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

И т.д. пока все равенства не разрешатся, или пока числа не кончатся )

Comments

[Adamos]

По байту с диска? По сектору хотя бы.

[Сергей Соколов]

Adamos, утрировал для иллюстрации )
500 мб оперативки позволяют более крупные блоки, конечно.

[Сергей Соколов]

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

В задаче нужно отобразить (map) длиннющие числа на 10-битные (0..512) в правильном порядке сортировки.

[Сергей Соколов]

mkone112
Что если эту «таблицу» из 500 чисел одинаковой длины читать вертикально — столбцами по килобайту.
Считали 500 первых Кб, отсортировали.
Далее надо считать по следующему Кб только у оставшихся в этом раунде равными.
Так до конца (до младших разрядов чисел) или пока не останется неоднозначностей.

В памяти одновременно не придётся держать тяжёлых данных.

[Adamos]

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

[Akina]

Adamos,

Только не по килобайту, а по сектору все-таки, чтобы зря не гонять диск.

Ну тут сработает буферизация и предчтение как ОС, так и самого диска и и его контроллера. Так что с учётом доступной памяти (полгектара) и количества сортируемых строк (полтыщи) блок чтения в зависимости от выбранного способа сортировки может быть 0.5 или 1 Мбайт.

[mayton2019]

Напоминает radix сорт.

Answer 3

[garbagecollected]

Если доступен bash

sort -g -S500M -o /path/to/output.txt /path/to/input.txt

Comments

[mkone112]

Вопрос о реализации алгоритма, а не поиске подходящей тулзы.

[garbagecollected]

mkone112, так у этой тулзы открытый исходный код. В чем проблемы то? Посоветовать генератор flowcharts чтоли?

[mkone112]

garbagecollected,

В чем проблемы то?

Слово "лаконично" в заголовке вопроса.

[garbagecollected]

mkone112, ну я уже не знаю чем вам помочь. Просто два факта: тулза sort была написана в 1988г. Последний коммит в нее внесен в 2010г. Поддержка этой утилиты осуществляется 100% всеми существующими ОС. За 34 года исходный код тулзы переё*ан вдоль и поперёк. И за последние 12 лет в идеально отлаженный алгоритм никто не вносил изменения, так как он работал без нареканий у сотней миллионов пользователей. Вы реально мне хотите сказать что вы найдёте алгоритм лучше, лаконичнее?

[Adamos]

garbagecollected, скорее всего, найдет. Потому что в утилите общего назначения, да еще на Сях прошлого века, как минимум будут заведомые "простыни" кода, куда более объемные и замороченные на деталях реализации, чем решение на современном Питоне, которого хотят от ТС.

[Everything_is_not_so_bad]

Adamos, это похоже на троллинг. Хотя, в любом случае, автора просят код на Питоне.

[mkone112]

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

[Everything_is_not_so_bad]

mkone112, если будет найдено решение по вопросу на Питоне, опубликуй, пожалуйста.

[garbagecollected]

На python это невозможно. Нужен ЯП с так называемым raw memory management, у которых за выделение памяти отвечает условные calloc, malloc, realloc и free, а не какой-нибудь там GarbageCollector. Такими языками являются, например, Си (без плюсов) и Rust, и может быть, какие-то другие, которые я не знаю.

[garbagecollected]

mkone112, все что от вас требовали написать на python за 10 минут:

import os

cmd = 'sort -g -S500M -o /path/to/output.txt /path/to/input.txt'

returned_value = os.system(cmd)

Вы просто провафлили задание