Какова временная сложность поиска в Dict, если в качестве ключей используются очень длинные строки?

Question

Я прочитал из python3 документа, что python использует таблицу ha sh для dict (). Таким образом, сложность времени поиска должна быть O (1) с O (N) в худшем случае. Однако недавно, когда я прошел курс, учитель сказал, что это происходит только тогда, когда вы используете int в качестве ключа. Если вы используете строку длины L в качестве ключей, сложность времени поиска составляет O (L).

Я пишу фрагмент кода, чтобы проверить его честность

import random
import string
from time import time
import matplotlib.pyplot as plt

def randomString(stringLength=10):
    """Generate a random string of fixed length """
    letters = string.ascii_lowercase
    return ''.join(random.choice(letters) for i in range(stringLength))

def test(L):
    #L: int length of keys

    N = 1000 # number of keys
    d = dict()
    for i in range(N):
        d[randomString(L)] = None

    tic = time()
    for key in d.keys():
        d[key]
    toc = time() - tic

    tic = time()
    for key in d.keys():
        pass
    t_idle = time() - tic

    t_total = toc - t_idle
    return t_total

L = [i * 10000 for i in range(5, 15)]
ans = [test(l) for l in L]

plt.figure()
plt.plot(L, ans)
plt.show()

Результат очень интересный , Как вы можете видеть, ось X - это длина строк, используемых в качестве ключей, а ось Y - общее время запроса всех 1000 ключей в словаре.

Кто-нибудь может объяснить этот результат?

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

Answer 1

Поскольку словарь является хеш-таблицей, а поиск ключа в хеш-таблице требует вычисления га sh, то временная сложность поиска ключа в словаре не может быть меньше временной сложности га *. 1026 * function.

В текущих версиях CPython строка длины L занимает O (L) время, чтобы вычислить га sh, если это первый раз, когда вы хэшировали это конкретный строковый объект и время O (1), если ха sh для этого строкового объекта уже вычислено (поскольку хранится га sh):

>>> from timeit import timeit
>>> s = 'b' * (10**9) # string of length 1 billion
>>> timeit(lambda: hash(s), number=1)
0.48574538500002973 # half a second
>>> timeit(lambda: hash(s), number=1)
5.301000044255488e-06 # 5 microseconds

Так что это также, как долго принимает при поиске ключа в словаре:

>>> s = 'c' * (10**9) # string of length 1 billion
>>> d = dict()
>>> timeit(lambda: s in d, number=1)
0.48521506899999167 # half a second
>>> timeit(lambda: s in d, number=1)
4.491000026973779e-06 # 5 microseconds

Вам также нужно знать, что ключ в словаре не ищется только по его га sh: когда хэши совпадают, необходимо проверить, что ключ, который вы искали, равен ключу, используемому в словаре, в случае, если совпадение ha sh является ложноположительным. Проверка на равенство строк занимает в худшем случае время O (L):

>>> s1 = 'a'*(10**9)
>>> s2 = 'a'*(10**9)
>>> timeit(lambda: s1 == s2, number=1)
0.2006020820001595

То есть для ключа длины L и словаря длины n:

• Если ключ отсутствует в словаре, и его ha sh уже был кэширован, тогда требуется O (1) среднее время, чтобы подтвердить его отсутствие.
• Если ключ отсутствует, а его ha sh не был кэширован, то требуется среднее время O (L) из-за вычисления га sh.
• Если ключ присутствует, для подтверждения его наличия требуется среднее время O (L) или нет, необходимо вычислить га sh из-за теста на равенство.
• Наихудшим случаем всегда является O (nL), потому что если каждый ха sh сталкивается и все строки равны, кроме последние места, то медленный тест на равенство должен быть выполнен n раз.

Answer 2

только когда вы используете int в качестве ключа. Если вы используете строку длины L в качестве ключей, сложность времени поиска будет O (L)

Просто для того, чтобы обратиться к точке, не охваченной ответом kaya3 ....

Почему люди часто говорят, что вставка, поиск или стирание таблицы ha sh является операцией O (1).

Для многих реальных применений таблиц ha sh типичная длина ключи не имеют тенденцию расти независимо от того, сколько ключей вы храните. Например, если вы настроили параметр ha sh для хранения имен в телефонной книге, средняя длина имени для первых 100 человек, вероятно, очень близка к средней длине для абсолютно всех. По этой причине время, затрачиваемое на поиск имени, не хуже, если у вас есть набор из десяти миллионов имен по сравнению с начальными 100 (этот вид анализа обычно игнорирует влияние на производительность размеров кэш-памяти ЦП и скорости ОЗУ и скорости диска, если ваша программа начинает меняться). Вы можете рассуждать о программе, не задумываясь о длине имен: например, вставка миллиона имен может занять примерно в тысячу раз больше времени, чем вставка тысячи.

В других случаях приложение имеет га sh таблицы, где ключ может значительно отличаться. Представьте себе, например, набор ha sh, где ключами являются видео, кодирующие двоичные данные: один набор данных - это старые видеоклипы со стандартным разрешением 24 кадра в секунду, а другой - фильмы со скоростью 8 000 UHD и скоростью 60 кадров в секунду. Время, затрачиваемое на вставку этих наборов ключей, не будет просто зависеть от количества таких ключей, поскольку в хешировании и сравнении ключей значительно разного объема работы. В этом случае - если вы хотите подумать о времени вставки для ключей разных размеров, анализ производительности big-O был бы бесполезен без соответствующего фактора. Вы все еще можете описать относительную производительность для наборов данных с ключами одинакового размера, учитывая только обычные характеристики производительности таблицы ha sh. Когда время хеширования ключа может стать проблемой, вы, возможно, захотите решить, является ли дизайн вашего приложения хорошей идеей, или, например, вы могли бы использовать набор, скажем, имен файлов вместо сырых видеоданных.