Сортировка миллиона 32-битных int'ов в 2 мегабайтах памяти на Питоне

[@santeri]

спасибо. интересно было почитать.

[@Dolphin_Daniel]

проникся) тяжеловато, конечно, для кропотливого анализа… особенно в понедельник вечером)

[@D3D]

использовать фаил как-то не кошерно, интересно сжать массив в памяти в питоне можно?

[@happybyte]

Сжимать не нужно. В данном случае можно еще ускориться используя bin/bucket/postman алгоритмы — тогда в конце слияние фактически не нужно будет делать в том виде, как это делает merge — достаточно будет просто склеить файлы. Если быть особенным извращенцем, то большой файл можно склеить из кусочков минуя чтение и запись — тупо объединив иноды, кластеры (или еще че в зависимости от FS) в один файл напрямую редактируя FS :)

Собственно гря в этом случае, как я понял до алгоритмов не дошло. Просто использовался трюк с (относительно неэффективным) разбиением на более мелкие куски.

А если вникнуть глубже в задачу, то можно специализировать алгоритм на тип данных, что может привести к тому, что в кусках, которые получаются после предварительной псевдо-сортировки, уже можно сравнивать даже не все 32 бита, а только половину, поскольку, например, старшие два байта в куске у всех чисел могут быть одинаковы :) +SMP, GPGPU и т.п. Пространства для оптимизации весьма и весьма много.

[@D3D]

В переводе написано «2 мегабайтах памяти на Питон» и получается что автор просто из оперативной памяти перекинул на жесткий диск, что кажется нарушением условий задачи, в оригинале же же неоднозначности нет «in 2 megabytes of RAM».

[@Goodkat]

ну где-то же должны лежать эти числа до сортировки и после сортировки
можно было бы усложнить решение условием, что суммарный объём оперативной памяти и создаваемых файлов не должен превышать двух мегабайт, но это тоже решаемо

[@pcmaniac]

Н. Вирт «Алгоритмы + Структуры данных = Программы» ;)

[@pcmaniac]

Вот интересно тут сделать раздел, в котором классические алгоритмы будут реализовываться энтузиастами на разных языках программирования. Это был-бы отличный (от холивара :) ) способ померяться сравнить элегантность реализации того или иного алгоритма на разных языках.

[@winger]

Идея очень неплохая, было бы интересно почитать грамотный код на разных языках. Глядишь и выучить что-то новое захочется)

Думаю стоит написать статью для затравки, например про реализации каких-нибудь сбалансированных деревьев

[@Beholder]

Только тяжело будет Хаскелю в даже 4 мегабайтах

[@Kudja]

Сорри, я не знаю питон, но по описанию алгоритма видится мне что сортируются отдельные файлы (куски исходного) в адресном пространстве оного (т.е по 10 000 интов), и выплевываются в временный файл, но записи уже хранящиеся в временных файла никак не увязанны между собой… ну и какая же это сортировка тогда?
поправьте если я не прав…

[@BlademoR]

В данном случае heapq.merge возвращает итератор, который позволит читать из потоков отсортированных файлов в нужном порядке, сбрасывая по 1000 штук в конечный файл.

[@Kudja]

ну так это тогда имхо совсем не решение задачи, т.к. система все равно даст один из вариантов:
1. Подгрузит эти данные в память от имени другого процесса и объем памяти при выполнении далеко привысит поставленный в задаче
2. она будет делать кучу операций чтения/записи, что сильно замедлит работу процесса…
или я не понял исходной задачи?
сорри — просто самому интересно стало каким образом тут все происходит… может быть если в вышесказанном я не прав, то опишите подробнее алгоритм?

[@pcmaniac]

Кэширование дисковых операций — это необязательное выделение памяти. т.е. она выделится только если есть свободная, но в принципе будет работать и без неё (чего не скажешь о выделении памяти под буфер для сортировки самой программой). А производительность алгоритма в условиях задачи не озвучена ;)

[@cblp]

В Питоне есть такая штука, как генератор. В общих чертах, это такая последовательность, члены которой вычисляются тогда, когда к ним обращаются. Обратите внимание на оператор yield.

[@BlademoR]

Это функция не подгружает все значения в память сразу, а будет грузить поочереди. В том и задача, чтоб не забить 2 мегабайта памяти сразу. Да, операций чтения будет достаточно много, но задача минимальной работы с диском и не требует.

[@cblp]

В 23 строке данные из временных файлов загружаются в iters, а в 26 происходит слияние.

[@mocksoul]

зачем каверкать русский язык?
int'ов — чисел

[@rayevg]

Я думаю, тут имелся ввиду типа данных.

[@pcmaniac]

«число» — понятие растяжимое. Оно может быть и 8 и 128 битным. Вот например я не вижу ничего сложного в сортировке миллиона 8-ми битных чисел в оперативной памяти т.к. они будут занимать 1Mb а по условию задачи нам выделяется 2.
Автор же имел ввиду тип int — 32-х битное целое. Миллион таких чесел «весит» 4Mb и без дополнительных ухищрений их в оперативной памяти не отсортировать ибо не влезут)

