размер эффективный словарь (ассоциативный массив) реализация

Question

Какие алгоритмы доступны для эффективного размера A dictionary or associative array? Например, с помощью этого набора ключей/значений, как можно избежать дублирования «Алиса» в значениях?

{ 
    "Pride and Prejudice": "Alice", 
    "The Brothers Karamazov": "Pat", 
    "Wuthering Heights": "Alice" 
} 

Я проверил Python's implementation on dictionary, но кажется, что реализация ориентирована на скорости (держащий O (1)) не размер.

Answer 1

Как отметил bennofs в комментариях, вы можете использовать intern(), чтобы гарантировать, что одинаковые строки сохраняются только один раз:

class InternDict(dict): 

    def __setitem__(self, key, value): 
     if isinstance(value, str): 
      super(InternDict, self).__setitem__(key, intern(value)) 
     else: 
      super(InternDict, self).__setitem__(key, value) 

Вот пример эффекта, который имеет:

>>> d = {} 
>>> d["a"] = "This string is presumably too long to be auto-interned." 
>>> d["b"] = "This string is presumably too long to be auto-interned." 
>>> d["a"] is d["b"] 
False 
>>> di = InternDict() 
>>> di["a"] = "This string is presumably too long to be auto-interned." 
>>> di["b"] = "This string is presumably too long to be auto-interned." 
>>> di["a"] is di["b"] 
True 

Answer 2

• Если ваш словарь может поместиться в память, тогда может использоваться простая Hashtable.

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

Существует в основном в два раза: массив & дерево.

• Array сосредоточиться на скорости при высокой стоимости памяти. Основное различие между реализацией Hashtable - поведение по унификации, некоторая реализация обеспечивает единство некоторых других нет.

• Дерево сосредоточиться на интеллектуальном использовании памяти по стоимости O (log (n)) использования процессора. g ++ map полагается на очень полную мощность red black tree.

Если размер очень очень Проблематика, то вы должны искать Huffman сжатие и/или Lampel Ziv сжатие, но это стоило немного больше, чтобы адаптироваться к dictionnary.

• Если dictionnary не может поместиться в памяти

Вы должны смотреть на базу данных. red black tree для базы данных известен как BTree (почти). Он имеет оптимизацию факторизации ветвей для случая с малым временем ожидания.

Я поставил много ссылку на Википедию, но если вам нравится этот предмет я Recommand вам:

Answer 3

Одним из способов повышения эффективности пространства (в дополнение к значениям обмена, которые (как bennofs указывает в комментарии), вы, вероятно, можете эффективно выполнить с помощью sys.intern), заключается в использовании hopscotch hashing, который является открытой схемой адресации (вариант линейного исследования) для разрешения конфликтов. Схемы закрытой адресации используют больше пространства, потому что вам нужно выделить связанный список для каждого ведра, тогда как с открытой схемой адресации вы просто используете открытый соседний слот в массиве поддержки без необходимости ng для размещения любых связанных списков. В отличие от других открытых схем адресации (таких как хэширование кукушки или линейного зондирования ванили), хеширование хопскотчей хорошо работает под высоким коэффициентом загрузки (более 90%) и гарантирует постоянный поиск времени.