Оптимизации, используемые в Python: список и кортеж

Автор оригинала: Artem Golubin
  • Перевод
В Python, есть два похожих типа — список (list) и кортеж (tuple). Самая известная разница между ними состоит в том, что кортежи неизменяемы.

Вы не можете изменить объекты в tuple:

>>> a = (1,2,3)
>>> a[0] = 10
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

Но вы можете модифицировать изменяемые объекты внутри кортежа:

>>> b = (1,[1,2,3],3)
>>> b[1]
[1, 2, 3]
>>> b[1].append(4)
>>> b
(1, [1, 2, 3, 4], 3)

Внутри CPython (стандартного интерпретатора), список и кортеж реализованы как лист из указателей (ссылок) на Python объекты, т.е. физически они не хранят объекты рядом с друг другом. Когда вы удаляете объект из списка происходит удаление ссылки на этот объект. Если на объект ещё кто-то ссылается, то он продолжит находиться в памяти.

Кортежи


Несмотря на тот факт, что кортежи намного реже встречаются в коде и не так популярны, это очень фундаментальный тип, который Python постоянно использует для внутренних целей.

Вы можете не замечать, но вы используете кортежи когда:

  • работаете с аргументами или параметрами (они хранятся как кортежи)
  • возвращаете две или более переменных из функции
  • итерируете ключи-значения в словаре
  • используете форматирование строк

Как правило, самый просто скрипт использует тысячи кортежей:

>>> import gc
>>> def type_stats(type_obj):
...     count = 0
...     for obj in gc.get_objects():
...         if type(obj) == type_obj:
...             count += 1
...     return count
...
>>> type_stats(tuple)
3136
>>> type_stats(list)
659
>>> import pandas
>>> type_stats(tuple)
6953
>>> type_stats(list)
2455

Пустые списки vs пустые кортежи


Пустой кортеж работает как синглтон, т.е. в памяти запущенного Python скрипта всегда находится только один пустой кортеж. Все пустые кортежи просто ссылаются на один и тот же объект, это возможно благодаря тому, что кортежи неизменяемы. Такой подход сохраняет много памяти и ускоряет процесс работы с пустыми кортежами.

>>> a = ()
>>> b = ()
>>> a is b
True
>>> id(a)
4409020488
>>> id(b)
4409020488
>>> # В CPython, функция id возвращает адрес в памяти.

Но это не работает со списками, ведь они могут быть изменены:

>>> a = []
>>> b = []
>>> a is b
False
>>> id(a)
4465566920
>>> id(b)
4465370632

Оптимизация выделения памяти для кортежей


Для того, чтобы снизить фрагментацию памяти и ускорить создание кортежей, Python переиспользует старые кортежи, которые были удалены. Если кортеж состоит из менее чем 20 элементов и больше не используется, то вместо удаления Python помещает его в специальный список, в котором хранятся свободные для повторного использования кортежи.

Этот список разделен на 20 групп, где каждая группа представляет из себя список кортежей размера n, где n от 0 до 20. Каждая группа может хранить до 2 000 свободных кортежей. Первая группа хранит только один элемент и представляет из себя список из одного пустого кортежа.

>>> a = (1,2,3)
>>> id(a)
4427578104
>>> del a
>>> b = (1,2,4)
>>> id(b)
4427578104

В примере выше, мы можем видеть, что a и b имеют одинаковый адрес в памяти. Это происходит из-за того, что мы мгновенно заняли свободный кортеж такого же размера.

Оптимизация выделения памяти для списков


Так как списки могут изменяться, такую же оптимизацию как в случае с кортежами провернуть уже не получится. Несмотря на это, для списков используется похожая оптимизация нацеленная на пустые списки. Если пустой список удаляется, то он так же может быть переиспользован в дальнейшем.

>>> a = []
>>> id(a)
4465566792
>>> del a
>>> b = []
>>> id(b)
4465566792

Изменение размера списка


Чтобы избежать накладные расходы на постоянное изменение размера списков, Python не изменяет его размер каждый раз, как только это требуется. Вместо этого, в каждом списке есть набор дополнительных ячеек, которые скрыты для пользователя, но в дальнейшем могут быть использованы для новых элементов. Как только скрытые ячейки заканчиваются, Python добавляет дополнительное место под новые элементы. Причём делает это с хорошим запасом, количество скрытых ячеек выбирается на основе текущего размера списка — чем он больше, тем больше дополнительных скрытых слотов под новые элементы.

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

