2

この質問のコメント（これは無関係であることがわかります）によって提起され、定期的にクエリ/アクセスする必要のあるデータに辞書を使用することは、迅速に適切ではないことに気づきました。

私はこのような状況にあります：

someDict = {}
someDict[(-2, -2)] = something
somedict[(3, -10)] = something else

ゲームでタイルの配列として機能するオブジェクトに座標のキーを保存しています。これらはある時点で負になるので、リストやある種のスパース配列を使用することはできません（これが用語だと思いますか？）。

どちらでもいいですか：

  • 辞書の検索を高速化するので、これは問題になりません
  • スパースな負のインデックスをサポートするコンテナの種類を見つけますか？

リストを使用しますが、クエリはO（log n）からO（n）に移動して、（x、y）の領域を検索します。（ここでもタイミングがずれていると思います）。

4

5 に答える 5

2

から始めるには

辞書の検索を高速化するので、これは問題になりません

辞書の検索は非常に高速ですO（1）ですが、（他の質問から）辞書のハッシュテーブル検索に依存しておらず、辞書のキーの線形検索に依存しています。

スパースな負のインデックスをサポートするコンテナの種類を見つけますか？

これは辞書に索引付けされていません。タプルは不変オブジェクトであり、タプル全体をハッシュしています。辞書は実際にはキーの内容を認識しておらず、ハッシュだけを認識しています。

他の人がしたように、データを再構築することをお勧めします。

たとえば、必要なデータをカプセル化するオブジェクトを作成し、それらをO（n lg n）検索用のバイナリツリーに配置できます。if foo in Bar:探している素晴らしい構文を提供するクラスですべてをラップすることもできます。

あなたが望むことを達成するために、おそらくいくつかの調整された構造が必要です。これは、dictとsetsを使用した単純化された例です（ユーザー6502の提案を少し微調整します）。

# this will be your dict that holds all the data
matrix = {}
# and each of these will be a dict of sets, pointing to coordinates
cols = {}
rows = {}

def add_data(coord, data)
    matrix[coord] = data
    try:
        cols[coord[0]].add(coord)
    except KeyError:
        # wrap coords in a list to prevent set() from iterating over it
        cols[coord[0]] = set([coord])
    try:
        rows[coord[1]].add(coord)
    except KeyError:
        rows[coord[1]] = set([coord])

# now you can find all coordinates from a row or column quickly
>>> add_data((2, 7), "foo4")
>>> add_data((2, 5), "foo3")
>>> 2 in cols
True
>>> 5 in rows
True
>>> [matrix[coord] for coord in cols[2]]
['foo4', 'foo3']

これをクラスまたはモジュールでラップするだけで、オフになります。いつものように、プロファイルが十分に速くない場合は、推測する前にテストしてください。

于 2011-03-11T20:16:06.070 に答える
2

Python辞書は非常に高速であり、整数のタプルを使用しても問題はありません。ただし、ユースケースでは、単一座標チェックを実行する必要がある場合があり、すべてのdictをトラバースするのはもちろん遅いようです。

ただし、線形検索を実行する代わりに、次の3つの辞書を使用して、必要なアクセスのデータ構造を高速化できます。

class Grid(object):
    def __init__(self):
        self.data = {}  # (i, j) -> data
        self.cols = {}  # i -> set of j
        self.rows = {}  # j -> set of i

    def __getitem__(self, ij):
        return self.data[ij]

    def __setitem__(self, ij, value):
        i, j = ij
        self.data[ij] = value
        try:
            self.cols[i].add(j)
        except KeyError:
            self.cols[i] = set([j])
        try:
            self.rows[j].add(i)
        except KeyError:
            self.rows[j] = add([i])

    def getRow(self, i):
        return [(i, j, data[(i, j)])
                for j in self.cols.get(i, [])]

    def getCol(self, j):
        return [(i, j, data[(i, j)])
                for i in self.rows.get(j, [])]

何をしようとしているのか、読み取りの頻度、更新の頻度、長方形でクエリを実行する場合、最も近い空でないセルを探す場合などに応じて、他にも多くの可能なデータ構造があることに注意してください。

于 2011-03-11T20:33:36.400 に答える
1

代替案の1つは、単にインデックスをシフトして正になるようにすることです。

たとえば、インデックスが次のように連続している場合：

...
-2 -> a
-1 -> c
0 -> d
1 -> e
2 -> f
...

LookupArray [Index + MinimumIndex]のように実行します。ここで、MinimumIndexは、使用する最小のインデックスの絶対値です。

そうすれば、最小値が-50の場合、0にマップされます。-20は30にマップされ、以下同様に続きます。

編集：

別の方法は、インデックスの使用方法にトリックを使用することです。次の主要な機能を定義する

Key(n) = 2 * n (n >= 0)
Key(n) = -2 * n - 1. (n < 0)

これにより、すべての正のキーが正の偶数インデックスにマップされ、すべての負の要素が正の奇数インデックスにマップされます。ただし、これは実用的ではない場合があります。100個の負のキーを追加すると、配列を200個拡張する必要があるためです。

注意すべきもう1つのこと：ルックアップを実行することを計画していて、キーの数が一定である（または非常にゆっくりと変化する）場合は、配列を使用してください。そうでなければ、辞書はまったく悪くありません。

于 2011-03-11T20:16:55.933 に答える
1

辞書の検索は非常に高速です。キーの一部（たとえば、行xのすべてのタイル）を検索するのは速くありません。dictのdictを使用できます。2タプルでインデックス付けされた単一の辞書ではなく、次のようなネストされた辞書を使用します。

somedict = {0: {}, 1:{}}
somedict[0][-5] = "thingy"
somedict[1][4] = "bing"

次に、特定の「行」にすべてのタイルが必要な場合は、それだけsomedict[0]です。

必要に応じてセカンダリ辞書を追加するためのロジックが必要になります。ヒント：標準タイプ、または場合によってはタイプを確認しgetitem()てください。setdefault()dictcollections.defaultdict

このアプローチにより、特定の行のすべてのタイルにすばやくアクセスできます。特定の列にすべてのタイルが必要な場合は、まだ時間がかかります（ただし、少なくともすべてのセルを調べる必要はなく、すべての行を調べる必要はありません）。ただし、必要に応じて、2つのdictのdict（1つは列、行の順序、もう1つは行、列の順序）を使用することで、これを回避できます。その場合、更新は2倍の作業になります。これは、ほとんどのタイルが静的であるゲームでは問題にならない場合がありますが、どちらの方向からでもアクセスは非常に簡単です。

数値を格納するだけで、ほとんどのセルが0になる場合は、scipyのスパース行列クラスを確認してください。

于 2011-03-11T20:19:43.877 に答える
0

多次元リストを使用します。通常、ネストされたオブジェクトとして実装されます。少しの算術演算で、これに負のインデックスを簡単に処理させることができます。可能なすべてのスロット（通常は空のスロット）に何かを配置する必要があるため、辞書よりも多くのメモリを使用する可能性がありNoneますが、アクセスは、辞書のようにハッシュするのではなく、単純なインデックス検索を介して行われます。

于 2011-03-11T20:16:22.603 に答える