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

[institoris]

Почему в формуле выбора размера Вы используете «2**3», а не «8»? Есть какая-то скрытая причина?

[rushter]

Можно упростить, да, просто в оригинале (на C) там вообще используется сдвиг 1 << 3, я его как-то машинально сконвертировал в 2**3.

[YourChief]

BTW, аналогом 1<<3 в Си на питоне будет 1<<3.

In [1]: 1<<3
Out[1]: 8

[rushter]

Будет, вот только зачастую, люди не связанные с низкоуровневыми языками, не могут быстро сообразить ответ. Редко пригождается и зачастую не даёт прибавки по скорости.

[rstm-sf]

Да и в питоне не все так просто, например.

[sshikov]

>Самая известная разница между ними состоит в том, что кортежи неизменяемы.
Вообще, кортежи это не изобретение питона, они скорее из реляционного исчисления или из математики. И для них характерно то, что элемент i принадлежит домену i. Т.е. типы элементов разные, и известны заранее, как и их количество. Для списка же все наоборот.

А вот то, что в питоне они immutable, это кажется все-таки особенность реализации, и в общем-то, наверное не является даже их обязательным свойством.

[geisha]

А вот то, что в питоне они 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'

[anjensan]

Просто у 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']}

[geisha]

Это весьма годное и правильно решение, но не единственно возможное.

Я настаивал именно на правильности и годности. Определить можно всё, что угодно, особенно когда речь идёт о питоне. Имеет ли это определение смысл — вопрос.

>>> 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

[anjensan]

Я с вами согласен, иммутабельность кортежей в 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

[geisha]

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

Да, но, опять же, в питоне много чего можно. С одной стороны, ты пользуешь фичи ООП, а, с другой стороны, тебе прямо говорят, что так делать не стоит:

Fraction instances are hashable, and should be treated as immutable.

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

[anjensan]

В сях, как я понял, это связано с другим свойством, гомогенностью.

Наверное вы имел в виду гетерогенность, это списки гомогенные. И нет, мутабельность кортежей в C++ с этим не связана.

[sshikov]

Так с полезностью никто и не спорит. Я про другое слегка.

[rushter]

Список сначала создается пустым, а уже потом туда добавляется элемент. Вы можете посмотреть байткод данного выражения или убедится что 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

[3apa3ka3]

у меня тоже как то не сошлось:

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

[rushter]

Лучше использовать стандартный REPL питона для таких тестов, IPython слишком умный. Пока вы печайте код он сам много всяких внутренних стуктур создает и мог перехватить свободный кортеж раньше. Особенно когда вы автодополнение используйте.

Я эти оптимизации не из головы взял, а в коде CPython подсмотрел, поэтому они точно существуют. github.com/python/cpython/blob/e271ca78e37a502b3dc1036f824aa3999efcd56b/Objects/tupleobject.c#L79

[3apa3ka3]

да все верно, немного поторопился с IPython, в чистой консоли питона все хорошо.

[Varim]

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

Почему заняты будут 9 а не 8? Я Python не знаю.

[sormon]

Ну есть же уже 8 элементов, добавляем еще 1, получаем список из 9 элементов.
А про расширение и алгоритм, рекомендую почитать www.laurentluce.com/posts/python-list-implementation

[Varim]

Да. Я криво прочитал.

[mk2]

Расширение размера списка в n раз, когда заканчивается место — это совсем не особенность Python. Так работают вообще все списки, которые хранят элементы непрерывно в памяти.

[trapwalker]

Автору ещё бы рассказать насколько эффективно в питоне добавлять элементы в начало и в середину списка.

[rushter]

В начало будет дольше всех, питон от нужного индекса все элементы справа двигает на один шаг в право обычным циклом.

[geisha]

Автору ещё бы рассказать насколько эффективно в питоне добавлять элементы в начало и в середину списка.

Это был сарказм? Я недавно слушал доклад о модных структурах в сях (конечно, их есть не только в сях): trees и тому прочее. Оказалось, что все эти сферические преимущества типа вставить элемент за O(log(N)), а потом найти его за тот же O(log(N)) работают только в вакууме (читай: только когда программа со всеми данными помещается в кэше процессора). Если идёт поиск по дереву или, не дай Б-г, по linked list — на каждом шаге тратится куча тактов только на то, чтобы подгрузить очередной кусок оперативной памяти.

Просто к слову пришлось.

[trapwalker]

Ну почему только в вакууме? Не только. Всё относительно. Вопрос в том, какие N и каков масштабный коэффициент обработки одного элемента. Если в дереве хранить ссылки на данные в медленном хранилище, то обработать O(N) или O(N^2) может занять часы, против секунд или миллисекунд. Замечательное тому подтверждение — индексы в реляционных БД. При неправильно составленном плане сложный запрос с джойнами может работать сутками, а логарифмический доступ в правильном порядке решит вопрос за миллисекунды. Были такие случаи в личной практике. При этом на маленьких наборах (читай при сдаче проекта, когда не набралось много данных) всё на тех же запросах работает и не вызывает ощущения дискомфорта.

[machspeed]

Спасибо.
Побольше бы такой информации, которую не встретишь в обычных учебниках.

[ShashkovS]

Что-то я много раз проверял, и какой-то значимой разницы между временем работы кортежей и списков не обнаруживал. Вот написал ещё один тест.
В нём списки/кортежи генерируются из 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()