Как сортировать строки в большом(2Гб) файле?
1,00
р.
Строки разной длины и из разных символов, т.е. вариант с сортировкой подсчетом, не катит. Сделал внешнюю сортировку слиянием. Разбиваю файл на куски по 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 tasks = new List() //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) }
/// /// Разбитие файла на куски укaзанного размера /// /// Файл для разбития /// Максимальный размер части файла. Default = 100Mb /// Путь к папке с частями файла 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 }
/// /// Внутренняя сортировка файла /// /// Сортируемый файл public static void InternalSort(string originalFile) { TimeWatcher.Start("InternalSort")
List list = File.ReadAllLines(originalFile).ToList() list.Sort() File.WriteAllLines(originalFile, list)
TimeWatcher.Show("InternalSort", true) }
/// /// Слияние файлов в указанной директории /// /// директория с файлами private static void MergeFilesInDirectory(string dir) { TimeWatcher.Start("MergeFilesInDirectory")
// Открываем все файлы разом и формируем слой чтения List readers = new List() List layer = new List(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 секунд.
..
Подробности тут: https:/ocial.msdn.microsoft.com/Forums/ru-RU/8d5880fe-108e-47d2-bbd7-4669e0aec1ec/-2-?forum=programminglanguageru
Ответ
Для ускорения работы с файлом, используйьте mmap — "POSIX-совместимый системный вызов Unix, позволяющий выполнить отображение файла или устройства на память."
Прикладываю свой код.
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 tasks = new List() //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) }
/// /// Разбитие файла на куски укaзанного размера /// /// Файл для разбития /// Максимальный размер части файла. Default = 100Mb /// Путь к папке с частями файла 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 }
/// /// Внутренняя сортировка файла /// /// Сортируемый файл public static void InternalSort(string originalFile) { TimeWatcher.Start("InternalSort")
List list = File.ReadAllLines(originalFile).ToList() list.Sort() File.WriteAllLines(originalFile, list)
TimeWatcher.Show("InternalSort", true) }
/// /// Слияние файлов в указанной директории /// /// директория с файлами private static void MergeFilesInDirectory(string dir) { TimeWatcher.Start("MergeFilesInDirectory")
// Открываем все файлы разом и формируем слой чтения List readers = new List() List layer = new List(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 секунд.
..
Подробности тут: https:/ocial.msdn.microsoft.com/Forums/ru-RU/8d5880fe-108e-47d2-bbd7-4669e0aec1ec/-2-?forum=programminglanguageru
Ответ
Для ускорения работы с файлом, используйьте mmap — "POSIX-совместимый системный вызов Unix, позволяющий выполнить отображение файла или устройства на память."
