Почему поиск в словаре намного быстрее, чем два if-теста в Python?

Question

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

check = {'R':'-', 'F':'+'}
seqs = ['R', 'F']*100

def check1():
    for entry in seqs:
        if entry == 'R':
            strand = '-'
        if entry == 'F':
            strand = '+'

def check2():
    for entry in seqs:
        strand = check[entry]

Используя% time для ipythong, я вижу, что поиск в словаре чуть более чем в два раза быстрее, чем при использовании двух тестов if:

In [63]: %timeit check1()
10000 loops, best of 3: 38.8 us per loop

In [64]: %timeit check2()
100000 loops, best of 3: 16.2 us per loop

Поскольку тесты if такОсновной, я не ожидал разницы в производительности.Это хорошо известно?Кто-нибудь может объяснить, почему это так?

UPDATE

Я проверил, как две функции выше, а также check3 () ниже влияют на время выполнения моего реального кода, инет никакого влияния на общее время.Таким образом, либо повышение, получаемое с помощью словаря, не так высоко в реальном примере, где значения 'R' и 'F' необходимо постоянно перечитывать из файла, или этот фрагмент кода просто не является частью моего узкого места.

В любом случае, спасибо за ответы!

Answer 1

Вы на самом деле не доказали, что поиск в словаре быстрее, чем два if теста.Вы показали, что поиск в этом конкретном словаре выполняется быстрее, чем эти два теста.

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

Вашсловарь использует ключи, которые являются короткими строками, которые соответствуют формату для идентификаторов, известных во время компиляции.Python услужливо «интернирует» ваши строки «R» и «F».Поскольку строки, которые вы используете в своих тестах, также известны во время компиляции, они будут точно такими же экземплярами.Что все это означает для поиска по словарю, так это то, что специализированная версия поиска используется для словаря, который имеет только строковые ключи, хеш всегда был предварительно вычислен, а сравнение ключей выполняется путем сравнения адресов (по крайней мере, когда это успешно и с вашимдве клавиши, которые никогда не выйдут из строя).

Ваш реальный код, я полагаю, будет читать строки из ввода, поэтому он не будет иметь внутреннюю копию 'R'.Это означает, что он должен будет вычислять хеш для каждой строки ввода.Адреса не будут совпадать, поэтому для каждого теста придется вызывать функцию сравнения строк.Вы все еще получаете некоторую оптимизацию для наличия только строковых ключей, и по крайней мере это не должно делать сравнение общего назначения для объектов, которые могут не быть строками.

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

Answer 2

Как и в случае с большим количеством кода виртуальной машины, в основном все сводится к числу задействованных кодов операций виртуальной машины.

Вы можете проверить собранные функции с помощью dis:

import dis
dis.dis(func)

В 2.6.4 для check1 требуется около 15-20 кодов операций (в зависимости от пути кода) для каждого сравнения и ветви. check2 занимает всего 7 (после добавления отсутствующего словаря chedict, объявленного глобально).

Answer 3

Это что-нибудь покажет:

def check3():
    for entry in seqs:
        if entry == 'R':
            strand = '-'
        else:
            strand = '+'

Это на самом деле быстрее, чем check2() на моем компьютере.

Answer 4

Словари сильно оптимизированы в Python; поиск - O(1) - это просто поиск по хеш-таблице и, следовательно, всего одна «операция» - половина числа операций, которые вы получаете с вашей последовательностью if тестов (что составляет O(n)).