2

Scalaで書かれたAndroid用のゲームには、プールしたいオブジェクトがたくさんあります。最初に、アクティブ（表示）インスタンスと非アクティブインスタンスの両方を同じプールに入れようとしました。これは、GCを引き起こし、低速であるフィルタリングのために低速でした。

そこで、2つのデータ構造を使用するようになりました。そのため、無料のインスタンスを取得する必要がある場合は、最初のインスタンスをパッシブプールから取得し、それをアクティブプールに追加します。また、アクティブプールへのランダムアクセスを高速化します（インスタンスを非表示にする必要がある場合）。これには2つのArrayBufferを使用しています。

だから私の質問は、この状況に最適なデータ構造はどれかということです。そして、その（またはそれらの）特定のデータ構造をどのように使用して追加および削除し、GCを可能な限り回避し、Android（メモリおよびCPUの制約）で効率的にする必要がありますか？

4

2 に答える 2

2

最適なデータ構造は、追加する内部リストです。

var next: MyClass

すべてのクラスに。非アクティブなインスタンスは、通常「フリーリスト」と呼ばれるものになり、アクティブなインスタンスは、単一リンクリストになりListます。

このように、オーバーヘッドはオブジェクトごとに正確に1つのポインターになり（実際にはそれより少なくなることはありません）、割り当てやGCはまったくありません。（フリーリストが長くなりすぎた場合に、フリーリストの一部または全部を破棄して独自に実装したい場合を除きます。）

コレクションの良さを失うことはありますが、クラスをイテレータにすることができます。

def hasNext = (next != null)

それを考えると、必要なのはそれだけですvar。（まあ、そしてextends Iterator[MyClass]。）プールのサイズが本当に非常に小さい場合は、シーケンシャルスキャンで十分に高速になります。

アクティブプールが大きすぎてリンクリストを順次スキャンできず、要素が頻繁に追加または削除されない場合は、それらをに保存する必要がありますArrayBuffer（必要に応じて要素を削除する方法を知っています）。アイテムを削除したら、それをフリーリストに入れます。

アクティブなプールが急速に切り替わる場合（つまり、追加/削除の数がランダムアクセスの数と同じである場合）、ある種の階層構造が必要です。Scalaは、でかなりうまく機能する不変のものを提供しますVectorが、変更可能なものはありません（2.9以降）。Javaにも本当に適したものはありません。独自のツリーを構築したい場合は、残っている子の数を追跡するノードを備えた赤黒またはAVLツリーがおそらく最適な方法です。（インデックスでアクセスするのは簡単なことです。）

于 2012-04-18T12:12:33.820 に答える
1

私の考えに言及すると思います。とにかく、filterメソッドとmapメソッドはコレクション全体を反復処理するので、それを単純化して、コレクションに対して単純なスキャンを実行することもできます（アクティブなインスタンスを探すため）。ここを参照してください：https ：//github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/TraversableLike.scala

def filter(p: A => Boolean): Repr = {
  val b = newBuilder
  for (x <- this)
    if (p(x)) b += x
  b.result
}

n = 31のナイーブスキャン（32ビットのIntビットマップを超える必要はない）、フィルター/ foreachスキャン、フィルター/マップスキャン、ビットマップスキャンを使用して、いくつかのテストを実行しました。セットの33％をランダムにアクティブに割り当てます。私は、正しい値などを見ないことによって不正行為をしていないことを再確認するために、実行中のカウンターを持っていました。ちなみに、これはAndroidでは動作していません。

アクティブな値の数によっては、ループに時間がかかりました。

結果：

naive scanned a million times in: 197 ms (sanity check: 9000000)
filter/foreach scanned a million times in: 441 ms (sanity check: 9000000)
map scanned a million times in: 816 ms (sanity check: 9000000)
bitmap scanned a million times in: 351 ms (sanity check: 9000000)

ここにコードを記述します-自由に分解するか、もっと良い方法があるかどうか教えてください-私はscalaにかなり慣れていないので、気持ちが損なわれることはありません：https ://github.com/wfreeman/ScalaScanPerformance/blob/ master / src / main / scala / scanperformance / ScanPerformance.scala

于 2012-04-18T22:07:44.870 に答える