Каков самый быстрый способ определить, содержит ли dict ключ, начинающийся с конкретной строки? Можем ли мы лучше, чем линейные? Как мы можем достичь операции O (1), когда мы знаем только начало ключа?
Вот текущее решение:
for key in dict.keys():
if key.start_with(str):
return True
return False
Без предварительной обработки dict, O(n) - лучшее, что вы можете сделать. Это не должно быть сложным, хотя:
any(key.startswith(mystr) for key in mydict)
(Не используйте dict и str как имена переменных, это уже имена двух встроенных функций.)
Если вы можете предварительно обработать dict, подумайте о том, чтобы положить ключи в дерево префикса (aka trie). Существует даже реализация Python в статье в Википедии.
Вы можете поместить все префиксы вставленных ключей в dict, поэтому для клавиши foo вы должны вставить f, fo и foo. У вас был бы поиск O (1), но вы бы потратили время на предварительную обработку (O (k), где k - длина ключа) и теряете массу памяти:
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. И, конечно, иметь в виду возможные столкновения для коротких префиксов (здесь: "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'}