27 июля 2009 в 18:44

Сортировка миллиона 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 раз!
Василий @spe
карма
54,0
рейтинг 0,0
Пользователь
Похожие публикации
Самое читаемое Разработка

Комментарии (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 миллионов целых чисел.

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