Какой хороший алгоритм для сортировки текстовых файлов, размер которых превышает доступную память (многие десятки гигабайт), и которые содержат переменную длину записи? Все алгоритмы, которые я видел, предполагают, что 1) данные умещаются в памяти или 2) записи имеют фиксированную длину. Но представьте себе большой CSV-файл, который я хотел отсортировать по полю "BirthDate" (4-е поле):
Id,UserId,Name,BirthDate
1,psmith,"Peter Smith","1984/01/01"
2,dmehta,"Divya Mehta","1985/11/23"
3,scohen,"Saul Cohen","1984/08/19"
...
99999999,swright,"Shaun Wright","1986/04/12"
100000000,amarkov,"Anya Markov","1984/10/31"
Я знаю, что:
- Это будет работать на одном компьютере (не распространяется).
- Машина, на которой я буду запускать это, будет иметь несколько процессоров.
- Файлы, которые я буду сортировать, могут быть больше, чем физическая память машины.
- Файл содержит строки переменной длины. Каждая строка будет состоять из фиксированного числа столбцов (значений, разделенных разделителями). Файл будет отсортирован по определенному полю (то есть по 4-му полю в файле).
- Идеальным решением , вероятно, было бы «использовать эту существующую утилиту сортировки», но я ищу лучший алгоритм .
- Я не жду полностью закодированного, рабочего ответа; что-то еще вроде «проверьте это, вот как это работает, или вот почему это хорошо работает для этой проблемы». Я просто не знаю, где искать ...
- Это не домашнее задание!
Спасибо! ♥
задан Sophie 15 December 2010 в 18:20
поделиться