Здравствуйте, D. Mon, Вы писали:
DM>Предлагаю продолжить на примере такой задачи:
DM>1. Есть большой текстовый файл A (несколько гигов, заведомо не помещается в память), нужно сделать текстовый файл A1, содержащий все строки из А, но отсортированные в алфавитном порядке. Ограничение по памяти — 256 МБ.
Доделал
demos/sort_lin до настоящей внешней сортировки. Использовал, кстати,
Generators 2Автор: remark
Дата: 28.05.08
— генераторы очень помогли в процессе.
Свойства получившейся программы: использует строго не более N Мб ОЗУ (по умолч. 128). Сливаются одновременно не более D (= 4) отсортированных файлов. Максимальный размер строки не более ((N << 19) / D). Ключем считается вся строка вместе с терминальным '\n', дубликаты строк отбрасываются.
Тесты:
Файл (исходники .cs) 50М, после сортировки 16М, N = 1: 6.53 sec; сортировка отсортированного 16М файла, N = 1: 4.21.
Те же файлы, N = 16: 3.29 и 1.64 сек.
Файл (.mp3) 2900M, после сортировки 2680М, N = 256: 17 mins; сортировка отсортированного 2680М файла, N = 256: 12 mins.
Файл (строки Фибоначчи случайной длины,
программа генерации) 1024М, после сортировки 884M, N = 128: 200 sec.