3

私はデータ構造について独学しようとしており、Python で kd ツリーを実装しています。kd ツリー クラスの 1 つのポイントの特定の半径内でツリー内のポイントを検索するメソッドがあります。

def within_radius(self, point, radius, result=[]):
    """
    Find all items in the tree within radius of point
    """
    d = self.discriminator

    if in_circle(point, radius, self.data):
        result.append(self.data)

    # Check whether any of the points in the subtrees could be
    # within the circle
    if point[d] - radius < self.data[d] and self.l_child:
        result.append(self.l_child.within_radius(point, radius, result))

    if point[d] + radius > self.data[d] and self.r_child:
        result.append(self.r_child.within_radius(point, radius, result))

    return result

それは機能しますが、返されるリストはかなりファンキーで、再帰呼び出しからの値が重複していますresult。ツリー再帰から返された値をリストに「蓄積」する良い方法は何ですか? しばらく考えているのですが、よくわかりません。

4

3 に答える 3

4

これが最もクリーンな方法かどうかはわかりませんが、このような再帰を行うときはいつでも、返されるリストであるキーワード引数を追加することがよくあります。そうすれば、リストを変更すると、常に同じリストに変更されます。

def recurse(max, _output=None):
    if _output is None:
        _output = []

    #do some work here, add to your list
    _output.append(max)

    if max <= 0: #Some condition where the recursion stops
        return _output
    else:        #recurse with new arguments so that we'll stop someday...
        return recurse(max-1, _output=_output)

これが機能するのは、停止条件が のTrue場合、_outputリストが返され、スタックのずっと上に渡されるためです。

アンダースコア付きの変数名を使用して、それが関数内でのみ使用されることを示しています。これは、アンダースコアがプレフィックスされた変数が使用される通常の方法 (変数が「プライベート」であることを示すためのクラス内) のわずかな拡張ですが、要点は理解できると思います...

これはあなたが持っているものとあまり変わらないことに注意してください。 ただし、あなたのバージョンでは、関数が呼び出されたときではなく、関数が作成されたときに評価されるresultため、呼び出し間で持続します。また、バージョンは戻り値 (リスト自体) を追加しています。それ自体への複数の参照を保持するリストについて考えると、これは非常に複雑になります...result = []

于 2012-08-14T13:09:13.550 に答える
2

mgilsonの分析に同意します。listは可変タイプでlist.appendあり、インプレースです。これが意味することです：

可変と不変の2つのタイプがあります。

変更可能なタイプは、変更した場合でも、メモリ上の同じ場所に存在します。たとえば、listsとsは可変型です。dictこれは、を作成しlistて特定の方法で変更した場合でも、メモリ内の同じ場所に存在することを意味します。listしたがって、 「myList」という名前を作成するとします。このリストをメモリ位置0x9000にあるとしましょう。次に、実行してもメモリ内myList.append(0)の場所は変更されません。myList行ったとしてもmyList[0] = 'a'、場所は変更されません-それは0x9000でまだ生きています。

不変タイプは、何らかの方法で変更しようとすると、別のメモリ位置に「移動」します。strsとtuplesは不変です。これが、次のエラーが発生する理由です。

>>> s = 'as'
>>> s[0] = 'b'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

これは、あなたが定義し（そして今はメモリアドレス0x5000に住んでいるs = 'as'としましょう）、それをとして再定義したとしても、メモリ内の場所が変わることを意味します。ss = 'af's

これで、可変タイプを再割り当てすると、メモリ内の位置が変わります。例えば、

L = [1,2,3]＃メモリ位置0x4000と言うL = [5,6,7]＃メモリ位置は0x4000ではなくなった

list.appendここで、 「インプレース」であるという特性が発揮されます。「list.appendインプレース」とは、新しいリストを作成せずに、新しい要素がリストに追加されることを意味します。これが、list.append以下に示すように、戻り値がない理由です。

>>> L = [1,2,3]
>>> ret = L.append(4)
>>> print L
[1, 2, 3, 4]
>>> print ret
None

ただし、新しいリストを作成する場合は、次のように行うことができます。

>>> L = [1,2,3]
>>> ret = L + [4]
>>> print L
[1, 2, 3]
>>> print ret
[1, 2, 3, 4]

したがって、あなたのケースで起こっていることは、両方の再帰呼び出し（左と右）でpoint、各再帰呼び出しのリストに追加されるということです。これが、重複する値を取得する理由です。

mgilsonが提案することを実行することでこれを回避できます。または、Lispファンの場合（これは非常に優れたLispの質問です）、[1,2,3] + [4]原則を使用してこれを実行できます（テストされていませんが、機能するはずです）。

def within_radius(self, point, radius, result=[]):
    """
    Find all items in the tree within radius of point
    """
    d = self.discriminator

    temp = []

    if in_circle(point, radius, self.data):
        temp = [self.data]

    # Check whether any of the points in the subtrees could be
    # within the circle
    if point[d] - radius < self.data[d] and self.l_child:
        temp += self.l_child.within_radius(point, radius, result)

    if point[d] + radius > self.data[d] and self.r_child:
        temp += self.r_child.within_radius(point, radius, result)

    return result+temp

お役に立てれば

于 2012-08-14T13:40:38.000 に答える
1

ここにいくつかの考えがあります：

  • 一意の結果のみを返したい場合は、セットを使用して、戻ったときにそれをリストに変換する必要があります。1 つのself.data落とし穴は、たとえばリストではなくタプルなど、不変でなければならないことです。
  • result再帰をスレッド化して再帰呼び出しの結果を追加しているため、各ヒットを結果に少なくとも 2 回明示的に追加しています。再帰を通じて結果をスレッド化すると、データ構造を作成して破棄することができなくなるため、おそらくそれを行うことができます。
  • mgilson が指摘しているように、Python がデフォルトの引数を処理する方法のためresult、関数宣言で空のリストに設定すると、あなたが思うようにはなりません。within_radiusを明示的に渡さずに呼び出すたびresultに、個々の呼び出しだけでなく、呼び出しごとにヒットが累積されます。（それは理にかなっていますか？これを参照してください）。mgilson's answer もこれを指摘しています。

これらすべてを念頭に置いて、私はおそらく次のようにします。

def within_radius(self, point, radius, result=None):
    d = self.discriminator

    result = set() if result is None else result

    if in_circle(point, radius, self.data):
        result.add(self.data)
    if point[d] - radius < self.data[d] and self.l_child:
        self.l_child.within_radius(point, radius, result)
    if point[d] + radius > self.data[d] and self.r_child:
        self.r_child.within_radius(point, radius, result)

    return list(result)
于 2012-08-14T13:44:43.580 に答える