Python-сообщество

Собственно вопрос вот:
Есть текстовый файл. В нем содержится около 1 млрд чисел. Нужно отсортировать числа по убыванию. Кто нибудь может подсказать какими методами сортировки воспользоваться? Понятное дело, что такие кол-ва информации обычным способом не отсортируешь. Может нужно разбить файл на части, работать с ними, а потом эти результаты объединять как - то (метод merge подойдет?). У кого какие идеи?

esal
Собственно вопрос вот:
Есть текстовый файл. В нем содержится около 1 млрд чисел. Нужно отсортировать числа по убыванию. Кто нибудь может подсказать какими методами сортировки воспользоваться? Понятное дело, что такие кол-ва информации обычным способом не отсортируешь. Может нужно разбить файл на части, работать с ними, а потом эти результаты объединять как - то (метод merge подойдет?). У кого какие идеи?

диапозон чисел от 0.01 до 1.0
а подробнее можно узнать об этом методе “сортировка подсчетом” ? Он точно подходит для такого огромного количества double чисел ?

какова разрядность чисел, т.е. не более 2-х знаков после запятой?
если так, то все просто. числа варьируются от 1 до 100 (умножив на 100).
делаем массив arr = range(101), и за 1 проход просчитываем кол-во каждого числа в куче. arr += 1
в итоге весь миллиард будет зажат в 400 байт (или около того). по этому массиву легко вычислить значение по индексу.

Отредактировано (Окт. 21, 2010 17:27:48)

если разрядность неограниченная, то можно такой вариант: за 1 проход раскидываем все числа например на 1000 куч, и потом каждую кучу сортируем, в первую кучу числа от 0,01 до 0,02, вот 2-ю от 0,02- 0,03 и т.д.

Думаю вам стоит присмотреться к “Сортировке слиянием”

питончую сортировку слияниями :) http://algolist.manual.ru/sort/faq/q10.php

или сильно оптимизированный вариант, но более сложная реализация http://algolist.manual.ru/sort/faq/q13.php

Отредактировано (Окт. 21, 2010 19:10:22)

o7412369815963
какова разрядность чисел, т.е. не более 2-х знаков после запятой?

esal
самый простой способ обработка через if и отсортировать по кускам от 0,01-0,02 затем когда закончишь собирать куски , заливай всё в 1 фаил , есть правда еще альтернатива к примеру sql использовать

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() - функция слияния.