LINUX.ORG.RU

Сортировка огромного текстового файла: реализовать алгоритм

 , ,


0

2

Добрый день, ЛОР!

Вопрос к знатокам всего, computer science в частности:

Как реализовать сортировку по алфавиту строк(линий) огромного (!!!) текстового файла, который не помещается целиком в виртуальную память?

Какие есть для этого алгоритмы? Если ли примеры реализации? Какие подводные камни? Кто сталкивался?

Спасибо!!!

merge sort на первый взгляд должен подойти

не сталкивался с таким

f1u77y ★★★ ()

1) сортировка слиянием должна подойти

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

sholom ()

в обыденной жизни строят внешние индексы (можно частичные) и дальше работают через них..

MKuznetsov ★★★★★ ()

чо, институт начался? или собеседовние? :)) мержсорт, да

anonymous ()
Ответ на: комментарий от sholom

прыгнуть на середину и пройти до конца текущей линии это все равно быстрее, чем искать линейно в файле массой овер 1 терабайт.

хотя хз зачем это может понадобиться. такой файл с таким количеством строк.

anonymous ()

помещается целиком в виртуальную память

Виртуальная память ограничена лишь разрядностью шины, т.е. для AMD64 48бит, что есть 256Тб. Но т.к. в вопросе нет указания архитектуры, то виртуальное адресное пространство не ограничено. Когда MMU перестанет находить нужные адреса в памяти, то начнется свапинг и дальше ты упрешся только в диск.

Ну а почитать, например, вот http://cseweb.ucsd.edu/~gmporter/papers/tritonsort-nsdi11.pdf У них radix sort внутри.

xpahos ★★★★★ ()

прям компутер ссаенс

пиши тег лаболаторная

rogerw ()
Ответ на: комментарий от rogerw

Вообще-то это компутер сайенс и есть.

строк(линий)

кекеке

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

anonymous ()

Выше правильно написали, по нормальному нужно индексы строить, и через них работать.
Без индексов:
https://en.wikipedia.org/wiki/Merge_sort
https://en.wikipedia.org/wiki/External_sorting
Т.е. идея в том, чтобы разбить файл на маленькие куски, сначала их отсортировать, а потом объеденить их по очереди.

Int64 ★★ ()
Последнее исправление: Int64 (всего исправлений: 2)

Залей его построчно в таблицу какой-нибудь SQL БД и там отсортируй-поиндексируй, как тебе нравится.

blexey ★★★★ ()
Ответ на: комментарий от anonymous

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

ТС хочет сдать сессию и присунуть какой-нибудь девочке. Инфа соточка.

A1 ()

попробуй начни со смены ника и авы

anonymous ()
Ответ на: комментарий от A1

А почему не мальчику? И вообще, я допускаю, что он просто никогда не сталкивался с данной проблемой, а тут появилась задача и её необходимо решить, и дело вовсе не в сессии.

anonymous ()

random sort подойдёт лучше, чем merge sort

anonymous ()

Как уже написали: делаешь любую сортировку для чанков, влезающих в память, потом сливаешь по два чанка в один, как в сортировке слиянием.

Deleted ()
Ответ на: комментарий от rogerw

Лицо часто ломают? Или это ты только в интернете такой дерзкий?

anonymous ()
Ответ на: комментарий от blexey

единственный нормальный ответ в треде. как грится, все уже украдено до нас..

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.