esal
Окт. 21, 2010 16:37:29
Собственно вопрос вот:
Есть текстовый файл. В нем содержится около 1 млрд чисел. Нужно отсортировать числа по убыванию. Кто нибудь может подсказать какими методами сортировки воспользоваться? Понятное дело, что такие кол-ва информации обычным способом не отсортируешь. Может нужно разбить файл на части, работать с ними, а потом эти результаты объединять как - то (метод merge подойдет?). У кого какие идеи?
appetito
Окт. 21, 2010 16:51:50
esal
Собственно вопрос вот:
Есть текстовый файл. В нем содержится около 1 млрд чисел. Нужно отсортировать числа по убыванию. Кто нибудь может подсказать какими методами сортировки воспользоваться? Понятное дело, что такие кол-ва информации обычным способом не отсортируешь. Может нужно разбить файл на части, работать с ними, а потом эти результаты объединять как - то (метод merge подойдет?). У кого какие идеи?
если диапазон чисел ограничен и невелик по сравнению с их количеством - то “сортировка подсчетом”
esal
Окт. 21, 2010 16:57:06
диапозон чисел от 0.01 до 1.0
а подробнее можно узнать об этом методе “сортировка подсчетом” ? Он точно подходит для такого огромного количества double чисел ?
o7412369815963
Окт. 21, 2010 17:27:26
какова разрядность чисел, т.е. не более 2-х знаков после запятой?
если так, то все просто. числа варьируются от 1 до 100 (умножив на 100).
делаем массив arr = range(101), и за 1 проход просчитываем кол-во каждого числа в куче. arr += 1
в итоге весь миллиард будет зажат в 400 байт (или около того). по этому массиву легко вычислить значение по индексу.
o7412369815963
Окт. 21, 2010 17:33:27
если разрядность неограниченная, то можно такой вариант: за 1 проход раскидываем все числа например на 1000 куч, и потом каждую кучу сортируем, в первую кучу числа от 0,01 до 0,02, вот 2-ю от 0,02- 0,03 и т.д.
tmt
Окт. 21, 2010 18:51:19
Думаю вам стоит присмотреться к “Сортировке слиянием”
Zubchick
Окт. 21, 2010 19:06:14
питончую сортировку слияниями :)
http://algolist.manual.ru/sort/faq/q10.phpили сильно оптимизированный вариант, но более сложная реализация
http://algolist.manual.ru/sort/faq/q13.php
esal
Окт. 21, 2010 19:31:38
o7412369815963
какова разрядность чисел, т.е. не более 2-х знаков после запятой?
числа например могут быть такие 0.1785623711 (10 знаков после запятой)
sypper-pit
Окт. 21, 2010 21:52:53
esal
самый простой способ обработка через if и отсортировать по кускам от 0,01-0,02 затем когда закончишь собирать куски , заливай всё в 1 фаил , есть правда еще альтернатива к примеру sql использовать
o7412369815963
Окт. 21, 2010 23:01:44
Zubchick
питончую сортировку слияниями :) http://algolist.manual.ru/sort/faq/q10.php
или сильно оптимизированный вариант, но более сложная реализация http://algolist.manual.ru/sort/faq/q13.php
туфта и надувательство, эта ф-ия не делает ничего:
list-type mergesort (list-type L; int n) {
if (n = 1) return (L) else {
разделить L на две половины L1 и L2;
return (merge (mergesort (L1,n/2), mergesort (L2,n/2)) );
}
}
merge() - функция слияния.и пример там не рабочий