辞書に特定の文字列で始まるキーが含まれているかどうかを判断する最速の方法は何ですか？私たちは線形より良いことができますか？鍵の始まりだけを知っているときに、どのようにO（1）操作を達成できますか？ O(n)は、あなたができる最善である、辞書を前処理なしで部分検索キーワードを使ってpython dictを検索する最速の方法
for key in dict.keys():
if key.start_with(str):
return True
return False
：ここ
は、現在のソリューションです。これは、しかし、複雑にする必要はありません。
any(key.startswith(mystr) for key in mydict)
（変数名、すでに2 built-in functionsの名前であるものとdictとstrを使用しないでください。）
をした場合、あなたは缶前処理をdictは、プレフィックスツリー（別名trie）にキーを入れることを検討します。ウィキペディアの記事にもPython implementationがあります。
トライはO（log N）であり、O（1）ではありません。しかし、それはあなたがここで欲しいものです。これは、データ構造のパラダイムの場合とほとんど同じです。 – abarnert
@abarnertいいえ、最大の文字列長が文字列数の対数であるという奇妙な仮定をしない限りはありません。トライでのルックアップは、キーの長さが線形であるため、トライの文字列の数に依存しません。 – delnan
@delnan：Nは文字列の数ではなく、別個のシンボルの数です。小規模で静的な記号（ASCII文字列など）がある場合は無視できます。多数のシンボル（たとえば、任意のUnicode）がある場合は、できません。いずれの場合も、各トライレベルで線形検索を実行するか、ログNを1回だけ実行します。 （はい、それは文字列の長さに直線的で、私はそれを無視しました...） – abarnert
あなたがf、foとfooを挿入するキーfooのためのあなたは、辞書に挿入されたキーのすべてのプレフィックスを置くことができます。あなたはO（1）のルックアップを持っているでしょうが、あなたは（kはキーの長さであるO（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'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'}
私はあなたがキーの一部から、キーのハッシュを推測することはできませんと、あなたがより良いものをacheiveすることができます疑います。また、2つのキーが同じ接頭辞で始まる場合、これはあいまいさを残します。 – Hyperboreus
これを行うことができるデータ構造がありますが、Python標準ライブラリでは使用できません。たとえば、トライまたはバイナリ検索ツリー。 – delnan
質問はスピードに関するものなので、 'dict_：key：for key 'は' dict_.keys（）： 'のキーよりもはるかに速く、後者はキーのリストを構築するので、覚えておく必要があります。 –