Имеется многогигабайтный файл, содержащий массив целых чисел от 1 до 10000. Элементы расположены хаотично с повторениями. Необходимо его отсортировать. Принять во внимание ограниченность в ресурсах.
Самым ленивым способом отсортировать можно используя «внешнюю сортировку со слиянием», но это весьма тяжёлый и долгий метод. В этой публикации я расскажу, какой метод пришёл мне в голову — я не смог не поделиться им.
Итак, меня смутил словарь данных: от 1 до 10000 и в то же время ограниченность ресурсов. Решил сделать следующее. Для начала будем генерировать нужный нам входной файл, не руками же его писать. Для этого использовал старый добрый rnd:
System.IO.StreamWriter file = new System.IO.StreamWriter(@"C:\1\Nabor.txt", true); //Создаём файлик
Random rnd = new Random();
this.progressBar1.Maximum = Convert.ToInt32(this.textBox1.Text); //Будет нам показывать процесс записи
int value;
for (int i = 0;i<Convert.ToInt32(this.textBox1.Text);i++) //шуруем циклом по заданному колличеству
{
value = rnd.Next(0, 10000);
file.WriteLine(value); //Собственно генерация и запись в наш файл
this.progressBar1.Value++;
}
file.Close();Далее сама сортировка:
1. Создаём массив int[10000]. В ОЗУ это займёт 40 Мб. На C# (на других языках чуть больше). Я буду называть его массивRAM, массив исходный — массивIN, и массив выходной — МассивOUT.
Почему 10000? Потому что словарь данных у нас в диапазоне от 1 до 10000.
2. Читаем исходный файл поэлементно ( в моём случае построчно) и делаем следующее с каждой записью:
string line; //Объявляем строку как читаемый элемент
int[] arr;
arr = new int[10000]; //Объявляем наш массив
System.IO.StreamReader file2 = new System.IO.StreamReader(@"C:\1\Nabor.txt");
while ((line = file2.ReadLine()) != null)
{
arr[Convert.ToInt32(line)]++; // плюсуем одно повторение для элемента
}
file2.Close();То есть в элемент массиваRAM с индексом, равному считанному значению из массиваIN делаем +1. В итоге в массивеRAM будет содержаться количество повторений каждого элемента из массиваIN.
Наглядно постарался изобразить на рисунке:
3. И последним этапом мы пробегаем по нашему массивуRAM и записываем поочерёдно все индексы элементов массиваRAM по количеству их повторений:
System.IO.StreamWriter file3 = new System.IO.StreamWriter(@"C:\1\Sort.txt", true);
int i, j;
for (i=0;i<10000;i++)
{
if (arr[i]>0) // Если вообще элемент встречался
{
for (j = 0; j < arr[i]; j++) // Цикл, сколько раз встречался = значение нашего массиваRAM
{
file3.WriteLine(i); //Записываем индекс нашего массива, а не его значение
}
}
}
file3.Close();Таким образом файл размером 575Мб с 100 000 000 записями был отсортирован и записан за 7,53 секунд на машине: AMD A10, 6Гб, SATA. Без жадности к памяти и ресурсам.
Напоследок хочу сказать, что использовать данный метод нужно осторожно, избегая переполнения типов. То есть, если взять массив из 5 000 000 000 значений пусть с тем же словарём данных, и предположить, что все значения в нём будут одно и тоже число, то совершится переполнение типа int, и программа выдаст исключение.
Весь проект, думаю, выкладывать смысла нет, но если будут пожелания, то выложу. Удачных разработок!)
Комментарии (30)
Jigglypuff
01.09.2016 12:25+1Поздравляю, вы изобрели сортировку подсчетом.
Jigglypuff
02.09.2016 08:23+1Отправлял этот комментарий до комментария Sirion.
Мне кажется, у R&C-пользователей должна быть возможность удалить отправленный на модерацию комментарий (специально для случаев, когда он становится неактуален).
Sirion
02.09.2016 08:48Если так по-хорошему, вообще всем пользователям не помешала бы возможность удаления комментариев. Вот эти постоянные «del», «не в ту ветку» и «я всегда буду обновлять комментарии» очень замусоривают треды. И не надо говорит, что юзерам надо быть внимательнее. Это сайт должен быть для людей, а не люди для сайта.
Enterindead
01.09.2016 12:25+4В ОЗУ это займёт 40 Мб. На C# (на других языках чуть больше)
Сильное заявление, проверять я его конечно не буду ©
knagaev
01.09.2016 15:44Ну накинулись и загнобили со своей сортировкой подсчётом :)
И вообще всё давно придумано, даже Шекспир всё у Эразма Роттердамского спёр.
Автор, советую книгу «Жемчужины программирования» Джона Бентли.Sirion
01.09.2016 16:24Только не у Эразма Роттердамского, а у Саксона Грамматика. И не «Жемчужины программирования» Джона Бентли, а «Алгоритмы: построение и анализ» Кормена.
knagaev
02.09.2016 15:52Не надо категоричности — в интернете кто-то не прав? :)
Да, у Саксона, говорят, «Гамлета», но Шекспир написал не только «Гамлета».
И я советовал автору «Жемчужины» (имею право?), а Вы можете посоветовать что хотите, можно и Кормена со товарищи.
kaiZer_dragomir
01.09.2016 19:13Автор, просто поставь тег «для новичков», или какие есть тут ещё посмотри. И никто бы не придирался так:)
А лучше просто займись немного формальным обучением(которым часто пренебрегают, к сожалению), что бы таких «открытий» не было.
DeadKnight
01.09.2016 19:13-2Знаете, конечно в наше время хорошо, когда ты в Гугле можешь найти все, что угодно. И думать не надо.
Но я все же считаю, что автор молодец. Лучше человек сейчас научится думать и находить решения, пусть даже уже и давно известные, чем тупо гуглить и копипастить.
Т.ч. не смотря на велосипед, автору все равно респект.
Farxial
01.09.2016 19:13Не понимаю, чего вы на него так.
Есть подозрение, что, получи ТС нормальное задание — он решил бы его не этим способом, а каким-то другим. Это с 1..10000 результат обошёлся в 40 Мб (и вообще-то это уже много, если ориентироваться не на новый комп, а на старый или на какую-нибудь встраиваемую систему), в реальных задачах он обошёлся бы намного дороже. Таким образом смысл задания даже не в том, чтобы придумать, как сделать максимально хорошо, а в том, чтобы тупо выполнить это задание.
Привет нашей текущей системе образования (такое может поступить только от неё или её адептов).
terra_agro
01.09.2016 19:14+1«Принять во внимание ограниченность в ресурсах.»
И тут же:
for (int i = 0;i<Convert.ToInt32(this.textBox1.Text);i++)
Midgard88
01.09.2016 19:16-1Да, я потом уже погуглил и понял что велосипед уже есть). Но задание выполнялось без компа, инэта и гугла, на листочке. Можно сказать на горячую при собеседовании. Поэтому Ни копипастов, ни алгоритмов, только то, что было в голове.
Тег «для новичков» поставлю)
zagayevskiy
01.09.2016 22:32+1Поэтому Ни копипастов, ни алгоритмов, только то, что было в голове.
Не советовал бы я вам это на собеседовании говорить. Алгоритмы — они в голове должны быть. А сортировка подсчётом — это первое, что приходит в голову после прочтения задачи.Farxial
02.09.2016 00:02-2«Сортировка подсчётом» — лишь название. А то, что он не знает всех алгоритмов (и их названий), нормально, если он ещё мало программирует (если это так).
zagayevskiy
02.09.2016 00:07+1O_o хэш-таблица — лишь название. Q-sort — лишь название.
Farxial
02.09.2016 00:35-2Ну… да? Это идентификаторы объектов. Если не знаешь, что %суть объекта% общеизвестно и имеет определённый идентификатор предпочтительнее изложения сути — излагаешь саму суть.
zagayevskiy
02.09.2016 12:17+2Если не знаешь, что %суть объекта% общеизвестно, то возьми и почитай книжку, чтобы знать, а не неси это на хабр как офигенное открытие.
я расскажу, какой метод пришёл мне в голову — я не смог не поделиться им.
Тем более с таким кодом, как у автора. Комментарии «объявляем массив», «плюсуем элемент».
daiver19
01.09.2016 22:58+2Мне вот интересно, если кто-нибудь напишет пост, в котором он решает задачу сложения двух целых чисел от 1 до 10 (потому что ему дали такое задание и он сам решение придумал), то тоже найдутся «защитники»?
G-M-A-X
02.09.2016 20:29+11. Создаём массив int[10000]. В ОЗУ это займёт 40 Мб. На C# (на других языках чуть больше).
Может 40 кБ?
for (j = 0; j < arr[i]; j++) // Цикл, сколько раз встречался = значение нашего массиваRAM { file3.WriteLine(i); //Записываем индекс нашего массива, а не его значение }
Лучше как-то так (PHP):
$buffer = str_repeat($i."\n", $arr[$i]); file_put_contents(file3, $buffer, FILE_APPEND | LOCK_EX);
Приходилось переделывать mysql-дамп под postgres — значительное ускорение дала буферизация записи.
П.С. Что у вас за стиль с дополнительной табуляцией для {? :)
Sirion
Поздравляю, вы изобрели сортировку подсчётом.
Mugik
Я вот тоже не пойму, вроде бы до первого апреля еще далеко, но неужели автор перед тем как взяться за задачу, хотя бы элементарно не посмотрел какие есть сортировки, причем сортировку слиянием он освоил. Наверно это шутка или может что-то автор забыл упомянуть в своей модификации.
Mugik
Нет, я ошибся, автор не освоил сортировку слиянием. Имеется в виду внешняя сортировка, ну тогда вопрос к автору, а что есть внешняя сортировка без слияния? Просто элементы разбегаются по разным участкам памяти и их уже не найти, если без слияния или как)