«Внешние» сортировки: что это, зачем это и как это реализовать?
Приветствую всех читателей!
Хочу сразу извиниться за возможные косяки в статье, на платформе публикуюсь впервые. Если вкратце о себе: я начинающий .NET backend разработчик. И вот в процессе своего обучения (2 курс университета) я столкнулся со внешними сортировками. Было понимание теории, а также была лень реализовывать самому.
Но после около получаса поиска информации по интернету не нашёл почти ничего (буквально пара видео на YouTube, не больше). Поэтому, хочу поделиться своими реализациями алгоритмов, а также поведать о внешних сортировках для тех, кто о подобном не слышал.
Ну-с, приступим!
Немного теории
Что вообще значит «внешняя» сортировка? Объясню: это сортировка, работающая не с данными в оперативной памяти, а с информацией, хранящейся в файлах на жёстком диске. Применяется, как правило, для больших (даже ОЧЕНЬ больших) объёмов данных. Например, сортировка таблиц по определённому столбцу.
В этой статье будут представлены реализации трёх методов внешней сортировки: прямой, естественный и многонитевой (многопутевой). Все они, по сути своей, представляют сортировку слиянием (MergeSort). Только вместо разбиения на подмассивы мы будем разбивать данные на подфайлы.
1. Прямой метод
Предположим, что имеется последовательный файл А, состоящий из записей а1, а2, … , an,
где n — кол-во записей. Для сортировки нам понадобятся два вспомогательных файла (далее — подфайлы) B и C, кол-во записей в каждом из них будет n / 2.
Последовательность шагов алгоритма:
Разделить имеющиеся элементы между подфайлами, поочерёдно записывая в них строки (нечётные по номеру — в файл B, чётные — в файл C), и осуществить их слияние обратно в исходный файл, получив отсортированные цепочки длиной 2 (кроме, быть может, одного элемента, которому пары не досталось).
Разбить имеющиеся отсортированные цепочки на пары, и осуществить слияние цепочек каждой пары.
Если число отсортированных цепочек больше 1, то перейти к шагу 2.
Что же, приступим к реализации!
Для начала объявим класс, в котором и будет находиться наш алгоритм
public class DirectOuterSort
{
//Сюда будет сохраняться строка с заголовками таблицы
private string? _headers;
//поле _iterations указывает, сколько элементов в одной отсортированной цепочке
//на данный момент.
//поле _segments показывает, сколько отсортированных цепочек у нас есть в обоих
//файлах в сумме
private long _iterations, _segments;
//здесь в нужном порядке будут храниться типы данных каждого столбца
//(понадобится для корректного сравения элементов)
private readonly Type[] _typesOfTableColumns
= { typeof(int), typeof(string), typeof(DateTime) };
//Индекс выбранного поля, по которому будем сортировать
private readonly int _chosenField;
public DirectOuterSort(int chosenField)
{
_chosenField = chosenField;
_iterations = 1;
}
}Начало положено: создали класс, объявили нужные поля. Теперь добавим метод разбиения записей на подфайлы.
private void SplitToFiles()
{
_segments = 1;
using var fileA = new StreamReader("A.csv");
_headers = fileA.ReadLine()!;
using var fileB = new StreamWriter("B.csv");
using var fileC = new StreamWriter("C.csv");
//В этой переменной будет храниться очередная считанная из исходного файла запись
string? currentRecord = fileA.ReadLine();
bool flag = true;
int counter = 0;
//цикл прекратится, когда мы дойдём до конца исходного файла
while (currentRecord is not null)
{
//дошли до конца цепочки, переключаемся на запись новой
if (counter == _iterations)
{
counter = 0;
flag = !flag;
_segments++;
}
if (flag)
{
//Запись отправляется в подфайл В
fileB.WriteLine(currentRecord);
}
else
{
//Запись отправляется в подфайл С
fileC.WriteLine(currentRecord);
}
//считываем следующую запись
currentRecord = fileA.ReadLine();
counter++;
}
}Теперь переходим к следующему шагу: напишем метод, который будет сливать пары отсортированных цепочек из подфайлов в новые отсортированные цепочки в исходном файле.
private void MergePairs()
{
using var writerA = new StreamWriter("A.csv");
using var readerB = new StreamReader("B.csv");
using var readerC = new StreamReader("C.csv");
//Не забываем вернуть заголовки таблицы на своё место, в начало исходного файла
writerA.WriteLine(_headers);
string? elementB = readerB.ReadLine();
string? elementC = readerC.ReadLine();
int counterB = 0;
int counterC = 0;
//Итерации будут происходить, когда
while (elementB is not null || elementC is not null)
{
string? currentRecord;
bool flag = false;
//Обрабатываем случай, когда закончился весь файл B, или цепочка из данной пары
//в нём
if (elementB is null || counterB == _iterations)
{
currentRecord = elementC;
}
else if (elementC is null || counterC == _iterations) //аналогично предыдущему блоку if, но для подфайла С
{
currentRecord = elementB;
flag = true;
}
else
{
//Если оба подфайла ещё не закончились, то сравниваем записи по нужному полю
if (CompareElements(elementB, elementC))
{
//Если запись из файла В оказалась меньше
currentRecord = elementB;
flag = true;
}
else
{
//Если запись из файла С оказалась меньше
currentRecord = elementC;
}
}
//Записываем в исходный файл выбранную нами запись
writerA.WriteLine(currentRecord);
if (flag)
{
elementB = readerB.ReadLine();
counterB++;
}
else
{
elementC = readerC.ReadLine();
counterC++;
}
if (counterB != _iterations || counterC != _iterations)
{
continue;
}
//Если серии в обоих файлах закончились, то обнуляем соответствующие счётчики
counterC = 0;
counterB = 0;
}
_iterations *= 2;
}
//Метод сравнения записей по выбранному полю, учитывая его тип данных
//Вернёт true, если element1 меньше element2
private bool CompareElements(string? element1, string? element2)
{
if (_typesOfTableColumns[_chosenField].IsEquivalentTo(typeof(int)))
{
return int.Parse(element1!.Split(';')[_chosenField])
.CompareTo(int.Parse(element2!.Split(';')[_chosenField])) < 0;
}
if (_typesOfTableColumns[_chosenField].IsEquivalentTo(typeof(DateTime)))
{
return DateTime.Parse(element1!.Split(';')[_chosenField])
.CompareTo(DateTime.Parse(element2!.Split(';')[_chosenField])) < 0;
}
return string.Compare(element1!.Split(';')[_chosenField],
element2!.Split(';')[_chosenField],
StringComparison.Ordinal) < 0;
}И, наконец, объединим эти методы, чтобы завершить наш алгоритм сортировки.
public void Sort()
{
while (true)
{
//Разбиваем записи на подфайлы
SplitToFiles();
//Если после разделения цепочка осталась одна, значит, записи в файле отсортированы
if (_segments == 1)
{
break;
}
//Сливаем вместе цепочки из под файлов
MergePairs();
}
}С первым алгоритмом закончили. Из его особенностей выделю:
В основной памяти требуется расположить всего лишь две переменные — для очередных записей из файлов B и C (на самом деле чуть больше, но всяко лучше, чем хранить огромные таблицы с данными целиком в оперативной памяти).
Всего будет проведено log2(n) операций слияния и (log2(n) + 1) операций разбиения на подфайлы (последняя нужна, чтобы убедиться в отсортированности записей).
8 элементов — 3 слияния и 4 разбиения
16 элементов — 4 слияния и 5 разбиений
1024 элемента — 10 слияний и 11 разбиений
2. Естественный метод
При использовании метода прямого слияния не принимается во внимание то, что исходный файл может быть частично отсортированным, т.е. содержать серии.
Серия — отсортированная подпоследовательность записей.
Метод естественного слияния основан на распознавании серий при распределении и их использовании при следующем слиянии. Т. е. теперь при слиянии мы будем работать не с парами отсортированных цепочек, которые всегда имеют идентичную длину, а с парами серий, которые зачастую не будут одинаковы по длине.
Начнём с того же, с чего начинали в прошлый раз. С создания класса объявления нужных полей!
public class NaturalOuterSort
{
private string? _headers;
private readonly int _chosenField;
private readonly Type[] _columnOfTableTypes
= { typeof(int), typeof(string), typeof(DateTime) };
//В этом списке будут храниться длины всех серий в обоих подфайлах
private readonly List _series = new();
public NaturalOuterSort(int chosenField)
{
_chosenField = chosenField;
}
} Отличия от предыдущего алгоритма сразу бросаются в глаза:
Пропали поля _iterations и _segments, т.к. мы не можем заранее знать длины и кол-во серий.
Появилось поле _series, в котором будут лежать длины наших серий
Далее у нас по списку — метод разбиения записей на подфайлы.
private void SplitToFiles()
{
using var fileA = new StreamReader("A.csv");
_headers = fileA.ReadLine();
using var fileB = new StreamWriter("B.csv");
using var fileC = new StreamWriter("C.csv");
//считываем строку, которую будем записывать в подфайл, и следующую за ней, чтобы
//сравнить их и проверить, закончилась серия или нет
string? firstStr = fileA.ReadLine();
string? secondStr = fileA.ReadLine();
bool flag = true;
int counter = 0;
while (firstStr is not null)
{
//Доп. флаг нужен, чтобы при окончании серии не потерять последнюю запись в этой
//самой серии
bool tempFlag = flag;
if (secondStr is not null)
{
if (CompareElements(firstStr, secondStr))
{
counter++;
}
else
{
//Если серия прервалась, то записываем её длину в список и обнуляем счётчик
tempFlag = !tempFlag;
_series.Add(counter + 1);
counter = 0;
}
}
if (flag)
{
fileB.WriteLine(firstStr);
}
else
{
fileC.WriteLine(firstStr);
}
//движемся к следующей записи
firstStr = secondStr;
secondStr = fileA.ReadLine();
flag = tempFlag;
}
_series.Add(counter + 1);
}Записи разбиты по подфайлам, теперь настало время слить их воедино.
private void MergePairs()
{
using var writerA = new StreamWriter("A.csv");
using var readerB = new StreamReader("B.csv");
using var readerC = new StreamReader("C.csv");
//Не забываем про заголовки
writerA.WriteLine(_headers);
//Индекс, по которому находится очередная серия в подфайле B
int indexB = 0;
//Индекс, по которому находится очередная серия в подфайле С
int indexC = 1;
//Счётчики, чтобы случайно не выйти за пределы серии
int counterB = 0;
int counterC = 0;
string? elementB = readerB.ReadLine();
string? elementC = readerC.ReadLine();
//Цикл закончит выполнение только когда
while (elementB is not null || elementC is not null)
{
if (counterB == _series[indexB] && counterC == _series[indexC])
{
//Случай, когда мы дошли до конца серий в обоих подфайлах
counterB = 0;
counterC = 0;
indexB += 2;
indexC += 2;
continue;
}
if (indexB == _series.Count || counterB == _series[indexB])
{
//Случай, когда мы дошли до конца серии в подфайле B
writerA.WriteLine(elementC);
elementC = readerC.ReadLine();
counterC++;
continue;
}
if (indexC == _series.Count || counterC == _series[indexC])
{
//Случай, когда мы дошли до конца серии в подфайле C
writerA.WriteLine(elementB);
elementB = readerB.ReadLine();
counterB++;
continue;
}
//Сравниваем записи по заданному полю и вписывам в исходный файл меньшую из них
if (CompareElements(elementB, elementC))
{
writerA.WriteLine(elementB);
elementB = readerB.ReadLine();
counterB++;
}
else
{
writerA.WriteLine(elementC);
elementC = readerC.ReadLine();
counterC++;
}
}
}
//Метод для сравнения записей по заданному полю с учётом его типа данных
private bool CompareElements(string? element1, string? element2)
{
if (_columnOfTableTypes[_chosenField].IsEquivalentTo(typeof(int)))
{
return int.Parse(element1!.Split(';')[_chosenField])
.CompareTo(int.Parse(element2!.Split(';')[_chosenField])) <= 0;
}
if (_columnOfTableTypes[_chosenField].IsEquivalentTo(typeof(DateTime)))
{
return DateTime.Parse(element1!.Split(';')[_chosenField])
.CompareTo(DateTime.Parse(element2!.Split(';')[_chosenField])) <= 0;
}
return string.Compare(element1!.Split(';')[_chosenField],
element2!.Split(';')[_chosenField],
StringComparison.Ordinal) <= 0;
}Ну и наконец, объединяем эти методы воедино, чтобы получить готовую сортировку.
public void Sort()
{
while (true)
{
_series.Clear();
SplitToFiles();
//Если у нас осталась всего одна серия, значит, записи в файле отсортированы
if (_series.Count == 1)
{
break;
}
MergePairs();
}
}Из особенностей естественного слияния:
Число разбиений/слияний файлов при использовании этого метода будет не хуже, чем при применении метода прямого слияния, а в среднем — даже лучше.
С другой стороны, увеличивается кол-во сравнений за счёт тех, которые требуются для распознания концов серий. Кроме того, поскольку длина серий не фиксирована, то максимальный размер файлов B и C может быть близок к размеру исходного файла A.
3. Многонитевой (многопутевой) метод
Процесс многопутевого слияния почти как две капли воды схож с процессом прямого слияния. За одним лишь тем исключением, что мы будем использовать больше двух подфайлов. В своём примере я продемонстрирую трёхпутевой метод (значит, кол-во подфайлов будет равно трём).
Уже по традиции, начнём с объявления класса и полей.
public class MultiThreadOuterSort
{
private string? _headers;
private readonly int _chosenField;
private long _iterations, _segments;
private readonly Type[] _columnOfTableTypes =
{ typeof(int), typeof(string), typeof(DateTime) };
public MultiThreadOuterSort(int chosenField)
{
_chosenField = chosenField;
_iterations = 1;
}
}Здесь мы видим уже знакомые нам поля, и значение каждого из них нисколько не изменилось. Переходим к следующему шагу — к разбиению на файлы.
private void SplitToFiles()
{
_segments = 1;
using var fileA = new StreamReader("A.csv");
_headers = fileA.ReadLine();
using var fileB = new StreamWriter("B.csv");
using var fileC = new StreamWriter("C.csv");
using var fileD = new StreamWriter("D.csv");
string? currentRecord = fileA.ReadLine();
//переменная flag поменяла свой тип с bool на int, т.к. теперь нам нужно больше
//двух значений
int flag = 0;
int counter = 0;
while (currentRecord is not null)
{
if (counter == _iterations)
{
//Случай, когда мы дошли до конца цепочки
counter = 0;
flag = GetNextFileIndexToWrite(flag);
_segments++;
}
switch (flag)
{
case 0:
fileB.WriteLine(currentRecord);
break;
case 1:
fileC.WriteLine(currentRecord);
break;
case 2:
fileD.WriteLine(currentRecord);
break;
}
currentRecord = fileA.ReadLine();
counter++;
}
}
//Метод получения следующего индекса файла для записи (B = 0, C = 1, D = 2)
private static int GetNextFileIndexToWrite(int currentIndex)
=> currentIndex switch
{
0 => 1,
1 => 2,
2 => 0,
_ => throw new Exception("Что-то вышло из под контроля. Будем разбираться")
};Теперь метод для слияния записей из трёх файлов. Он у меня получился довольно громоздким (из-за проверок исключительных ситуаций, например, при конце серии в одном или двух из подфайлов). Поэтому буду рад предложениям по улучшению читаемости кода и оптимизации сортировок в комментариях.
private void MergeFiles()
{
using var writerA = new StreamWriter("A.csv");
using var readerB = new StreamReader("B.csv");
using var readerC = new StreamReader("C.csv");
using var readerD = new StreamReader("D.csv");
writerA.WriteLine(_headers);
string? elementB = readerB.ReadLine();
string? elementC = readerC.ReadLine();
string? elementD = readerD.ReadLine();
int counterB = 0;
int counterC = 0;
int counterD = 0;
while (elementB is not null || elementC is not null || elementD is not null)
{
string? currentRecord;
int flag;
if (CheckElement(elementB, counterB) && !CheckElement(elementC, counterC) && !CheckElement(elementD, counterD))
{
//Случай, когда цепочка закончилась только в файле B
(currentRecord, flag) = GetMinOfElements(
elementC,
elementD) switch
{
0 => (elementC, 1),
1 => (elementD, 2)
};
}
else if (CheckElement(elementC, counterC) && !CheckElement(elementB, counterB) && !CheckElement(elementD, counterD))
{
//Случай, когда цепочка закончилась только в файле С
(currentRecord, flag) = GetMinOfElements(
elementB,
elementD) switch
{
0 => (elementB, 0),
1 => (elementD, 2)
};
}
else if (CheckElement(elementD, counterD) && !CheckElement(elementB, counterB) && !CheckElement(elementC, counterC))
{
//Случай, когда цепочка закончилась только в файле D
(currentRecord, flag) = GetMinOfElements(
elementB,
elementC) switch
{
0 => (elementB, 0),
1 => (elementC, 1)
};
}
else if (counterB == _iterations && counterC == _iterations)
{
//Случай, когда цепочки закончились в файлах В и С
currentRecord = elementD;
flag = 2;
}
else if (counterB == _iterations && counterD == _iterations)
{
//Случай, когда цепочки закончились в файлах В и D
currentRecord = elementC;
flag = 1;
}
else if (counterC == _iterations && counterD == _iterations)
{
//Случай, когда цепочки закончились в файлах C и D
currentRecord = elementB;
flag = 0;
}
else
{
//Случай, когда не закончилась ни одна из 3 цепочек
(currentRecord, flag) = GetMinOfElements(
elementB,
elementC,
elementD) switch
{
0 => (elementB, 0),
1 => (elementC, 1),
2 => (elementD, 2)
};
}
switch (flag)
{
case 0:
writerA.WriteLine(currentRecord);
elementB = readerB.ReadLine();
counterB++;
break;
case 1:
writerA.WriteLine(currentRecord);
elementC = readerC.ReadLine();
counterC++;
break;
case 2:
writerA.WriteLine(currentRecord);
elementD = readerD.ReadLine();
counterD++;
break;
}
if (counterB != _iterations || counterC != _iterations || counterD != _iterations)
{
continue;
}
//Обнуляем все 3 счётчика, если достигли конца всех цепочек во всех файлах
counterC = 0;
counterB = 0;
counterD = 0;
}
_iterations *= 3;
}
//Ниже дан ряд методов для поиска минимального из 3 элементов (с учётом того),
//что некоторые из них могут отсутствовать
private int GetMinOfElements(params string?[] elements)
{
if (elements.Contains(null))
{
switch (elements.Length)
{
case 2:
return elements[0] is null ? 1 : 0;
case 3 when elements[0] is null && elements[1] is null:
return 2;
case 3 when elements[0] is null && elements[2] is null:
return 1;
case 3 when elements[1] is null && elements[2] is null:
return 0;
}
}
if (_columnOfTableTypes[_chosenField].IsEquivalentTo(typeof(int)))
{
return GetMinInt(elements
.Select(s => s is null ? int.MaxValue : int.Parse(s.Split(';')[_chosenField]))
.ToArray());
}
if (_columnOfTableTypes[_chosenField].IsEquivalentTo(typeof(DateTime)))
{
return GetMinDateTime(elements
.Select(s => s is null ? DateTime.MaxValue: DateTime.Parse(s.Split(';')[_chosenField]))
.ToArray());
}
return GetMinString(elements!);
}
private int GetMinString(IReadOnlyList elements)
{
if (elements.Count == 1)
{
return 0;
}
var min = elements[0].Split(';')[_chosenField];
var minIndex = 0;
for (var i = 1; i < elements.Count; i++)
{
if (string.Compare(elements[i].Split(';')[_chosenField], min, StringComparison.Ordinal) > 0)
{
continue;
}
min = elements[i].Split(';')[_chosenField];
minIndex = i;
}
return minIndex;
}
private static int GetMinInt(IReadOnlyList elements)
{
if (elements.Count == 1)
{
return 0;
}
var min = elements[0];
var minIndex = 0;
for (var i = 1; i < elements.Count; i++)
{
if (elements[i] > min)
{
continue;
}
min = elements[i];
minIndex = i;
}
return minIndex;
}
private static int GetMinDateTime(IReadOnlyList elements)
{
if (elements.Count == 1)
{
return 0;
}
var min = elements[0];
var minIndex = 0;
for (var i = 1; i < elements.Count; i++)
{
if (DateTime.Compare(elements[i], min) > 0)
{
continue;
}
min = elements[i];
minIndex = i;
}
return minIndex;
}
private bool CheckElement(string? element, int counter)
=> element is null || counter == _iterations; И, наконец, финальный штрих. Соединяем методы вместе уже привычным нам способом.
public void Sort()
{
while (true)
{
SplitToFiles();
if (_segments == 1)
{
break;
}
MergeFiles();
}
}По мере увеличения длины уже отсортированных цепочек вспомогательные файлы с большими номерами (начиная с последнего) перестают использоваться, т.к. им «не достаётся» ни одной цепочки.
Кол-во проходов алгоритма будет равным loga (n), где, а — кол-во подфайлов, n — кол-во записей в исходном файле.
Улучшение эффективности внешней сортировки
Думаю, это прозвучит логично, если я скажу, что чем больше в исходном файле серий — то тем больше проходов понадобится алгоритму, дабы отсортировать его.
Следовательно, в процессе оптимизации мы можем уменьшить кол-во серий в исходном файле. Как этого добиться? Разбить этот файл на маленькие части (так, чтобы каждая из них целиком помещалась в Оперативной Памяти) и отсортировать каждую из них методом внутренней сортировки.
Заключение
Как и всё в этом мире, мой скромный рассказ подходит к концу. Постарался сделать эту статью в том формате, в каком сам бы хотел её найти: краткие, но понятные объяснения, и развёрнуто показанные примеры кода в листингах.
Спасибо всем, что дошли до этого места. До следующих статей!
