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 миллионов целых чисел.
Only those users with full accounts are able to leave comments. Log in, please.
Сортировка миллиона 32-битных int'ов в 2 мегабайтах памяти на Питоне