1

オブジェクトのリストを描画するゲーム ループがあります。このリストは「mylist」と呼ばれ、1000 個のオブジェクトのようなものを保持します。 2番目。

リストの容量が十分に大きい場合、リストへの挿入が実質的に無料であることが正しく理解されている場合、問題は O(n) である削除にあります。削除後。

すべての削除を集約してフレームごとに 1 回作成できれば、mylist.Except(listToRemove) を使用し、これは O(n) になるため効率的です。しかし、残念ながら私にはそれができません。

リスト内のオブジェクトを見つける必要があるため、リンクされたリストも問題があります。

誰もがより良い提案をしていますか?

4

4 に答える 4

3

はどうHashSetですか？O(1)挿入と取り外しをサポートします。順序付けが必要な場合は、ノードをすばやく見つけることができるツリー データ構造またはLinkedListプラス aを使用します。Dictionary

BCL にはSortedListと と がSortedSetありSortedDictionaryます。1つを除くすべてが非常に遅かったのですが、どれが「良い」ものだったのか思い出せません。内部的にはツリーベースです。

于 2013-03-23T14:28:31.940 に答える
0

検索を行っている場合、最善の策は、Dictionary平均ケースの O(1) と最悪ケースの O(n) のいずれかを使用することです (同じバケットにハッシュする場合)。

順序を維持する必要がある場合は、バランスの取れた二分探索木の任意の実装を使用でき、パフォーマンスは O(logn) になります。

.NET では、これは単純に次のようになります。

辞書- 挿入/削除 O(1) (平均ケース)

SortedDictionary - 順序付き操作、挿入/削除の順序を保持O(logn)

于 2013-03-23T14:30:29.857 に答える
0

したがって、理想的には、 O(1)またはO(log n)の削除と挿入を持つデータ構造を使用する必要があります。ディクショナリ型のデータ構造は、一定の平均ケースの挿入および削除時間の複雑さのため、おそらく理想的です。ゲームオブジェクトの基本クラスをオーバーライドHashSetしてからオーバーライドすることをお勧めします。GetHashCode()

ここでは、さまざまなディクショナリ/ハッシュ テーブルのデータ構造について詳しく説明します。

時間の複雑さ

以下は、すべての「辞書のような」データ構造とその時間の複雑さです。

Type              Find by key  Remove      Add
HashSet           O(1)*        O(1)*     O(1)**
Dictionary        O(1)*        O(1)*     O(1)**
SortedList        O(log n)     O(n)      O(n)
SortedDictionary  O(log n)     O(log n)  O(log n)

*O(n) 衝突あり
**O(n) 衝突あり、または配列の容量を超えて追加する場合。

ハッシュセットと辞書

HashSetaと aの違いはDictionary、Dictionary は a で機能するのKeyValuePairに対し、aHashSetではキーはオブジェクト自体 (そのGetHashCode()メソッド) であるということです。

SortedList と SortedDictionary の比較

注文を維持する必要がある場合にのみ、これらを考慮する必要があります。違いは、SortedDictionary赤黒ツリーをSortedList使用し、そのキーと値に並べ替えられた配列を使用することです。

参考文献

于 2013-03-23T14:30:46.710 に答える
0

パフォーマンスに関しては、どのような種類のリストからも何も挿入したり削除したりしないことで、おそらく最良の結果が得られるでしょう。十分な大きさの配列を割り当て、すべてのオブジェクトにレンダリングするかどうかのタグを付けます。

ただし、要件を考えると、これはおそらく時期尚早の最適化です。1000 要素のリスト全体を 1 秒間に 30 回再作成しても、パフォーマンスの低下は見られません。

Braidの作成者による、インディペンデント ビデオ ゲームでの適切なデータ構造の使用に関するこのプレゼンテーションのスライドを読むことをお勧めします。（tl; drはすべてに配列を使用するだけです）。

于 2013-03-23T14:48:14.700 に答える