[@mocksoul]

в заголовке и названии статьи — норм. В середине везде — не норм.

— it reads up to 1000 integers at a time
— он считывает до 1000 int'ов за раз

чуете чем попахивает?

[@pcmaniac]

Думаю что писать «до 1000 32-битных int'ов» слишком громоздко. По названию и вступлению и так уже все поняли что эти int'ы 32-х битные.

[@mocksoul]

тьфу да это-то тут при чём.

прекратите смотреть на все что видите с точки зрения разработчика — это переводится просто «он считывает до 1000 чисел за раз». Всё. Никаких тут 32-битных int'ов и прочих вещей.

[@Mezomish]

А с какой точки зрения нужно смотреть? Химика-генетика?
Статья имеет явно выраженный программистский контекст. А в этом контексте перевод «1000 чисел за раз» — некорректен.

[@chiaroscuro]

Эхехе. int — не число что ли? LOL

[@Mezomish]

Боюсь, я сейчас сломаю Вашу картину мира, но числа бывают не только целые. Более того: целые числа бывают не только int. Надеюсь, это было не очень больно…

Возвращаясь к вопросу: разумеется, int — это число. Но переводить «1000 integers» как «1000 чисел» — неверно. Вот такой, панимашь, парадокс.

[@chiaroscuro]

> но числа бывают не только целые. Более того: целые числа бывают не только int.

Ба! А мужики-то не знают!

«1000 integers» — тысяча целых чисел (учел ошибку), ну никак не 1000 int'ов (фффуу. кстати, раз уж занудствуем, int'ы бывают не только 32-х битные)

[@Mezomish]

Ну вот, уже лучше. Не просто «1000 чисел», а «1000 целых чисел».
А если быть ещё точнее, то «1000 целых 32-битных чисел» (о чём и идёт речь в статье). Автором подразумевалось именно это (ибо статья как раз об этом).
А т.к. статья написана программистом для программистов, то «программизм» «1000 int'ов» там более чем уместен, т.к. не оставляет двусмысленностей и лаконично доносит смысл. В отличие от «1000 чисел», которое вызывает кучу вопросов: «каких чисел?», «какой точности?» и т.д.

[@highw]

зануда

[@Dolphin_Daniel]

я думаю просто Василий поленился переводить) имелись ввиду целые числа…

[@YasonBy]

Действительно, незачем — лучше уж писать англицизмы, чем коверкать русский язык.

[@BlademoR]

В данном случае heapq.merge возвращает итератор, который позволит читать из потоков отсортированных файлов в нужном порядке, сбрасывая по 1000 штук в конечный файл.

[@BlademoR]

Извините, не туда написал.

[@muslimov]

«100 жемчужин программирования»- первая задача, о сортировки при условии что в объем данных превышает объем доступной памяти.

[@david_mz]

Ничего что второй файл будет размером… я даже не назову сходу такой приставки, для 10^15 байт:)

[@Mezomish]

Петабайт.

[@winger]

Так вы же предлагаете во втором файле для каждого возможного значения иметь по соответствующему сдвигу количество таких чисел. Возможных значений 2^32, на количество надо по крайней мере 3 байта, итого имеем размер 12 гигабайт. Для такой задачи многовато, да и затраты по времени чтения/записи такого файла будут гигантскими

[@david_mz]

«Тоже» — это как Вы? Надеюсь, что нет:)

Расскажите-ка про свой алгоритм. Посмотрим, сколько Вам места понадобится…

[@david_mz]

Ага, уже 12 гигабайт:) Несколько больше 4 Мб, не так ли?

С петабайтом я ошибся, признаю. Но и 12 гигабайт приемлемыми назвать никак нельзя. И да, _в таком случае_ лучше «городить сотню файлов».

[@david_mz]

Вы тоже ненормальный? Я с самого начала говорил про Ваш второй файл. Перечитайте хистори.

[@david_mz]

habrahabr.ru/blogs/python/65503/#comment_1836028 — на мой вопрос о втором файле Вы начали гнать про 4 мегабайта _в первом_.

Идите уже, почитайте что-нибудь другое. Всё с Вами понятно.

[@OdobenusRosmarus]

существует типовое решение для сортировки, когда объем намного превышает RAM — четырехленточная сортировка.

[@sylvio]

Погуглил — не нашел, помогите

[@OdobenusRosmarus]

en.wikipedia.org/wiki/Merge_sort раздел Merge sorting tape drives

[@sylvio]

А, ну так это называется сортировка слиянием

[@OdobenusRosmarus]

Да, она, просто модифицированный вариант, рассчитанный на компьютеры с малой памятью

[@lig]

Гвидо там еще написал, что нужно молиться на heapq.merge, чем и собираюсь теперь заняться после прочтения оригинала.

[@Vayun]

Не очень наглядный пример) Вот если хотя бы 100 миллионов целых чисел.