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

    Мой перевод статьи Гвидо ван Россума:

    Меня тут в шутку спросили: смогу ли я отсортировать миллион 32-битных int'ов в 2 мегабайтах памяти на Питоне. Во время размышления, мне пришло в голову задействовать механизм ввода-вывода с использованием буферной памяти.

    Вообще, это именно шуточный вопрос — одни только данные займут 4 мегабайта, при условии бинарного представления! Правда, можно пойти на хитрость — взять файл, содержащий миллион 32-битных int'ов. Как же отсортировать их, используя минимальное количество памяти? Это должна быть какая-то разновидность сортировки слиянием, в которой небольшие куски данных сортируются и записываются во временный файл, после чего происходит слияние временных файлов для получения окончательного результата.

    Вот мое решение:

    Copy Source | Copy HTML
    1. #!/usr/bin/env python3.0
    2. import sys, array, tempfile, heapq
    3. assert array.array('i').itemsize == 4
    4.  
    5. def intsfromfile(f):
    6.  while True:
    7.     a = array.array('i')
    8.     a.fromstring(f.read(4000))
    9.     if not a:
    10.         break
    11.     for x in a:
    12.         yield x
    13.  
    14. iters = []
    15. while True:
    16.  a = array.array('i')
    17.  a.fromstring(sys.stdin.buffer.read(40000))
    18.  if not a:
    19.      break
    20.  f = tempfile.TemporaryFile()
    21.  array.array('i', sorted(a)).tofile(f)
    22.  f.seek(0)
    23.  iters.append(intsfromfile(f))
    24.  
    25. a = array.array('i')
    26. for x in heapq.merge(*iters):
    27.  a.append(x)
    28.  if len(a) >= 1000:
    29.      a.tofile(sys.stdout.buffer)
    30.      del a[:]
    31. if a:
    32.  a.tofile(sys.stdout.buffer)

    На моей 3х-летней персоналке под управлением Linux, выполнение заняло 5.4 секунды при чтении данных из входного файла, содержащего ровно миллион случайных 32-битных int'ов. Это не так уж плохо, учитывая, что при чтении данных прямо из памяти сортировка занимает 2 секунды:

    Copy Source | Copy HTML
    1. #!/usr/bin/env python3.0
    2. import sys, array
    3. a = array.array('i', sys.stdin.buffer.read())
    4. a = list(a)
    5. a.sort()
    6. a = array.array('i', a)
    7. a.tofile(sys.stdout.buffer)

    Вернемся к нашей сортировке. Первые 3 строки очевидны:

    Copy Source | Copy HTML
    1. #!/usr/bin/env python3.0
    2. import sys, array, tempfile, heapq
    3. assert array.array('i').itemsize == 4

    Первая строка указывает, что мы используем Python 3.0. Вторая строка импортирует необходимые модули. Третья строка вызывает прерывание на 64-битных системах, где int не 32-битный — передо мной не ставилась задача написать портируемый код.

    Затем мы объявили функцию, которая считывает int'ы из файла:

    Copy Source | Copy HTML
    1. def intsfromfile(f):
    2.  while True:
    3.      a = array.array('i')
    4.      a.fromstring(f.read(4000))
    5.      if not a:
    6.          break
    7.      for x in a:
    8.          yield x

    Это то самое место, где имеет место быть оптимизация алгоритма: он считывает до 1000 int'ов за раз, выдавая их по одному. Вначале я не использовал буферизацию — функция просто считывала 4 байта из файла, преобразовывала в целое и возвращала. Но это работало в 4 раза медленнее! Обратите внимание, что мы не можем использовать a.fromfile(f, 1000), так как метод fromfile() вернет ошибку, если в файле недостаточно данных, а я хотел, чтобы код сам адаптировался к любому количеству int'ов в файле.

    Далее следует цикл ввода. Он циклически считывает кусок из 10'000 int'ов из входного файла, сортирует их в памяти и записывает во временный файл. Затем мы добавим итератор для временного файла в список итераторов, который понадобится нам на заключительном этапе, используя описанную выше функцию intsfromfile().

    Copy Source | Copy HTML
    1. iters = []
    2. while True:
    3.  a = array.array('i')
    4.  a.fromstring(sys.stdin.buffer.read(40000))
    5.  if not a:
    6.      break
    7.  f = tempfile.TemporaryFile()
    8.  array.array('i', sorted(a)).tofile(f)
    9.  f.seek(0)
    10.  iters.append(intsfromfile(f))

    Соответственно, для входного миллиона int'ов будет создано 100 временных файлов по 10'000 значений в каждом.

    Наконец, мы объединяем все эти файлы (каждый из них уже отсортирован) вместе. Модуль heapq содержит замечательную функцию для решения этой задачи: heapq.merge(iter1, iter2, ... ), возвращающую итератор, который пропускает входные параметры в такой последовательности, при которой каждый входной параметр сам передает свое значение в нужном порядке (как в данном случае).

    Copy Source | Copy HTML
    1. a = array.array('i')
    2. for x in heapq.merge(*iters):
    3.  a.append(x)
    4.  if len(a) >= 1000:
    5.      a.tofile(sys.stdout.buffer)
    6.      del a[:]
    7. if a:
    8.  a.tofile(sys.stdout.buffer)

    Это еще один случай, при котором буферизированный ввод\вывод оказывается необходимым: запись каждого отдельного значения в файл, как только оно становится доступным, снижает темп работы алгоритма вдвое. Используя буферизацию на входе и выходе, нам удалось увеличить скорость выполнения в 10 раз!
    Метки:
    Поделиться публикацией
    Похожие публикации
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 60
    • –1
      спасибо. интересно было почитать.
      • +2
        проникся) тяжеловато, конечно, для кропотливого анализа… особенно в понедельник вечером)
        • –4
          использовать фаил как-то не кошерно, интересно сжать массив в памяти в питоне можно?
          • 0
            Сжимать не нужно. В данном случае можно еще ускориться используя bin/bucket/postman алгоритмы — тогда в конце слияние фактически не нужно будет делать в том виде, как это делает merge — достаточно будет просто склеить файлы. Если быть особенным извращенцем, то большой файл можно склеить из кусочков минуя чтение и запись — тупо объединив иноды, кластеры (или еще че в зависимости от FS) в один файл напрямую редактируя FS :)

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

            А если вникнуть глубже в задачу, то можно специализировать алгоритм на тип данных, что может привести к тому, что в кусках, которые получаются после предварительной псевдо-сортировки, уже можно сравнивать даже не все 32 бита, а только половину, поскольку, например, старшие два байта в куске у всех чисел могут быть одинаковы :) +SMP, GPGPU и т.п. Пространства для оптимизации весьма и весьма много.
            • 0
              В переводе написано «2 мегабайтах памяти на Питон» и получается что автор просто из оперативной памяти перекинул на жесткий диск, что кажется нарушением условий задачи, в оригинале же же неоднозначности нет «in 2 megabytes of RAM».
              • 0
                ну где-то же должны лежать эти числа до сортировки и после сортировки
                можно было бы усложнить решение условием, что суммарный объём оперативной памяти и создаваемых файлов не должен превышать двух мегабайт, но это тоже решаемо
          • 0
            Н. Вирт «Алгоритмы + Структуры данных = Программы» ;)
            • +5
              Вот интересно тут сделать раздел, в котором классические алгоритмы будут реализовываться энтузиастами на разных языках программирования. Это был-бы отличный (от холивара :) ) способ померяться сравнить элегантность реализации того или иного алгоритма на разных языках.
              • 0
                Идея очень неплохая, было бы интересно почитать грамотный код на разных языках. Глядишь и выучить что-то новое захочется)

                Думаю стоит написать статью для затравки, например про реализации каких-нибудь сбалансированных деревьев
                • НЛО прилетело и опубликовало эту надпись здесь
                  • НЛО прилетело и опубликовало эту надпись здесь
                    • 0
                      Только тяжело будет Хаскелю в даже 4 мегабайтах
                      • НЛО прилетело и опубликовало эту надпись здесь
              • +3
                Сорри, я не знаю питон, но по описанию алгоритма видится мне что сортируются отдельные файлы (куски исходного) в адресном пространстве оного (т.е по 10 000 интов), и выплевываются в временный файл, но записи уже хранящиеся в временных файла никак не увязанны между собой… ну и какая же это сортировка тогда?
                поправьте если я не прав…
                • 0
                  В данном случае heapq.merge возвращает итератор, который позволит читать из потоков отсортированных файлов в нужном порядке, сбрасывая по 1000 штук в конечный файл.
                  • –1
                    ну так это тогда имхо совсем не решение задачи, т.к. система все равно даст один из вариантов:
                    1. Подгрузит эти данные в память от имени другого процесса и объем памяти при выполнении далеко привысит поставленный в задаче
                    2. она будет делать кучу операций чтения/записи, что сильно замедлит работу процесса…
                    или я не понял исходной задачи?
                    сорри — просто самому интересно стало каким образом тут все происходит… может быть если в вышесказанном я не прав, то опишите подробнее алгоритм?
                    • 0
                      Кэширование дисковых операций — это необязательное выделение памяти. т.е. она выделится только если есть свободная, но в принципе будет работать и без неё (чего не скажешь о выделении памяти под буфер для сортировки самой программой). А производительность алгоритма в условиях задачи не озвучена ;)
                      • 0
                        В Питоне есть такая штука, как генератор. В общих чертах, это такая последовательность, члены которой вычисляются тогда, когда к ним обращаются. Обратите внимание на оператор yield.
                        • НЛО прилетело и опубликовало эту надпись здесь
                        • 0
                          Это функция не подгружает все значения в память сразу, а будет грузить поочереди. В том и задача, чтоб не забить 2 мегабайта памяти сразу. Да, операций чтения будет достаточно много, но задача минимальной работы с диском и не требует.
                      • 0
                        В 23 строке данные из временных файлов загружаются в iters, а в 26 происходит слияние.
                      • –5
                        зачем каверкать русский язык?
                        int'ов — чисел
                        • +6
                          Я думаю, тут имелся ввиду типа данных.
                          • +2
                            «число» — понятие растяжимое. Оно может быть и 8 и 128 битным. Вот например я не вижу ничего сложного в сортировке миллиона 8-ми битных чисел в оперативной памяти т.к. они будут занимать 1Mb а по условию задачи нам выделяется 2.
                            Автор же имел ввиду тип int — 32-х битное целое. Миллион таких чесел «весит» 4Mb и без дополнительных ухищрений их в оперативной памяти не отсортировать ибо не влезут)
                            • –4
                              в заголовке и названии статьи — норм. В середине везде — не норм.

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

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

                                  прекратите смотреть на все что видите с точки зрения разработчика — это переводится просто «он считывает до 1000 чисел за раз». Всё. Никаких тут 32-битных int'ов и прочих вещей.
                                  • 0
                                    А с какой точки зрения нужно смотреть? Химика-генетика?
                                    Статья имеет явно выраженный программистский контекст. А в этом контексте перевод «1000 чисел за раз» — некорректен.
                                    • –3
                                      Эхехе. int — не число что ли? LOL
                                      • 0
                                        Боюсь, я сейчас сломаю Вашу картину мира, но числа бывают не только целые. Более того: целые числа бывают не только int. Надеюсь, это было не очень больно…

                                        Возвращаясь к вопросу: разумеется, int — это число. Но переводить «1000 integers» как «1000 чисел» — неверно. Вот такой, панимашь, парадокс.
                                        • 0
                                          > но числа бывают не только целые. Более того: целые числа бывают не только int.

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

                                          «1000 integers» — тысяча целых чисел (учел ошибку), ну никак не 1000 int'ов (фффуу. кстати, раз уж занудствуем, int'ы бывают не только 32-х битные)
                                          • +1
                                            Ну вот, уже лучше. Не просто «1000 чисел», а «1000 целых чисел».
                                            А если быть ещё точнее, то «1000 целых 32-битных чисел» (о чём и идёт речь в статье). Автором подразумевалось именно это (ибо статья как раз об этом).
                                            А т.к. статья написана программистом для программистов, то «программизм» «1000 int'ов» там более чем уместен, т.к. не оставляет двусмысленностей и лаконично доносит смысл. В отличие от «1000 чисел», которое вызывает кучу вопросов: «каких чисел?», «какой точности?» и т.д.
                                  • –1
                                    зануда
                              • 0
                                я думаю просто Василий поленился переводить) имелись ввиду целые числа…
                                • +2
                                  Действительно, незачем — лучше уж писать англицизмы, чем коверкать русский язык.
                                • 0
                                  В данном случае heapq.merge возвращает итератор, который позволит читать из потоков отсортированных файлов в нужном порядке, сбрасывая по 1000 штук в конечный файл.
                                  • +1
                                    Извините, не туда написал.
                                    • НЛО прилетело и опубликовало эту надпись здесь
                                  • +1
                                    «100 жемчужин программирования»- первая задача, о сортировки при условии что в объем данных превышает объем доступной памяти.
                                    • НЛО прилетело и опубликовало эту надпись здесь
                                      • 0
                                        Ничего что второй файл будет размером… я даже не назову сходу такой приставки, для 10^15 байт:)
                                        • 0
                                          Петабайт.
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                            • +1
                                              Так вы же предлагаете во втором файле для каждого возможного значения иметь по соответствующему сдвигу количество таких чисел. Возможных значений 2^32, на количество надо по крайней мере 3 байта, итого имеем размер 12 гигабайт. Для такой задачи многовато, да и затраты по времени чтения/записи такого файла будут гигантскими
                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                • НЛО прилетело и опубликовало эту надпись здесь
                                              • +1
                                                «Тоже» — это как Вы? Надеюсь, что нет:)

                                                Расскажите-ка про свой алгоритм. Посмотрим, сколько Вам места понадобится…
                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                  • +1
                                                    Ага, уже 12 гигабайт:) Несколько больше 4 Мб, не так ли?

                                                    С петабайтом я ошибся, признаю. Но и 12 гигабайт приемлемыми назвать никак нельзя. И да, _в таком случае_ лучше «городить сотню файлов».
                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                      • –1
                                                        Вы тоже ненормальный? Я с самого начала говорил про Ваш второй файл. Перечитайте хистори.
                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                          • –1
                                                            habrahabr.ru/blogs/python/65503/#comment_1836028 — на мой вопрос о втором файле Вы начали гнать про 4 мегабайта _в первом_.

                                                            Идите уже, почитайте что-нибудь другое. Всё с Вами понятно.
                                          • 0
                                            существует типовое решение для сортировки, когда объем намного превышает RAM — четырехленточная сортировка.
                                            • 0
                                              Погуглил — не нашел, помогите
                                              • 0
                                                en.wikipedia.org/wiki/Merge_sort раздел Merge sorting tape drives
                                                • 0
                                                  А, ну так это называется сортировка слиянием
                                                  • 0
                                                    Да, она, просто модифицированный вариант, рассчитанный на компьютеры с малой памятью
                                            • 0
                                              Гвидо там еще написал, что нужно молиться на heapq.merge, чем и собираюсь теперь заняться после прочтения оригинала.
                                              • –1
                                                Не очень наглядный пример) Вот если хотя бы 100 миллионов целых чисел.

                                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.