Является ли операция добавления в set () или вставка в dict () в Python фактически O (n), где n - длина строки ключа? - PullRequest
Новая
       58

Является ли операция добавления в set () или вставка в dict () в Python фактически O (n), где n - длина строки ключа?

2 голосов
/ 02 мая 2019

Существует противоречие относительно того, является ли операция вставки в dict () или операция добавления в set () O (n) или O (1), где n - длина строки.

Предположим, у нас есть строки различной длины, т.е. n1, n2, ... n_x.Тогда временная сложность выполнения следующего: 

s = set()
d = dict()
for x in {N}: # where N = [n1, n2, ... n_x]
  s.add(x)
  d[x] = 1

равна O(len(N) * Z), где Z = len(n_1) + len(n_2) + ... len(n_x) Если мы предположим, что операция добавления или вставки является O (1), тогда сложность времени будет O (len (N))).

Верно ли указанное выше?

С: http://svn.python.org/projects/python/trunk/Objects/stringobject.c мы видим, что вычисление хеша зависит от длины строки, что, как я предполагаю, приведено ниже:

static long string_hash(PyStringObject *a)
{
    register Py_ssize_t len;
    register unsigned char *p;
    register long x;

    if (a->ob_shash != -1)
        return a->ob_shash;
    len = Py_SIZE(a);
    p = (unsigned char *) a->ob_sval;
    x = *p << 7;
    while (--len >= 0)
        x = (1000003*x) ^ *p++;
    x ^= Py_SIZE(a);
    if (x == -1)
        x = -2;
    a->ob_shash = x;
    return x;
}

Здесь ( эффективность длинных (str) ключей в словаре Python ) кто-то показал, что изменение длины строки не влияет на время вычисления хэша.Но это противоречит приведенному выше коду.

Из следующей ссылки мы знаем, что вычисленное значение хеша сохраняется в объекте.Это означает, что поиск будет постоянным временем O (1). Получить хэш ключей словаря без перерасчета

1 Ответ

4 голосов
/ 02 мая 2019

Есть несколько вещей, от которых зависит производительность insert . Вычисление хеш-функции действительно является O (k) для строки длины k, но это просто неинтересно в общем случае.

Если вы рассматриваете строковые ключи длиной всего 8 байтов, существует 18446744073709551616 различных комбинаций, и 8 является константой , вычисление хеш-значения для 8-байтового ключа равно O (8) равно O (1) ,

Но при 18446744073709551616 элементах вставка в хеш-таблицу все еще может занять 1 мкс. И для списка, где вставка в начало будет O (n), а вставка / копирование одного элемента занимает только одну наносекунду в конце списка, вставка в начало списка этого многие вещи могут занять 585 лет.

OTOH, хотя вполне возможно, что у вас может быть коллекция из 4294967296 или даже 18446744073709551616 элементов, если у вас есть ключ из 4294967296 или 18446744073709551616 байт для вашей хеш-таблицы, которые вам действительно нужны переосмыслить вашу архитектуру .

...