2

在一个用 Scala 编写的 Android 游戏中，我有很多我想要合并的对象。首先，我尝试在同一个池中同时拥有活动（可见）和非活动实例；这很慢，因为过滤会导致 GC 并且很慢。

所以我转而使用两种数据结构，所以当我需要获得一个免费实例时，我只需从被动池中取出第一个并将其添加到活动池中。我还快速随机访问活动池（当我需要隐藏实例时）。我为此使用了两个 ArrayBuffers。

所以我的问题是：哪种数据结构最适合这种情况？以及应该如何使用那个（或那些）特定的数据结构来添加和删除以尽可能避免 GC 并在 Android 上高效（内存和 cpu 限制）？

4

2 回答 2

2

最好的数据结构是内部列表，您可以在其中添加

var next: MyClass

到每一堂课。然后，非活动实例成为通常所谓的“空闲列表”，而活动实例成为单链表 la List。

这样，您的开销恰好是每个对象一个指针（您实际上不能得到任何更少的指针），并且根本没有分配或 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/主/src/main/scala/scanperformance/ScanPerformance.scala

于 2012-04-18T22:07:44.870 回答