1

Всех приветствую.
Задание реализовать алгоритм внешней сортировки "прямое слияние" и применить его на файле размерностью 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();
        }
        
    }
}
10
  • Дело, скорее всего, в использовании оперативной памяти и буферизации - Почему вы так решили? Сколько по времени выполняется сортировка на файле, скажем в 10 мегабайт? Если это сортировка строго внешняя, то наверное нельзя читать много данных в память, или можно, в чем заключается "внешность"? Вы в курсе, что у вас очень много одинаковых чисел в файле? Будет ли разница в скорости, если запустить сортировку, скажем 10 мегабайт для одинаковых, а потом для случайнах чисел? 4 часа прошло, откуда вы знаете, что алгоритм не завис на одном из этапов?
    – aepot
    Commented 5 сент. 2020 в 17:55
  • Вы использете .NET Framework, или Core? Можно ли использовать асинхронность и SIMD классы?
    – aepot
    Commented 5 сент. 2020 в 17:56
  • Вы хотя бы буфер использовали бы при чтении / записи в файл.
    – tym32167
    Commented 5 сент. 2020 в 18:15
  • У вас всего 1000 возможных значений, может имеет смысл использовать сортировку подсчетом?
    – tym32167
    Commented 5 сент. 2020 в 18:16
  • 1
    @danil0110 Проведите простой эксперимент. Возьмите тот же файл на 1Гб и простеньким кодом считывайте его и тут же записывайте в другой файл по одному числу, обязательно поставьте замер времени. А потом то же самое, но считывая блоками, например по 1024 Кб(и читать и писать) и сравните время. Можете попробовать разные размеры буферов, вот и увидите разницу) Commented 5 сент. 2020 в 20:03

1 ответ 1

8

Мне удалось разобраться с помощью профилирования процессора, что же самое медленное в вашем коде, а самое медленное вот это:

br.BaseStream.Position != br.BaseStream.Length

А если быть точнее, то именно получение .Length занимает кучу времени. Уверен, этому есть объяснение, и если залезть в исходники FileStream и лежащих под ним классов, это объяснение можно найти.

Далее, я немного изменил код, добавил всяких using взамен .Close(). Ну потому что так правильно.

Так же добавил буферизацию на запись, она хоть и не значительный, но дает прирост производительности тоже. Использовал буферы размером 65536 байт. Использовать буферы большего размера не рекомендую, а меньшего - попробуйте. Буферизация с таким же буфером на чтение прироста не дала, или я его не заметил, поэтому не стал использовать.

Итого, 10-мегабайтный файл у меня обрабатывался 8 секунд, 100-мегабайтный - 87 секунд, сколько будет обрабатываться гигабайт - проверьте сами, я предполагаю, что не более 20 минут.

internal class Program
{
    public static void Main(string[] args)
    {
        Stopwatch sw = new Stopwatch();
        sw.Start();
        string filename = "data.bin";
        // Generator(filename, 500);
        LargeFileGeneration(filename);
        Console.WriteLine("Before sort: ");
        OutputData(filename);
        DirectMerge dm = new DirectMerge(filename);
        dm.Sort();
        Console.WriteLine("After sort: ");
        OutputData(filename);
        sw.Stop();
        Console.WriteLine($"Elapsed: {(double)sw.ElapsedMilliseconds / 1000} seconds");
        Console.ReadKey();
    }

    public static void LargeFileGeneration(string file)
    {
        using (BinaryWriter bw = new BinaryWriter(File.Create(file, 65536)))
        {
            Random rnd = new Random();
            for (int i = 0; i < 256000000; i++)
            {
                bw.Write(rnd.Next(0, 256000000));
            }
        }
    }

    public static void OutputData(string file) // вывод первых 100 чисел для проверки
    {
        using (BinaryReader br = new BinaryReader(File.OpenRead(file)))
        {
            long length = br.BaseStream.Length;
            long position = 0;
            for (int i = 0; i < 100; i++)
            {
                if (position == length)
                {
                    break;
                }
                else
                {
                    Console.Write($"{br.ReadInt32()} ");
                    position += 4;
                }
            }
            Console.WriteLine();
        }
    }

    public static void Generator(string file, int count) // для тестов
    {
        using (BinaryWriter bw = new BinaryWriter(File.Create(file, 65536)))
        {
            Random rnd = new Random();
            for (int i = 0; i < count; i++)
            {
                bw.Write(rnd.Next(-500, 500));
            }
        }
    }
}
public class DirectMerge
{
    public string FileInput { get; set; }
    private long iterations, segments;

    public DirectMerge(string input)
    {
        FileInput = input;
        iterations = 1; // степень двойки, количество элементов в каждой последовательности
    }

    public void Sort()
    {
        while (true)
        {
            Console.Write(".");
            SplitToFiles();
            // суть сортировки заключается в распределении на
            // отсортированные последовательности.
            // если после распределения на 2 вспомогательных файла
            // выясняется, что последовательность одна, значит файл
            // отсортирован, завершаем работу.
            if (segments == 1)
            {
                break;
            }
            MergePairs();
        }
        Console.WriteLine();
    }

    private void SplitToFiles() // разделение на 2 вспом. файла
    {
        segments = 1;
        using (BinaryReader br = new BinaryReader(File.OpenRead(FileInput)))
        using (BinaryWriter writerA = new BinaryWriter(File.Create("a.bin", 65536)))
        using (BinaryWriter writerB = new BinaryWriter(File.Create("b.bin", 65536)))
        {
            long counter = 0;
            bool flag = true; // запись либо в 1-ый, либо во 2-ой файл

            long length = br.BaseStream.Length;
            long position = 0;
            while (position != length)
            {
                // если достигли количества элементов в последовательности -
                // меняем флаг для след. файла и обнуляем счетчик количества
                if (counter == iterations)
                {
                    flag = !flag;
                    counter = 0;
                    segments++;
                }

                int element = br.ReadInt32();
                position += 4;
                if (flag)
                {
                    writerA.Write(element);
                }
                else
                {
                    writerB.Write(element);
                }
                counter++;
            }
        }
    }

