Словари¶

Второй основной структурой данных в Python является словарь. Как вы наверное помните, словари отличаются от списков тем, что в них доступ к элементу получают по ключу, а не по позиции. Позднее в этой книге вы увидите множество способов реализации словаря. Сейчас же наиболее важно отметить, что операции получения и записи элемента в словарь имеют \(O(1)\). Другой важной операцией со словарями является определение принадлежности ему элемента. Проверка, есть ли с словаре данный ключ или нет, тоже \(O(1)\). Эффективности всех операций над словарями собраны в таблице 3. Важное замечание в сторону относительно производительности словарей: эффективности, которые мы предоставляем в таблице, - это усреднённая производительность. В редких случаях принадлежность, получение или запись элемента могут деградировать до \(O(n)\). Мы встретимся с этим в одной из последующих глав, когда будем говорить о различных способах, которыми можно реализовать словарь.

В нашем последнем эксперименте с производительностью мы сравним эффективность операций принадлежности у списков и словарей. В процессе мы подтвердим, что оператор принадлежности для списков имеет \(O(n)\), а для словарей - \(O(1)\). Производить сравнение будем просто: создадим список с диапазоном чисел, затем будем брать их по одному случайным образом и смотреть, есть ли такая величина в списке. Если таблица производительности верна, то чем больше список, тем дольше будет происходить определение, содержится ли в нём данное число.

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

Листинг 6 реализовывает это сравнение. Заметьте, что мы выполняем в точности одинаковые операции number in container. Различие только в том, что в седьмой строке x - это список, а в девятой - словарь.

Листинг 6

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import timeit
import random

for i in range(10000,1000001,20000):
    t = timeit.Timer("random.randrange(%d) in x"%i,
                     "from __main__ import random,x")
    x = list(range(i))
    lst_time = t.timeit(number=1000)
    x = {j:None for j in range(i)}
    d_time = t.timeit(number=1000)
    print("%d,%10.3f,%10.3f" % (i, lst_time, d_time))

Рисунок 4 подытоживает результаты запуска листинга 6. Вы видите, что словарь стабильно быстрее. Для списков малых размеров на 10 000 элементов словарь быстрее в 89,4 раза. Для больших списков на 990 000 элементов разница становится в 11 603 раза! Вы также можете видеть, что время, требуемое операции проверки принадлежности, для списка линейно возрастает с ростом его размера. Это подтверждает утверждение о \(O(n)\) оператора принадлежности у списков. Так же хорошо видно, что аналогичная операция для словаря остаётся постоянной даже при возрастании его объёма. Фактически, для словаря размером в 10 000 операция проверки принадлежности занимает 0,004 миллисекунды, как и для словаря на 990 000 элементов.

Рисунок 4: Сравнение операторов in для списков и словарей в Python

Поскольку Python - развивающийся язык, то в глубине его постоянно происходят изменения. Последнюю информацию о производительности структур данных в этом языке можно найти на сайте Python. На момент написания этих строк Python wiki имеет хорошую страничку, посвящённую временн*о*й сложности. Вы можете ознакомиться с ней здесь