Алгоритм сортировки: большой текстовый файл со строками переменной длины (значения через запятую) - PullRequest
Новая
       28

Алгоритм сортировки: большой текстовый файл со строками переменной длины (значения через запятую)

6 голосов
/ 15 декабря 2010

Что такое хороший алгоритм для сортировки текстовых файлов, размер которых превышает доступную память (много десятков гигабайт) и содержит записи переменной длины?Все алгоритмы, которые я видел, предполагают, что 1) данные помещаются в память, или 2) записи имеют фиксированную длину.Но представьте себе большой CSV-файл, который я хотел отсортировать по полю «Дата рождения» (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"

Я знаю, что:

  1. Это будет выполняться на один компьютер (не распространяется).
  2. На компьютере, на котором я буду работать, будет несколько процессоров.
  3. Файлы, которые я буду сортировать, могут быть больше, чемфизическая память машины.
  4. Файл содержит строки переменной длины.Каждая строка будет состоять из фиксированного числа столбцов (значений, разделенных разделителями).Файл будет отсортирован по определенному полю (т.е. 4-му полю в файле).
  5. Идеальным решением , вероятно, было бы «использовать эту существующую утилиту сортировки», но яв поисках лучшего алгоритма .
  6. Я не ожидаю полностью закодированного рабочего ответа;что-то более похожее на «проверьте это, вот как это работает, или вот почему это хорошо работает для этой проблемы».Я просто не знаю, где искать ...
  7. Это не домашняя работа!

Спасибо!♥

Ответы [ 4 ]

3 голосов
/ 15 декабря 2010

Этот класс алгоритмов называется внешней сортировкой. Я бы начал с проверки записи в Википедии . Содержит некоторые обсуждения и указатели.

1 голос
/ 15 декабря 2010

Предложите следующие ресурсы:

Сортировка слиянием: http://en.wikipedia.org/wiki/Merge_sort

Полу численные алгоритмы, том 2, Искусство компьютерного программирования: Кнут: Аддисон Уэсли: ISBN 0-201-03822-6 (v.2)

0 голосов
/ 27 августа 2013

Не нужно сортировать.Чтение файла ALL.CSV и добавление каждой строки чтения в файл за день, например 19841231.CSV.Для каждого существующего дня с данными в числовом порядке прочитайте этот CSV-файл и добавьте эти строки в новый файл.Оптимизация возможна, например, путем обработки исходного файла более одного раза или путем записи дней, фактически происходящих в файле ALL.CSV.

Таким образом, строка, содержащая «1985/02/28», должна быть добавленафайл 19850228.CSV.Файл 19850228.CSV должен быть добавлен в NEW.CSV после того, как файл 19850227.CSV был добавлен в NEW.CSV.Числовой порядок позволяет избежать использования всех алгоритмов сортировки, хотя это может привести к повреждению файловой системы.

На самом деле файл ALL.CSV можно разбить на файл, например, за год.1984.CSV, 1985.CSV и т. Д.

0 голосов
/ 15 декабря 2010

Стандартный подход сортировки слиянием будет работать.Общая схема:

  1. Разделить файл на N частей примерно одинакового размера
  2. Сортировать каждую часть (в памяти, если она достаточно мала, в противном случае рекурсивно применить тот же алгоритм)
  3. Объединить отсортированные части
...