Эффективный алгоритм сортировки файловых записей - PullRequest
Новая
       14

Эффективный алгоритм сортировки файловых записей

0 голосов
/ 22 февраля 2011

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

Образец записи:

000000000000dc01 t обработка ошибки 44

0000000dfa01a000 т веселья 44

Всего записей => 5000 Язык программирования c

Я хотел бы знать, какой алгоритм подходит для сортировки этого файла по адресу и каков эффективный способ чтения этих записей?

Ответы [ 3 ]

6 голосов
/ 22 февраля 2011

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

В первом проходе считайте блоки из N записей (гдеN определяется как количество записей, которые помещаются в память), сортирует их и записывает во временный файл.Когда этот этап завершен, у вас либо есть номер (назовите его M) временных файлов, в каждом из которых содержится различное количество сортируемых записей, либо у вас есть один временный файл, содержащий блоки отсортированных записей.

Второй проход - это M-way merge.

Некоторое время назад я написал статью о том, как сделать это с помощью текстового файла.См. Сортировка большого текстового файла .Это довольно просто расширить, чтобы он мог сортировать другие типы записей, которые вы определяете.

Для получения дополнительной информации см. Внешняя сортировка .

1 голос
/ 22 февраля 2011

Поскольку записи имеют различную длину, эффективный метод будет следующим:

  1. Чтение и анализ файла в массив указателей на записи
  2. Сортировка массива указателей
  3. Запишите результаты

Произвольный доступ к файлу будет медленным, так как переводы строки должны быть найдены, чтобы найти конкретную запись.

Если у вас действительно большой файл, адаптируйте егопроцесс для: 

for each n records
   read and parse
   sort
   write to temporary file

mergesort temporary files
0 голосов
/ 22 февраля 2011

На месте Быстрая сортировка - один из лучших общих алгоритмов сортировки. Возможна более быстрая сортировка (например, сортировка по группам), но она зависит от некоторых свойств сортируемых данных.

...