Python - Tree Search

Question

私はPythonで最も効率的なツリー検索の実装を探しています。 ツリー検索に長さnのシーケンスを与え、ブランチがすでに作成されているかどうかを検出する必要があります。そうでない場合は、ブランチを生成します。

例：

I1：配列1 [0.89,0.43,0.28]

 0.89 check 
     | 
     0.43 check 
     | 
     0.28 check(last branch, last number of sequence == found) 

I2：配列2 [0.89,0.43,0.99]

 0.89 check 
     | 
     0.43 check 
     |           | 
     0.28 missing(Creating new branch)   0.99 

シーケンス内の順序を考慮することが重要です。

目指すのは、膨大な範囲のシーケンス（見えない、見えない）を追跡することです。

誰もがアイデアを持っていますか？

Answer 1

これに無限にネストされたcollections.defaultdictを使用できます。次の関数は、defaultdictを作成します。要求された値が存在しない場合は常に、同じ関数を呼び出して、別のdefaultdictを作成します。

import collections 
nested = lambda: collections.defaultdict(nested) 
dic = nested() 

ここで、ネストされたdefaultdictにシーケンスを追加できます。あなたは、ループ内でこれを行う、または再帰的に、または単にreduce使用することができます。

s1 = [0.89,0.43,0.28] 
s2 = [0.89,0.43,0.99] 

from functools import reduce # Python 3 
reduce(lambda d, x: d[x], s1, dic) 
reduce(lambda d, x: d[x], s2, dic) 

その後、dicはこのようになります

：（実際に、それは少し違って見えるが、それはまた機能、それを印刷するためだけ defaultdictのですで作成されました。）

{0.89: {0.43: {0.28: {}, 0.99: {}}}} 

---

「配列の順序が重要である」によって、あなたはシーケンス内の配列が追加された順序ではなく、順番を意味する場合代わりにcollections.OrderedDictを使用する必要があります。この場合、新しい要素の追加はもう少し複雑ですが、あまり関与しません。

dic = collections.OrderedDict() 

def putall(d, s): 
    for x in s: 
     if x not in d: 
      d[x] = collections.OrderedDict() 
     d = d[x] 

putall(dic, s1) 
putall(dic, s2)