Приветствую всех читателей!
Хочу сразу извиниться за возможные косяки в статье, на платформе публикуюсь впервые. Если вкратце о себе: я начинающий .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<int> _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<string> 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<int> 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<DateTime> 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 - кол-во записей в исходном файле.
Улучшение эффективности внешней сортировки
Думаю, это прозвучит логично, если я скажу, что чем больше в исходном файле серий - то тем больше проходов понадобится алгоритму, дабы отсортировать его.
Следовательно, в процессе оптимизации мы можем уменьшить кол-во серий в исходном файле. Как этого добиться? Разбить этот файл на маленькие части (так, чтобы каждая из них целиком помещалась в Оперативной Памяти) и отсортировать каждую из них методом внутренней сортировки.
Заключение
Как и всё в этом мире, мой скромный рассказ подходит к концу. Постарался сделать эту статью в том формате, в каком сам бы хотел её найти: краткие, но понятные объяснения, и развёрнуто показанные примеры кода в листингах.
Спасибо всем, что дошли до этого места. До следующих статей!