    private void MergePairs() // слияние отсорт. последовательностей обратно в файл
    {
        using (BinaryReader readerA = new BinaryReader(File.OpenRead("a.bin")))
        using (BinaryReader readerB = new BinaryReader(File.OpenRead("b.bin")))
        using (BinaryWriter bw = new BinaryWriter(File.Create(FileInput, 65536)))
        {
            long counterA = iterations, counterB = iterations;
            int elementA = 0, elementB = 0;
            bool pickedA = false, pickedB = false, endA = false, endB = false;
            long lengthA = readerA.BaseStream.Length;
            long lengthB = readerB.BaseStream.Length;
            long positionA = 0;
            long positionB = 0;
            while (!endA || !endB)
            {
                if (counterA == 0 && counterB == 0)
                {
                    counterA = iterations;
                    counterB = iterations;
                }

                if (positionA != lengthA)
                {
                    if (counterA > 0 && !pickedA)
                    {
                        elementA = readerA.ReadInt32();
                        positionA += 4;
                        pickedA = true;
                    }
                }
                else
                {
                    endA = true;
                }

                if (positionB != lengthB)
                {
                    if (counterB > 0 && !pickedB)
                    {
                        elementB = readerB.ReadInt32();
                        positionB += 4;
                        pickedB = true;
                    }
                }
                else
                {
                    endB = true;
                }

                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 раза
        }
    }
}

Вывод в консоль для 100 мегабайт

Before sort:
20127621 12590185 16433753 6247001 24131419 7347460 9169540 12736617 9742965 7124673 24310234 15757835 1636965 13314741 25575884 14185208 21490832 6338873 3442705 21657 18002116 15497946 12667595 18584567 6598540 20608226 20864423 8465434 14884840 1037725 9362099 19807226 13746855 8642553 5675197 8507707 15701872 1993417 17679036 9308352 12807474 23336948 4461486 1133486 3056311 18156949 7793164 23099844 24886250 5492144 2007366 21229978 12028658 23978768 4152 4629675 25522589 23449185 25248460 3523192 12083036 704106 23451776 8705240 23362573 4503008 2010980 18594412 7639543 17068176 24083335 19497414 14259837 19734353 12814183 20265167 11036459 11534109 15528256 14041591 12815061 23364579 9179183 9392696 24630358 13732121 7778568 15368087 8638400 1045522 8585117 17852687 2344956 14155844 22825315 12103367 25485171 21356246 3370912 24153303
..........................
After sort:
0 0 0 2 2 2 2 2 3 5 6 7 9 9 9 11 13 15 20 21 22 22 23 24 24 26 27 28 29 33 33 34 34 36 36 36 37 37 38 41 42 45 45 46 47 47 47 50 50 51 52 52 53 56 57 57 58 59 59 59 62 63 65 66 66 68 70 71 72 74 75 76 77 78 79 79 79 82 85 86 87 89 91 91 92 93 93 97 98 98 101 101 102 104 105 106 107 108 110 111
Elapsed: 87,471 seconds

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

Дополнительно потестировал для 100 мегабайт: пересобрал для x64 - 71 секунда, потом запустил релизную версию без отладчика, с установленной галочкой "optimize code" - 56 секунд.

Еще последняя итерация Split отрабатывает вхолостую, и segments можно вычислять вне цикла математически, а не счетчиком, затем прервать работу сплита, если сегмент ожидается один. Это тоже немного уменьшит общее время выполнения. Ну либо перенести break под Merge в главном методе и поменять условие на segments == 2.

7
  • 1
    Вы меня очень выручили, спасибо большое! 1 ГБ - 12 минут. Вопрос по поводу буфера, так как еще ни разу не использовал его: почему 65536 байт вы рекомендуете как максимальный?
    – danulqua
    Commented 6 сент. 2020 в 9:28
  • @danil0110 размер буфера рекомендуется равным степени двойки, затем объект в памяти считается большим и помещается в память для больших объектов, по-моему начиная с 85 килобайт, а следующая степень двойки - 131 килобайт. А зачем все это - потому что сборщику мусора будет проще работать, такая легкая оптимизация, подстраиваясь под особенности работы сборщика. Почему кратным двойке - я везде где можно использую ArrayPool вместо создания буферных массивов через new, для меня использовать кратные массивы - привычка. Ну и большой буфер - не всегда полезно в плане производительности.
    – aepot
    Commented 6 сент. 2020 в 9:42
  • @danil0110 кстати, отсутствие настройки буфера не значит отсутвие буфера вообще, просто если не указывать, размер буфера будет по умолчанию. Если честно, я не помню, какой там по умолчанию, но не большой. Вы можете убрать настройку буфера, и увидите, что будет если и медленнее работать, то совсем незначительно.
    – aepot
    Commented 6 сент. 2020 в 9:51
  • 1
    @danil0110 немного оптимизировал цикл в Merge методе, должно стать чуть быстрее.
    – aepot
    Commented 6 сент. 2020 в 10:24
  • 1
    Не вижу проблем с LOH, но я вам просто на слово поверю. Просто когда я генерил файлы по 16-32 гига и сортировал, то маленький буфер мне дал минимальную производительность, потому я просто просто делал буфер от 1 до 10 мегабайт, но и писал я в 256 файлов одновременно, хотя возможно это было больше с фрагментацией связано.
    – tym32167
    Commented 7 сент. 2020 в 10:45

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.