Базовая хеш-структура данных Python для словарей

Question

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

Python использует структуру хеш-данных для хранения словарей (не путать с криптографической хеш-функцией).Поиски O (1), но если хеш-таблица заполнена, ее нужно перефразировать, что очень дорого.

Мой вопрос: лучше ли мне использовать Дерево двоичного поиска AVL или достаточно хеш-таблицы?

Answer 1

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

Если вы посмотрите на реализацию словаря Python , вы увидите, что:

1. словарь начинается с 8 записей (PyDict_MINSIZE);
2. словарь с размером 50 000 или менее записей увеличивается в четыре раза при увеличении;
3. словарь с более чем 50 000 записей удваивается при увеличении;
4. ключевые хэши кэшируются в словаре, поэтому они не пересчитываются при изменении размера словаря.

(« ЗАМЕЧАНИЯ ПО ОПТИМИЗАЦИИ СЛОВАРЕЙ » тоже стоит прочитать.)

Так что, если в вашем словаре есть 1 000 000 записей, я думаю, что он будетразмер одиннадцать раз (8 → 32 → 128 → 512 → 2048 → 8192 → 32768 → 131072 → 262144 → 524288 → 1048576 → 2097152) при стоимости 2 009 768 дополнительных вставок при изменении размеров.Похоже, что это намного меньше, чем стоимость всей перебалансировки, связанной с 1 000 000 вставок в дерево AVL.

Answer 2

Словари Python высоко оптимизированы. Python делает различные оптимизации для особых случаев, которые разработчики Python учитывают в реализации словаря CPython.

1. В CPython все PyDictObject оптимизированы для словарей, содержащих только строковые ключи.
2. Словарь Python старается никогда не быть заполненным более чем на 2/3.

Книга " Красивый код " обсуждает все это.

Восемнадцатая глава - реализация словаря Python: быть всем для всех людей. Автор Adrew Kuchling

Гораздо лучше использовать его, чем пытаться получить созданную вручную пользовательскую реализацию, которая должна будет реплицировать все эти оптимизации, чтобы быть где угодно, рядом с основной реализацией словаря CPython.

Answer 3

Каково соотношение предметов к уникальным предметам?Какое ожидаемое количество уникальных элементов?

Если заполнить хэш-память, расширение должно быть просто вопросом перераспределения памяти, а не перефразирования.легко сделать.

Обратите внимание также на класс счетчика, доступный с python 2.7 http://docs.python.org/library/collections.html#counter-objects http://svn.python.org/view?view=rev&revision=68559

Answer 4

Использование dict - O (1). Когда диктат растет, иногда требуется перераспределение, но оно амортизируется O (1)

Если ваш другой алгоритм O (log n), простой дикт будет всегда побеждать его по мере увеличения набора данных.

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

Хэш-таблица не только достаточно хороша, но и лучше

Answer 5

Вы должны будете реализовать свои собственные структуры данных в C, чтобы иметь реальную возможность превзойти встроенные структуры.

Также вы можете избежать некоторых накладных расходов, используя get, избегая двойного поиска существующих элементов. Или коллекций. Счет, если вы используете Python 2.7 +.

def increment(map, key):
    map[key] = map.get(key,0)+1