Самый быстрый способ поиска python dict с частичным ключевым словом

Question

Каков самый быстрый способ определить, содержит ли ключ ключ, начинающийся с конкретной строки? Можем ли мы лучше, чем линейные? Как мы можем достичь операции O (1), когда мы знаем только начало ключа?

Вот текущее решение:

for key in dict.keys(): 
    if key.start_with(str): 
     return True 
return False 

Answer 1

Без предварительной обработки Dict, O(n) лучшее, что вы можете сделать. Она не должна быть сложной, хотя:

any(key.startswith(mystr) for key in mydict) 

(. Не используйте dict и str как имена переменных, те уже имена двух built-in functions)

Если вы можете предобработки dict, подумайте о том, чтобы положить ключи в дерево префикса (aka trie). Существует даже Python implementation в статье в Википедии.

Answer 2

Вы можете поместить все префиксы вставленных ключей к Словарю, поэтому для ключа foo вы вставили бы f, fo и foo. Вы бы O (1) поиска, но вы бы тратить время на предварительную обработку (O (к), где к является длина ключа), и тратить много памяти:

def insert_with_prefixes(key, value, dict_): 
    prefixes = (key[:i+1] for i in xrange(len(key))) 
    dict_.update((prefix, value) for prefix in prefixes) 

Для повседневного использования я бы (и я иду) с методом в arshajii's ответ. И, конечно, иметь в виду возможных многочисленных столкновений для коротких префиксов (здесь: "h"):

>>> a = {} 
>>> insert_with_prefixes('hello', 'world', a) 
>>> insert_with_prefixes('homo', 'sapiens', a) 
>>> a 
{'h': 'sapiens', 'hom': 'sapiens', 'homo': 'sapiens', 'ho': 'sapiens', 
'hel': 'world', 'hell': 'world', 'hello': 'world', 'he': 'world'}