Comments 60
спасибо. интересно было почитать.
проникся) тяжеловато, конечно, для кропотливого анализа… особенно в понедельник вечером)
использовать фаил как-то не кошерно, интересно сжать массив в памяти в питоне можно?
Сжимать не нужно. В данном случае можно еще ускориться используя bin/bucket/postman алгоритмы — тогда в конце слияние фактически не нужно будет делать в том виде, как это делает merge — достаточно будет просто склеить файлы. Если быть особенным извращенцем, то большой файл можно склеить из кусочков минуя чтение и запись — тупо объединив иноды, кластеры (или еще че в зависимости от FS) в один файл напрямую редактируя FS :)
Собственно гря в этом случае, как я понял до алгоритмов не дошло. Просто использовался трюк с (относительно неэффективным) разбиением на более мелкие куски.
А если вникнуть глубже в задачу, то можно специализировать алгоритм на тип данных, что может привести к тому, что в кусках, которые получаются после предварительной псевдо-сортировки, уже можно сравнивать даже не все 32 бита, а только половину, поскольку, например, старшие два байта в куске у всех чисел могут быть одинаковы :) +SMP, GPGPU и т.п. Пространства для оптимизации весьма и весьма много.
Собственно гря в этом случае, как я понял до алгоритмов не дошло. Просто использовался трюк с (относительно неэффективным) разбиением на более мелкие куски.
А если вникнуть глубже в задачу, то можно специализировать алгоритм на тип данных, что может привести к тому, что в кусках, которые получаются после предварительной псевдо-сортировки, уже можно сравнивать даже не все 32 бита, а только половину, поскольку, например, старшие два байта в куске у всех чисел могут быть одинаковы :) +SMP, GPGPU и т.п. Пространства для оптимизации весьма и весьма много.
Н. Вирт «Алгоритмы + Структуры данных = Программы» ;)
Вот интересно тут сделать раздел, в котором классические алгоритмы будут реализовываться энтузиастами на разных языках программирования. Это был-бы отличный (от холивара :) ) способ померяться сравнить элегантность реализации того или иного алгоритма на разных языках.
Сорри, я не знаю питон, но по описанию алгоритма видится мне что сортируются отдельные файлы (куски исходного) в адресном пространстве оного (т.е по 10 000 интов), и выплевываются в временный файл, но записи уже хранящиеся в временных файла никак не увязанны между собой… ну и какая же это сортировка тогда?
поправьте если я не прав…
поправьте если я не прав…
В данном случае heapq.merge возвращает итератор, который позволит читать из потоков отсортированных файлов в нужном порядке, сбрасывая по 1000 штук в конечный файл.
ну так это тогда имхо совсем не решение задачи, т.к. система все равно даст один из вариантов:
1. Подгрузит эти данные в память от имени другого процесса и объем памяти при выполнении далеко привысит поставленный в задаче
2. она будет делать кучу операций чтения/записи, что сильно замедлит работу процесса…
или я не понял исходной задачи?
сорри — просто самому интересно стало каким образом тут все происходит… может быть если в вышесказанном я не прав, то опишите подробнее алгоритм?
1. Подгрузит эти данные в память от имени другого процесса и объем памяти при выполнении далеко привысит поставленный в задаче
2. она будет делать кучу операций чтения/записи, что сильно замедлит работу процесса…
или я не понял исходной задачи?
сорри — просто самому интересно стало каким образом тут все происходит… может быть если в вышесказанном я не прав, то опишите подробнее алгоритм?
Кэширование дисковых операций — это необязательное выделение памяти. т.е. она выделится только если есть свободная, но в принципе будет работать и без неё (чего не скажешь о выделении памяти под буфер для сортировки самой программой). А производительность алгоритма в условиях задачи не озвучена ;)
В Питоне есть такая штука, как генератор. В общих чертах, это такая последовательность, члены которой вычисляются тогда, когда к ним обращаются. Обратите внимание на оператор
yield.Это функция не подгружает все значения в память сразу, а будет грузить поочереди. В том и задача, чтоб не забить 2 мегабайта памяти сразу. Да, операций чтения будет достаточно много, но задача минимальной работы с диском и не требует.
В 23 строке данные из временных файлов загружаются в
iters, а в 26 происходит слияние.
зачем каверкать русский язык?
int'ов — чисел
Я думаю, тут имелся ввиду типа данных.
«число» — понятие растяжимое. Оно может быть и 8 и 128 битным. Вот например я не вижу ничего сложного в сортировке миллиона 8-ми битных чисел в оперативной памяти т.к. они будут занимать 1Mb а по условию задачи нам выделяется 2.
Автор же имел ввиду тип int — 32-х битное целое. Миллион таких чесел «весит» 4Mb и без дополнительных ухищрений их в оперативной памяти не отсортировать ибо не влезут)
Автор же имел ввиду тип int — 32-х битное целое. Миллион таких чесел «весит» 4Mb и без дополнительных ухищрений их в оперативной памяти не отсортировать ибо не влезут)
в заголовке и названии статьи — норм. В середине везде — не норм.
— it reads up to 1000 integers at a time
— он считывает до 1000 int'ов за раз
чуете чем попахивает?
— it reads up to 1000 integers at a time
— он считывает до 1000 int'ов за раз
чуете чем попахивает?
Думаю что писать «до 1000 32-битных int'ов» слишком громоздко. По названию и вступлению и так уже все поняли что эти int'ы 32-х битные.
тьфу да это-то тут при чём.
прекратите смотреть на все что видите с точки зрения разработчика — это переводится просто «он считывает до 1000 чисел за раз». Всё. Никаких тут 32-битных int'ов и прочих вещей.
прекратите смотреть на все что видите с точки зрения разработчика — это переводится просто «он считывает до 1000 чисел за раз». Всё. Никаких тут 32-битных int'ов и прочих вещей.
А с какой точки зрения нужно смотреть? Химика-генетика?
Статья имеет явно выраженный программистский контекст. А в этом контексте перевод «1000 чисел за раз» — некорректен.
Статья имеет явно выраженный программистский контекст. А в этом контексте перевод «1000 чисел за раз» — некорректен.
Эхехе. int — не число что ли? LOL
Боюсь, я сейчас сломаю Вашу картину мира, но числа бывают не только целые. Более того: целые числа бывают не только int. Надеюсь, это было не очень больно…
Возвращаясь к вопросу: разумеется, int — это число. Но переводить «1000 integers» как «1000 чисел» — неверно. Вот такой, панимашь, парадокс.
Возвращаясь к вопросу: разумеется, int — это число. Но переводить «1000 integers» как «1000 чисел» — неверно. Вот такой, панимашь, парадокс.
> но числа бывают не только целые. Более того: целые числа бывают не только int.
Ба! А мужики-то не знают!
«1000 integers» — тысяча целых чисел (учел ошибку), ну никак не 1000 int'ов (фффуу. кстати, раз уж занудствуем, int'ы бывают не только 32-х битные)
Ба! А мужики-то не знают!
«1000 integers» — тысяча целых чисел (учел ошибку), ну никак не 1000 int'ов (фффуу. кстати, раз уж занудствуем, int'ы бывают не только 32-х битные)
Ну вот, уже лучше. Не просто «1000 чисел», а «1000 целых чисел».
А если быть ещё точнее, то «1000 целых 32-битных чисел» (о чём и идёт речь в статье). Автором подразумевалось именно это (ибо статья как раз об этом).
А т.к. статья написана программистом для программистов, то «программизм» «1000 int'ов» там более чем уместен, т.к. не оставляет двусмысленностей и лаконично доносит смысл. В отличие от «1000 чисел», которое вызывает кучу вопросов: «каких чисел?», «какой точности?» и т.д.
А если быть ещё точнее, то «1000 целых 32-битных чисел» (о чём и идёт речь в статье). Автором подразумевалось именно это (ибо статья как раз об этом).
А т.к. статья написана программистом для программистов, то «программизм» «1000 int'ов» там более чем уместен, т.к. не оставляет двусмысленностей и лаконично доносит смысл. В отличие от «1000 чисел», которое вызывает кучу вопросов: «каких чисел?», «какой точности?» и т.д.
зануда
я думаю просто Василий поленился переводить) имелись ввиду целые числа…
Действительно, незачем — лучше уж писать англицизмы, чем коверкать русский язык.
В данном случае heapq.merge возвращает итератор, который позволит читать из потоков отсортированных файлов в нужном порядке, сбрасывая по 1000 штук в конечный файл.
«100 жемчужин программирования»- первая задача, о сортировки при условии что в объем данных превышает объем доступной памяти.
UFO just landed and posted this here
Ничего что второй файл будет размером… я даже не назову сходу такой приставки, для 10^15 байт:)
Петабайт.
UFO just landed and posted this here
Так вы же предлагаете во втором файле для каждого возможного значения иметь по соответствующему сдвигу количество таких чисел. Возможных значений 2^32, на количество надо по крайней мере 3 байта, итого имеем размер 12 гигабайт. Для такой задачи многовато, да и затраты по времени чтения/записи такого файла будут гигантскими
«Тоже» — это как Вы? Надеюсь, что нет:)
Расскажите-ка про свой алгоритм. Посмотрим, сколько Вам места понадобится…
Расскажите-ка про свой алгоритм. Посмотрим, сколько Вам места понадобится…
UFO just landed and posted this here
Ага, уже 12 гигабайт:) Несколько больше 4 Мб, не так ли?
С петабайтом я ошибся, признаю. Но и 12 гигабайт приемлемыми назвать никак нельзя. И да, _в таком случае_ лучше «городить сотню файлов».
С петабайтом я ошибся, признаю. Но и 12 гигабайт приемлемыми назвать никак нельзя. И да, _в таком случае_ лучше «городить сотню файлов».
существует типовое решение для сортировки, когда объем намного превышает RAM — четырехленточная сортировка.
Гвидо там еще написал, что нужно молиться на heapq.merge, чем и собираюсь теперь заняться после прочтения оригинала.
Не очень наглядный пример) Вот если хотя бы 100 миллионов целых чисел.
Sign up to leave a comment.
Сортировка миллиона 32-битных int'ов в 2 мегабайтах памяти на Питоне