Всех приветствую.
Задание реализовать алгоритм внешней сортировки "прямое слияние" и применить его на файле размерностью 1 ГБ.
Алгоритм реализовал, работает, проверял на небольших объемах (10000 чисел, 50000 чисел и т.д.), работает недолго.
С момента запуска программы для сортировки уже того самого большого файла прошло 4 часа, программа все еще не завершила свою работу.
Помогите, пожалуйста, ускорить этот процесс (суть алгоритма нужно сохранить). Дело, скорее всего, в использовании оперативной памяти и буферизации.
Главный файл:
using System;
using System.Collections.Specialized;
using System.Diagnostics;
using System.IO;
namespace Algorithms_LR1
{
internal class Program
{
public static void Main(string[] args)
{
string filename = "data.bin";
// Generator(filename, 500);
LargeFileGeneration(filename);
Console.WriteLine("Before sort: ");
OutputData(filename);
DirectMerge dm = new DirectMerge(filename);
dm.Sort();
Console.WriteLine("\nAfter sort: ");
OutputData(filename);
}
public static void LargeFileGeneration(string file)
{
BinaryWriter bw = new BinaryWriter(File.Create(file));
Random rnd = new Random();
for (int i = 0; i < 256000000; i++)
{
bw.Write(rnd.Next(-500, 500));
}
bw.Close();
}
public static void OutputData(string file) // вывод первых 100 чисел для проверки
{
BinaryReader br = new BinaryReader(File.Open(file, FileMode.Open));
for (int i = 0; i < 100; i++)
{
if (br.BaseStream.Position == br.BaseStream.Length)
{
break;
}
else
{
Console.Write($"{br.ReadInt32()} ");
}
}
br.Close();
}
public static void Generator(string file, int count) // для тестов
{
Random rnd = new Random();
BinaryWriter bw = new BinaryWriter(File.Create(file));
for (int i = 0; i < count; i++)
{
bw.Write(rnd.Next(-500, 500));
}
bw.Close();
}
}
}
Класс с сортировкой:
using System;
using System.CodeDom;
using System.Collections.Generic;
using System.IO;
using System.Runtime.CompilerServices;
namespace Algorithms_LR1
{
public class DirectMerge
{
public string FileInput { get; set; }
private ulong iterations, segments;
public DirectMerge(string input)
{
FileInput = input;
iterations = 1; // степень двойки, количество элементов в каждой последовательности
}
public void Sort()
{
while (true)
{
SplitToFiles();
// суть сортировки заключается в распределении на
// отсортированные последовательности.
// если после распределения на 2 вспомогательных файла
// выясняется, что последовательность одна, значит файл
// отсортирован, завершаем работу.
if (segments == 1)
{
break;
}
MergePairs();
}
}
private void SplitToFiles() // разделение на 2 вспом. файла
{
segments = 1;
BinaryReader br = new BinaryReader(File.Open(FileInput, FileMode.Open));
BinaryWriter writerA = new BinaryWriter(File.Create("a.bin"));
BinaryWriter writerB = new BinaryWriter(File.Create("b.bin"));
ulong counter = 0;
bool flag = true; // запись либо в 1-ый, либо во 2-ой файл
while (br.BaseStream.Position != br.BaseStream.Length)
{
// если достигли количества элементов в последовательности -
// меняем флаг для след. файла и обнуляем счетчик количества
if (counter == iterations)
{
flag = !flag;
counter = 0;
segments++;
}
if (flag)
{
writerA.Write(br.ReadInt32());
counter++;
}
else
{
writerB.Write(br.ReadInt32());
counter++;
}
}
br.Close();
writerA.Close();
writerB.Close();
}
private void MergePairs() // слияние отсорт. последовательностей обратно в файл
{
BinaryReader readerA = new BinaryReader(File.Open("a.bin", FileMode.Open));
BinaryReader readerB = new BinaryReader(File.Open("b.bin", FileMode.Open));
BinaryWriter bw = new BinaryWriter(File.Create(FileInput));
ulong counterA = iterations, counterB = iterations;
int elementA = 0, elementB = 0;
bool pickedA = false, pickedB = false, endA = false, endB = false;
while (true)
{
if (endA && endB)
{
break;
}
if (counterA == 0 && counterB == 0)
{
counterA = iterations;
counterB = iterations;
}
if (readerA.BaseStream.Position != readerA.BaseStream.Length)
{
if (counterA > 0)
{
if (!pickedA)
{
elementA = readerA.ReadInt32();
pickedA = true;
}
}
}
else
{
endA = true;
}
if (readerB.BaseStream.Position != readerB.BaseStream.Length)
{
if (counterB > 0)
{
if (!pickedB)
{
elementB = readerB.ReadInt32();
pickedB = true;
}
}
}
else
{
endB = true;
}
if (endA && endB && pickedA == false && pickedB == false)
{
break;
}
if (pickedA)
{
if (pickedB)
{
if (elementA < elementB)
{
bw.Write(elementA);
counterA--;
pickedA = false;
}
else
{
bw.Write(elementB);
counterB--;
pickedB = false;
}
}
else
{
bw.Write(elementA);
counterA--;
pickedA = false;
}
}
else if (pickedB)
{
bw.Write(elementB);
counterB--;
pickedB = false;
}
}
iterations *= 2; // увеличиваем размер серии в 2 раза
bw.Close();
readerA.Close();
readerB.Close();
}
}
}