0

2Dで約500ポイントのデータセットがあり、指定された座標（単一の整数で各ポイントを参照できることも意味します）（x、y）は0から10の間です。現在、領域を通常の領域に分割しようとしています。グリッドを適用してセルを正方形にします。このプロセスはアルゴリズムで繰り返されており、ある時点で>>>500個の正方形のセルが存在することに注意してください。

達成したいこと：すべてのポイントをループします。各ポイントについて、ポイントが存在する正方形のセルを見つけて、この情報を保存します。
数ステップ後：すべてのポイントを再度ループします。各ポイントについて、そのセルとセルの隣接セルを識別します。これらのセルのすべてのポイントを取得し、さらに使用するために、たとえばリストに追加します。

私の思考プロセス：空のセルがたくさんあり、それらのためにメモリを無駄にしたくないので、ツリーを使用します。
例：cell_39_41では、cell_39_42はポイントです。第1レベル：子を持つルートノード39
第2レベル：子を持つ39ノード41,42
第3レベル：子ポイント1を持つ41ノードおよび子ポイント2を持つ42ノード
第4レベル：実際のポイントを表すノード
cell_39_41またはcell_39_42にさらにポイントが見つかった場合それぞれの第3レベルノードの子として追加されます。

class Node(object):

def __init__(self, data):
    self.data = data
    self.children = []

def add_child(self, obj):
    self.children.append(obj)

セル内のポイントを返すための無関係なメソッドを省略しました。

この実装の問題：
1。2番目または3番目のレベルのノードを追加する場合、子を追加したり、特定のセルとその隣接セルでポイントを見つけたりできるように、ノードを参照する必要があります。これは、子リストがソートされていないため、コストのかかる線形検索を大量に実行する必要があることを意味します。
2.数百のノードを追加しますが、一意の名前でそれらを参照できるようにする必要があります。これは個人的に大きな失敗かもしれませんが、ループでそのような名前を生成する方法を考えることはできません。

ですから、基本的には、思考プロセスに間違いがあるか、使用されているツリーの実装が適切でない可能性があると確信しています。私はbツリーまたは類似の実装をたくさん読んだことがありますが、この問題は2Dに限定されているため、それらは多すぎて適切ではないと感じました。

4

2 に答える 2

2

これはどう ...

def add_point(data_dict, row, column, point):
    # modifies source of data_dict in place, since dictionaries are mutable
    data_dict.setdefault(row, {}).setdefault(column, []).append(point)

def get_table(data):
    out_dict = {}
    for row, column, point in data:
        add_point(out_dict, row, column, point)
    return out_dict


if __name__ == "__main__":
    data = [(38, 41, 38411), (39, 41, 39411), (39, 42, 39421)]
    points = get_table(data)    
    print points    
    add_point(points, 39, 42, 39422)    
    print points
于 2012-06-11T13:45:43.713 に答える
1

辞書の辞書をツリーとして使用します。

tree = {
    '_data': 123,
    'node1': {
        '_data': 456,
        'node11': {
           'node111': {}
        },
    'node2': {
    }
}

辞書での検索は高速です!

tree['node1']['node12']['node123']['_data'] = 123 # adding

一意の名前:

shortcuts = {}
shortcuts['name'] = tree['node1']['node11']['node111']
print shortcuts['name']['_data']
于 2012-06-11T12:31:21.283 に答える