9

Строки разной длины и из разных символов, т.е. вариант с сортировкой подсчетом, не катит. Сделал внешнюю сортировку слиянием. Разбиваю файл на куски по 100Мб, сортирую каждый, выполняю слияние. Все это занимает у меня около 10 минут. Хотя рядом лежит чужой софт, который за 6 минут сортирует тот же объем и выполняет удаление дублей из него.

Прикладываю свой код.

public static class Sorting
{
    public static void ExternalMergeSort(string originalFile, string newFile)
    {
        //Разбить файл на части по 100 Мб
        string dir = SplitFile(originalFile);
        //Отсортировать каждую часть

        foreach (string file in Directory.GetFiles(dir, "*.txt", SearchOption.AllDirectories))
            InternalSort(file);

        //Многопоточный вариант - не хватает памяти
        //List<Task> tasks = new List<Task>();
        //foreach (string file in Directory.GetFiles(dir, "*.txt", SearchOption.AllDirectories))
        //{
        //    Task t = new Task(() => InternalSort(file));
        //    tasks.Add(t);
        //    t.Start();
        //}
        //Task.WaitAll(tasks.ToArray());
        //Объединить части
        MergeFilesInDirectory(dir);
    }


    /// <summary>
    /// Разбитие файла на куски укaзанного размера
    /// </summary>
    /// <param name="originalFile">Файл для разбития</param>
    /// <param name="maxFileSize">Максимальный размер части файла. Default = 100Mb</param>
    /// <returns>Путь к папке с частями файла</returns>
    private static string SplitFile(string originalFile, double maxFileSize= 1e+8)
    {
        TimeWatcher.Start("SplitFile");

        var lines = File.ReadLines(originalFile);

        string dir = Path.GetDirectoryName(originalFile);
        string extDir = dir + "/" + Path.GetFileNameWithoutExtension(originalFile);
        if (!Directory.Exists(extDir)) Directory.CreateDirectory(extDir);

        string partPath = extDir + "/" + Guid.NewGuid().ToString() + Path.GetExtension(originalFile);

        var outputFile = new StreamWriter( File.OpenWrite(partPath));
        foreach(string line in lines)
        {
            outputFile.WriteLine(line);
            if (outputFile.BaseStream.Position >= maxFileSize)
            {
                outputFile.Close();
                partPath = extDir + "/" + Guid.NewGuid().ToString() + Path.GetExtension(originalFile);
                outputFile = new StreamWriter(File.OpenWrite(partPath));
            }
        }

        TimeWatcher.Show("SplitFile", true);
        return extDir;
    }

    /// <summary>
    /// Внутренняя сортировка файла
    /// </summary>
    /// <param name="originalFile">Сортируемый файл</param>
    public static void InternalSort(string originalFile)
    {
        TimeWatcher.Start("InternalSort");

        List<string> list = File.ReadAllLines(originalFile).ToList();
        list.Sort();
        File.WriteAllLines(originalFile, list);

        TimeWatcher.Show("InternalSort", true);
    }

    /// <summary>
    /// Слияние файлов в указанной директории
    /// </summary>
    /// <param name="dir">директория с файлами</param>
    private static void MergeFilesInDirectory(string dir)
    {
        TimeWatcher.Start("MergeFilesInDirectory");

        // Открываем все файлы разом и формируем слой чтения
        List<StreamReader> readers = new List<StreamReader>();
        List<string> layer = new List<string>(readers.Count);
        foreach (string file in Directory.GetFiles(dir, "*.txt", SearchOption.AllDirectories))
        {
            var reader = new StreamReader(File.OpenRead(file));
            readers.Add(reader);
            layer.Add(reader.ReadLine());
        }

        //Создаем файл результата
        var writter = new StreamWriter(File.OpenWrite(dir + "/Result.txt"));

        int Id = 0;
        while(layer.FirstOrDefault(x=>x!=null) != null)
        {
            string min = layer.Min();
            Id = layer.IndexOf(min);
            layer[Id] = readers[Id].ReadLine();
            writter.WriteLine(min);
        }

        writter.Close();
        foreach (var reader in readers)
            reader.Close();

        foreach (string file in Directory.GetFiles(dir, "*.txt", SearchOption.AllDirectories))
        {
            if (Path.GetFileNameWithoutExtension(file) != "Result")
                File.Delete(file);
        }
        TimeWatcher.Show("MergeFilesInDirectory", true);
    }
}

Нашел возможность увеличить максимальный размер объекта(в .NET ограничение 2Гб). Благодаря этому можно спокойно прочитать весь файл в память, а уже там отрывать куски. Чтение 2 Гб(с SSD в DDR3) заняло 0.7 секунд.

<configuration>
  <runtime>
    <gcAllowVeryLargeObjects enabled="true" />
  </runtime>  
..

Подробности тут: https://social.msdn.microsoft.com/Forums/ru-RU/8d5880fe-108e-47d2-bbd7-4669e0aec1ec/-2-?forum=programminglanguageru

12
  • 1) Читайте с буфером 2) Пишите с буфером 3) Сортируйте за логарифм
    – tym32167
    26 янв 2019 в 1:45
  • А по подробнее?) 26 янв 2019 в 2:02
  • 5
    ну, как минимум, я вижу, что вы считываете строки по одной за раз. Пишете тоже по 1 стоке за раз. Но чтобы эффективно читать с жесткого диска и писать, вам надо уменьшить количество считываний / записей. Вы этого можете добиться при помощи буфера в памяти. Я уже писал про это: раз, два, три, ну, или вот у меня был вопрос, где я генерировал 16 гигов и сортировал их за 25 минут
    – tym32167
    26 янв 2019 в 2:15
  • @tym32167, подправил. Скорость разбития файла выросла в 3 раза(с 30 секунд до 10). Уже спасибо! Однако основное время отбирает сортировка. Ваш вопрос почитал, но чет так и не понял, куда рыть. Ткните пальцем пожалуйста) 26 янв 2019 в 6:00
  • В методе SplitFile вы читаете 100 Мб и записываете в новый файл. Потом в методе InternalSort повторно читаете эти же данные. Измените алгоритм: читайте из большого файла 100 Мб в список, сразу сортируйте его и записывайте. Потом останется лишь смержить. 26 янв 2019 в 9:55

1 ответ 1

0

Малый файл читаем в память целиком как массив байт. Разбиваем массив на куски по разделителю 0x0A(разделитель включаем в строку). Сортируем получившийся массив кусков( Потребуется написать свой Comparer). Затем открываем BufferedStream на чтение большого файла и еще один такой же стрим на запись в выходной файл. Тут я для удобства использова StreamReader. Читаем строку. Получаем байты строки в unicode. И выполняем бинарный поиск этого массива байт строки в нашем отсортированном массиве кусков малого файла. Если не нашли - записываем в выходной файл. Так же можно дополнительно сохранять отсортированный массив в тот же файл, из которого его получили и каким то образом запоминать, что файл уже отсортирован и при следуещем его использовании не сортировать. Важно. Сборка должна выполняться под x64. Размер файла который читается целиком - не должен быть больше 2ГБ. Иначе функция File.ReadAllBytes выдаст исключение.

Ваш ответ

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

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