Re[2]: Мастер-класс по ФП
От: R.K. Украина  
Дата: 28.01.09 16:49
Оценка:
Здравствуйте, 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.
You aren't expected to absorb this
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.