В данном случае Python также поддерживает операции поиска с помощью встроенных инструментов. Словари, например, предоставляют оптимизированные инструменты поиска по таблицам, реализованные на языке C. Встроенная операция доступа к элементам словаря по ключу, вероятнее всего, будет выполняться быстрее, чем эквивалентная реализация поиска на языке Python:
> >> x = {} # пустой словарь
> >> for i in [3, 1, 9, 2, 7]: x[i] = None # вставка
…
>>> x
{7: None, 1: None, 2: None, 3: None, 9: None}
>>>
> >> for i in range(8): print((i, i in x), end=’ ‘) # просмотр
…
(0,False) (1,True) (2,True) (3,True) (4,False) (5,False) (6,False) (7,True)
Поскольку словари встроены в язык, они доступны всегда и обычно всегда оказываются быстрее структур данных, реализованных на языке Python. Часто аналогичную функциональность могут предложить встроенные множества — при этом достаточно просто представить себе множество как словарь, не имеющий значений:
> >> x = set() # пустое множество
> >> for i in [3, 1, 9, 2, 7]: x.add(i) # вставка
…
>>> x
{7, 1, 2, 3, 9}
> >> for i in range(8): print((i, i in x), end=’ ‘) # просмотр
…
(0,False) (1,True) (2,True) (3,True) (4,False) (5,False) (6,False) (7,True)
Существует множество способов добавления элементов в множества и словари — оба типа удобно использовать для проверки наличия ключа, но словари дополнительно позволяют присваивать значения ключам:
> >> v = [3, 1, 9]
# генератор множеств
|
{1, >>> {1, |
3, 9} set(v) 3, 9} |
# |
конструктор множества |
|
>>> {1: |
{k: k+100 for k in v} 101, 3: 103, 9: 109} |
# |
генератор словарей |
|
>>> {1: |
dict(zip(v, [99] * len(v))) 99, 3: 99, 9: 99} |
# |
конструктор словаря |
|
>>> {1: |
dict.fromkeys(v, 99) 99, 3: 99, 9: 99} |
# |
метод словаря |
Тогда зачем заниматься реализацией собственных структур данных для поиска, если встроенные типы обеспечивают такую гибкость? В некоторых приложениях этого может и не потребоваться, но в данном случае может оказаться более целесообразным применить оптимизированные алгоритмы поиска в деревьях. Например, использование сбалансированных деревьев позволяет повысить скорость поиска даже в самых тяжелых случаях и превзойти по быстродействию обобщенные алгоритмы поиска, используемые в словарях и множествах. Кроме того, здесь действуют те же побудительные мотивы, которые подтолкнули нас к созданию собственных реализаций стеков и множеств, — заключая доступ к деревьям в интерфейс на основе классов, мы упрощаем возможность расширения и изменения в будущем.
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
