Сортировка большого количества строк одинаковой длины

Question

У меня очень большая последовательность строк.Длина каждой строки - 50. Каждая строка содержит только буквы английского алфавита.Каков наилучший (самый быстрый) способ сортировки этой последовательности?

Answer 1

Если бы мне пришлось это кодировать, я бы, вероятно, сделал бы один проход, который разделил бы входные данные на множество выходных файлов в зависимости от первой пары символов или около того;цель состоит в том, чтобы сделать каждый выходной файл достаточно маленьким, чтобы поместиться в основную память.Затем я открыл бы каждый файл по порядку, отсортировал его в памяти и добавил к выводу.Первый проход - O (n), второй - более или менее O (n log n), и вы должны выполнить дисковый ввод-вывод четыре раза для каждой записи.Возможно, можно было бы добиться большего успеха с помощью какого-то загадочного алгоритма, но, вероятно, ненамного, и это легко понять и кодировать.

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

В псевдокоде:

open input file (r)
for i in ['aa', 'ab', 'ac', ..., 'zz']:
    open output file[i] (w)
for record in input file:
    write record to output file[record[0:2]]
close all files
open main output file (w)
for i in ['aa', 'ab', 'ac', ..., 'zz']:
    open input file[i] (r)
    slurp whole file into memory
    close input file
    sort data
    append whole sorted file to main output file

РЕДАКТИРОВАТЬ: подождите, вы хотите сказать, что записи содержат только символы AB и C?Других писем нет?В этом случае вам, вероятно, придется разделить исходную подстроку длиннее 2. Разделение на первые 3 символа разделит ее на 27 файлов, каждый из которых имеет размер в среднем 370 МБ.

Answer 2

Поскольку 500 МБ - это не много данных, вы можете просто загрузить весь файл в память, отсортировать его и записать результат обратно на диск.

Я предполагаю, что содержимое файла выложено так:

ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX\r\n
ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX\r\n
    :
    :
ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX\r\n

Код:

// Load
var data = File.ReadAllBytes("file.txt");
var itemCount = data.Length / 52;
var indexes = new int[itemCount];
for (int i = 0; i < itemCount; i++)
{
    indexes[i] = i;
}

// Sort
Array.Sort<int>(indexes, (x, y) =>
{
    for (int i = 0; i < 50; i++)
    {
        if (data[x * 52 + i] > data[y * 52 + i]) return 1;
        if (data[x * 52 + i] < data[y * 52 + i]) return -1;
    }
    return 0;
});

// Store
using (var stream = new Stream("result.txt"))
{
    for (int i = 0; i < itemCount; i++)
    {
        stream.Write(data, indexes[i] * 52, 52);
    }
}

Answer 3

Алгоритм, который вы ищете, это, вероятно, сортировка слиянием

http://en.wikipedia.org/wiki/Merge_sort

и это

http://en.wikipedia.org/wiki/External_sorting

НО в вашем конкретномВ этом случае прочитайте это:

Нужен способ сортировки файла журнала объемом 100 ГБ по дате

Это может работать для вас!

Answer 4

Примерно так?

List<string> list = new List<string>();
/* fill the list */
list.Sort();

Метод Sort() имеет различные перегрузки, которые позволяют настроить способ сравнения строк.

EDIT О, под "большим" вы подразумеваете строки на 500 ГБ, тогда это, вероятно, не собирается сокращаться.

Answer 5

Быстрая сортировка (если используется правильно) может быть очень эффективной при сортировке строк.

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

Пример: Допустим, входное значение равно {"hello", "world", "house", "homly" }, а первый раздел находится вокруг клавиши "world"

Вы получаете: {"hello", "house", "homly"}, {"world"}

Если вы хотите перераспределить первый набор, вам не нужно сравнивать первый символ строк, поскольку вы уже знаете, что первый символ одинаков во всех них!

Как правило, длина общего префикса в наборе будет равна количеству выполнений разбиения для получения набора.

Если вам интересно погрузиться глубже, прочтите Быстрые алгоритмы сортировки и поиска строк