リストを使用して配列のインデックスを確認する

Question

Pythonでは、状態を表すリストを生成しています（たとえば、状態は[1,3,2,2,5]です）。

各要素の値は、1から特定の数までの範囲で指定できます。 特定の規則に基づいて、これらの状態は特定の方法で進化する可能性があります。私はすでに遭遇した国には興味がない。

今、私のコードは、リストがリストのリストにあるかどうかをチェックし、そうでなければそれを追加します。しかし、このリストは非常に大きくなり、チェックするために多くのリソースを使用しています。

Iは、その配列内の特定の位置を確認し、そして場合、その位置が0の場合は1

に設定

、ゼロの多次元配列を作成

• たい私はリストまたは配列として格納された状態を取って、インデックス値に対応するように1 で調整し、その値をゼロ配列のインデックス として渡そうとしますが、それは1つの要素を変更するだけではありません。

  リストが括弧で囲まれているため、index（）はカンマで区切られた整数の 引数を必要としているからです。

  コードの複雑さを増やさない配列のインデックスをチェックするために、整数のリストまたは配列を渡す方法はありますか？またはさらに効率的な方法を 私はすでに生成している状態を格納し、チェックするには？

Answer 1

あなたはすでに遭遇した状態をsetに維持する必要があります。これにより、包含チェック（state in visited）がO（1）であり、O（N）でないことが保証されます。 listsはハッシュ可能ではありませんので、あなたがtuplesに変換する必要がある、または最初の場所でタプルを使用します。

visited = set() 
states = [[1,3,2,2,5], [...], ...] 

for state in states: 
    tpl = tuple(state) 
    if tpl not in visited: # instant check no matter the size of visted 
     # process state 
     visited.add(tpl) 

この5次元のリストを作成してある有効な指標として状態値を渡すあなたのアイデアが、大きい（n^5 n：各スロットの値の数）とおそらくまばらな、したがってウエストがかかったマトリックスが作成されます。 ところでではなく、m[1][3][2][2][5]経由でこのようなマトリックスのスロットにアクセスします。

Answer 2

はい、あなたの状態のクラスを定義し、そのハッシュ関数を定義することができます。このように、検索の実行している時間がO(1)に削減し、必要なスペースはNではなく、状態の数の状態の数あるO(N)に削減*状態のサイズ

状態のサンプルクラス：

class State(object): 
    def __init__(self, state_array): 
     self.state_array = state_array 
    def getHash(self): 
     return hash(self.state_array) # using python default hash function here, you can totally design your own. 

現在の状態保存：Pythonで、こと

# current_state is the state you currently have 
all_states = {} 
if current_state.getHash() not in all_state: 
    all_states[current_state.getHash()] = 1 
else: 
    # Do something else 

注はO(1)となります。なぜなら、pythonのdictは実際にはハッシュマップなのです。