Паттерн роста размера списка выглядит примерно так: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88,…

Для примера, если вы хотите добавить новый элемент в список с 8 элементами, то свободных ячеек в нём уже не будет и Python сразу расширит его размер до 16 ячеек, где 9 из них будут заняты и видны пользователю.

Формула выбора размера написанная на Python:

>>> def get_new_size(n_items):
...     new_size = n_items + (n_items // 2 ** 3)
...     if n_items < 9:
...             new_size += 3
...     else:
...             new_size += 6
...
...     return new_size
...
>>> get_new_size(9)
16

Скорость


Если сравнивать эти два типа по скорости, то в среднем по больнице, кортежи слегка быстрее списков. У Raymond Hettinger есть отличное объяснение разницы в скорости на stackoverflow.

P.S.: Я являюсь автором этой статьи, можете задавать любые вопросы.
Поделиться публикацией

Похожие публикации

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 28

    +1
    Почему в формуле выбора размера Вы используете «2**3», а не «8»? Есть какая-то скрытая причина?
      0
      Можно упростить, да, просто в оригинале (на C) там вообще используется сдвиг 1 << 3, я его как-то машинально сконвертировал в 2**3.
        +3
        BTW, аналогом 1<<3 в Си на питоне будет 1<<3.
        In [1]: 1<<3
        Out[1]: 8
        
          +4
          Будет, вот только зачастую, люди не связанные с низкоуровневыми языками, не могут быстро сообразить ответ. Редко пригождается и зачастую не даёт прибавки по скорости.
    +2
    >Самая известная разница между ними состоит в том, что кортежи неизменяемы.
    Вообще, кортежи это не изобретение питона, они скорее из реляционного исчисления или из математики. И для них характерно то, что элемент i принадлежит домену i. Т.е. типы элементов разные, и известны заранее, как и их количество. Для списка же все наоборот.

    А вот то, что в питоне они immutable, это кажется все-таки особенность реализации, и в общем-то, наверное не является даже их обязательным свойством.
      –1
      А вот то, что в питоне они immutable, это кажется все-таки особенность реализации, и в общем-то, наверное не является даже их обязательным свойством.
      Свойство полезное настолько, что почти обязательное:
      >>> some_set = {(1, 'one'), (2, 'two')}
      >>> (1, 'one') in some_set
      True
      >>> another_set = {[1, 'one'], [2, 'two']}
      Traceback (most recent call last):
        File "<stdin>", line 1, in <module>
      TypeError: unhashable type: 'list'
      
        +1
        Просто у tuple определен __hash__, а у list нет.
        Это весьма годное и правильно решение, но не единственно возможное.
        class hlist(list):
            def __hash__(self): return hash(tuple(self))
        
        >>> another_set = {hlist([1, 'one']), hlist([2, 'two'])}
        >>> another_set 
        {[1, 'one'], [2, 'two']}
        

          0
          Это весьма годное и правильно решение, но не единственно возможное.
          Я настаивал именно на правильности и годности. Определить можно всё, что угодно, особенно когда речь идёт о питоне. Имеет ли это определение смысл — вопрос.
          >>> for i in another_set:
          ...     print "before:", i in another_set
          ...     i[0] = 3
          ...     print "after:", i in another_set
          ... 
          before: True
          after: False
          before: True
          after: False
          
            +1
            Я с вами согласен, иммутабельность кортежей в Python — крайне важная фишка.
            Но и sshikov прав, говоря что иммутабельность не является характеристикой кортежей самих по себе. Есть языки, в которых кортежи мутабельны (например std::tuple в C++).

            С вашим примером согласен, но опять же а) есть языки, где мутабельные списки хешабельны; b) в Python полно объектов с __hash__, которые на самом деле можно мутировать (если захотеть себе палок в колеса).
            Например fractions.Fraction технически мутабельный
            >>> from fractions import Fraction
            >>> s = {Fraction(1, 3), Fraction(1, 5)}
            >>> for x in s:
            ...  print("before:", x in s)
            ...  x._denominator += 1  
            ...  print("after:", x in s)
            ... 
            before: True
            after: False
            before: True
            after: False

              0
              в Python полно объектов с __hash__, которые на самом деле можно мутировать (если захотеть себе палок в колеса).

              Да, но, опять же, в питоне много чего можно. С одной стороны, ты пользуешь фичи ООП, а, с другой стороны, тебе прямо говорят, что так делать не стоит:
              Fraction instances are hashable, and should be treated as immutable.

              Т.е. за всех разработчиков не скажу, но, по крайней мере, те, кто писал документацию для fractions, прямо связывают immutable с __hash__. Вообще, возвращаясь к оригинальному комментарию, для меня (пишу на питоне) разница между кортежами и списками — это именно immutable. В сях, как я понял, это связано с другим свойством, гомогенностью.
                0
                В сях, как я понял, это связано с другим свойством, гомогенностью.
                Наверное вы имел в виду гетерогенность, это списки гомогенные. И нет, мутабельность кортежей в C++ с этим не связана.
          0
          Так с полезностью никто и не спорит. Я про другое слегка.
        +1
        Оптимизация выделения памяти для списков.

        a = []
        id(a)
        >>> 12147008
        del(a)
        b = [1]
        id(b)
        >>> 12147008

        Тут дело явно не в пустых списках.
          +1
          Список сначала создается пустым, а уже потом туда добавляется элемент. Вы можете посмотреть байткод данного выражения или убедится что CPython переиспользует пыстые списки в его исходниках :)

          In [3]: def test():
             ...:     a = [1,]
             ...:
          
          In [4]: dis.dis(test)
            2           0 LOAD_CONST               1 (1)
                        2 BUILD_LIST               1
                        4 STORE_FAST               0 (a)
                        6 LOAD_CONST               0 (None)
                        8 RETURN_VALUE
          
            0
            у меня тоже как то не сошлось:
            Python 3.7.0 (default, Jul  4 2018, 20:22:06) 
            Type 'copyright', 'credits' or 'license' for more information
            IPython 6.4.0 -- An enhanced Interactive Python. Type '?' for help.
            
            In [1]: a = (1,2,3)
            
            In [2]: id(a)
            Out[2]: 139724211253896
            
            In [3]: del a
            
            In [4]: b = (1,2,4)
            
            In [5]: id(b)
            Out[5]: 139724211206904
              +3
              Лучше использовать стандартный REPL питона для таких тестов, IPython слишком умный. Пока вы печайте код он сам много всяких внутренних стуктур создает и мог перехватить свободный кортеж раньше. Особенно когда вы автодополнение используйте.

              Я эти оптимизации не из головы взял, а в коде CPython подсмотрел, поэтому они точно существуют. github.com/python/cpython/blob/e271ca78e37a502b3dc1036f824aa3999efcd56b/Objects/tupleobject.c#L79
                0
                да все верно, немного поторопился с IPython, в чистой консоли питона все хорошо.
          0
          Для примера, если вы хотите добавить новый элемент в список с 8 элементами, то свободных ячеек в нём уже не будет и Python сразу расширит его размер до 16 ячеек, где 9 из них будут заняты и видны пользователю.
          Почему заняты будут 9 а не 8? Я Python не знаю.
            +2
            Ну есть же уже 8 элементов, добавляем еще 1, получаем список из 9 элементов.
            А про расширение и алгоритм, рекомендую почитать www.laurentluce.com/posts/python-list-implementation
              0
              Да. Я криво прочитал.
            +5
            Расширение размера списка в n раз, когда заканчивается место — это совсем не особенность Python. Так работают вообще все списки, которые хранят элементы непрерывно в памяти.
              0
              Автору ещё бы рассказать насколько эффективно в питоне добавлять элементы в начало и в середину списка.
                –1
                В начало будет дольше всех, питон от нужного индекса все элементы справа двигает на один шаг в право обычным циклом.
                  –1
                  Автору ещё бы рассказать насколько эффективно в питоне добавлять элементы в начало и в середину списка.
                  Это был сарказм? Я недавно слушал доклад о модных структурах в сях (конечно, их есть не только в сях): trees и тому прочее. Оказалось, что все эти сферические преимущества типа вставить элемент за O(log(N)), а потом найти его за тот же O(log(N)) работают только в вакууме (читай: только когда программа со всеми данными помещается в кэше процессора). Если идёт поиск по дереву или, не дай Б-г, по linked list — на каждом шаге тратится куча тактов только на то, чтобы подгрузить очередной кусок оперативной памяти.

                  Просто к слову пришлось.
                    +2
                    Ну почему только в вакууме? Не только. Всё относительно. Вопрос в том, какие N и каков масштабный коэффициент обработки одного элемента. Если в дереве хранить ссылки на данные в медленном хранилище, то обработать O(N) или O(N^2) может занять часы, против секунд или миллисекунд. Замечательное тому подтверждение — индексы в реляционных БД. При неправильно составленном плане сложный запрос с джойнами может работать сутками, а логарифмический доступ в правильном порядке решит вопрос за миллисекунды. Были такие случаи в личной практике. При этом на маленьких наборах (читай при сдаче проекта, когда не набралось много данных) всё на тех же запросах работает и не вызывает ощущения дискомфорта.
                +2
                Спасибо.
                Побольше бы такой информации, которую не встретишь в обычных учебниках.
                  0
                  Что-то я много раз проверял, и какой-то значимой разницы между временем работы кортежей и списков не обнаруживал. Вот написал ещё один тест.
                  В нём списки/кортежи генерируются из 1000000 строчек с числами, после чего в случайном порядке вычитываются все элементы списка/кортежа, потом читаются 3 элемента с фиксированными индексами.
                  Вот результат:
                  Num tests: 1000000, total numbers: 128524778, avg: 128.524778, median: 20, std: 269.0942898722472
                  Dummy. Crt:5.29, read:2.38, read fixed:0.0622, tot:7.73
                  Tuples. Crt:29.7, read:4.88, read fixed:0.108, tot:34.7
                  Lists. Crt:29.4, read:4.58, read fixed:0.106, tot:34.0
                  One run more
                  Dummy. Crt:8.35, read:2.63, read fixed:0.0704, tot:11.0
                  Lists. Crt:28.3, read:4.4, read fixed:0.102, tot:32.8
                  Tuples. Crt:29.2, read:4.79, read fixed:0.105, tot:34.1


                  Вот код для python 3.7
                  try:
                      from time import perf_counter_ns
                      dv = 1e9
                  except ImportError:
                      print('Use python 3.7!')
                      from time import perf_counter as perf_counter_ns
                      dv = 1
                  import random
                  
                  
                  def gen_test():
                      NTESTS = 1000000
                      LENS = list(range(11)) + [15, 20, 25, 35, 55, 75, 100, 300, 1000]
                      WEIGHTS = [100] * 11 + [100] * 4 + [200] * 2 + [200] * 3
                      assert len(LENS) == len(WEIGHTS)
                      tests = []
                      for __ in range(NTESTS):
                          l = random.choices(population=LENS, weights=WEIGHTS)[0]
                          data = ' '.join(str(random.randint(0, 10 ** 9)) for __ in range(l))  # Данные, которые будем писать
                          checks = list(range(l))  # Индексы, которые будем читать
                          random.shuffle(checks)
                          tests.append((data, checks))
                      return tests
                  
                  
                  def prt_test_stats(tests):
                      tests_lens = [len(tst[0].split()) for tst in tests]
                      tests_lens.sort()
                      avg = sum(tests_lens)/len(tests_lens)
                      median = tests_lens[len(tests_lens)//2]
                      std = (sum((l-avg)**2 for l in tests_lens)/(len(tests_lens) - 1))**.5
                      print(f'Num tests: {len(tests)}, total numbers: {sum(tests_lens)}, avg: {avg}, median: {median}, std: {std}')
                  
                  
                  def test_tuple(tests, tm=perf_counter_ns):
                      dur_crt = 0
                      dur_read = 0
                      dur_read_fixed = 0
                      for data, checks in tests:
                          t1 = tm()
                          row = tuple(map(int, data.split()))
                          t2 = tm()
                          for ind in checks:
                              val = row[ind]
                          t3 = tm()
                          if len(row) > 10:
                              t4 = tm()
                              val = row[1]
                              val = row[7]
                              val = row[0]
                              t5 = tm()
                              dur_read_fixed += t5 - t4
                          dur_crt += t2 - t1
                          dur_read += t3 - t2
                      return dur_crt, dur_read, dur_read_fixed
                  
                  
                  def test_list(tests, tm=perf_counter_ns):
                      dur_crt = 0
                      dur_read = 0
                      dur_read_fixed = 0
                      for data, checks in tests:
                          t1 = tm()
                          row = list(map(int, data.split()))
                          t2 = tm()
                          for ind in checks:
                              val = row[ind]
                          t3 = tm()
                          if len(row) > 10:
                              t4 = tm()
                              val = row[1]
                              val = row[7]
                              val = row[0]
                              t5 = tm()
                              dur_read_fixed += t5 - t4
                          dur_crt += t2 - t1
                          dur_read += t3 - t2
                      return dur_crt, dur_read, dur_read_fixed
                  
                  
                  def test_dummy(tests, tm=perf_counter_ns):
                      dur_crt = 0
                      dur_read = 0
                      dur_read_fixed = 0
                      for data, checks in tests:
                          t1 = tm()
                          row = data.split()
                          t2 = tm()
                          for ind in checks:
                              val = ind
                          t3 = tm()
                          if len(row) > 10:
                              t4 = tm()
                              val = 1
                              val = 7
                              val = 0
                              t5 = tm()
                              dur_read_fixed += t5 - t4
                          dur_crt += t2 - t1
                          dur_read += t3 - t2
                      return dur_crt, dur_read, dur_read_fixed
                  
                  
                  tests = gen_test()
                  prt_test_stats(tests)
                  
                  dur_crt, dur_read, dur_read_fixed = test_dummy(tests)
                  print(f'Dummy. Crt:{dur_crt/dv:0.3}, read:{dur_read/dv:0.3}, read fixed:{dur_read_fixed/dv:0.3}, tot:{(dur_crt+dur_read+dur_read_fixed)/dv:0.3}')
                  dur_crt, dur_read, dur_read_fixed = test_tuple(tests)
                  print(f'Tuples. Crt:{dur_crt/dv:0.3}, read:{dur_read/dv:0.3}, read fixed:{dur_read_fixed/dv:0.3}, tot:{(dur_crt+dur_read+dur_read_fixed)/dv:0.3}')
                  dur_crt, dur_read, dur_read_fixed = test_list(tests)
                  print(f'Lists. Crt:{dur_crt/dv:0.3}, read:{dur_read/dv:0.3}, read fixed:{dur_read_fixed/dv:0.3}, tot:{(dur_crt+dur_read+dur_read_fixed)/dv:0.3}')
                  
                  print(f'One run more')
                  
                  dur_crt, dur_read, dur_read_fixed = test_dummy(tests)
                  print(f'Dummy. Crt:{dur_crt/dv:0.3}, read:{dur_read/dv:0.3}, read fixed:{dur_read_fixed/dv:0.3}, tot:{(dur_crt+dur_read+dur_read_fixed)/dv:0.3}')
                  dur_crt, dur_read, dur_read_fixed = test_list(tests)
                  print(f'Lists. Crt:{dur_crt/dv:0.3}, read:{dur_read/dv:0.3}, read fixed:{dur_read_fixed/dv:0.3}, tot:{(dur_crt+dur_read+dur_read_fixed)/dv:0.3}')
                  dur_crt, dur_read, dur_read_fixed = test_tuple(tests)
                  print(f'Tuples. Crt:{dur_crt/dv:0.3}, read:{dur_read/dv:0.3}, read fixed:{dur_read_fixed/dv:0.3}, tot:{(dur_crt+dur_read+dur_read_fixed)/dv:0.3}')
                  



                  ИМХО при выборе список/кортеж нужно использовать только следующие соображения:
                  1. Если нужно использовать как ключ словаря/элемент множества, то только кортеж, без вариантов;
                  2. Если нужно добавлять/удалять элементы, или менять элементы внутри, то список, без вариантов;
                  3. Если внутри есть разнородные данные (то есть смысл элементов индексом i и индексом j может различаться, например ('Ivanov', 5)), то используем кортеж;
                  4. Если данные однородные, то используем список.

                  В контексте пп.3-4 тип как бы намекает:
                  если список, то он так и просит одинаковой обработки разных элементов:
                  
                  for el in my_list:
                     pass
                  

                  а если кортеж, то он так и просит чего-нибудь в духе
                  
                  name, result, __, __, __, email = my_tuple()
                  

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

                  Самое читаемое