在Scala中将实例从Set移动到另一个

Question

在游戏中,我需要密切关注我的哪些精灵正在使用中.当我同时"激活"多个精灵时,我想将它们从我的传输passivePool到activePool两个都是不可变的HashSets(好吧,我会每次都准确地创建新的集合).所以我的基本想法是:

activePool ++= passivePool.take(5)
passivePool = passivePool.drop(5)

但是阅读scala文档我猜我所采取的5可能与5我然后丢弃的不同.这绝对不是我想要的.我也可以这样说:

val moved = passivePool.take(5)
activePool ++= moved
passivePool --= moved

但是因为这是我需要在有限的设备(Android手机)上实时完成每一帧的事情,我想这会慢得多,因为我必须逐一搜索每个moved精灵passivePool.

任何聪明的解决方案？还是我错过了一些基本的东西？请记住效率是这里的主要关注点.而且我不能使用Lists而不是Sets,因为当游戏中的精灵被破坏时,我还需要从activePools中随机访问精灵.

Answer 1

没有像基准测试来获得这些问题的答案.让我们取100套1000的尺寸,一次放下5个,直到它们为空,看看需要多长时间.

passivePool.take(5); passivePool.drop(5)                    // 2.5   s
passivePool.splitAt(5)                                      // 2.4   s
val a = passivePool.take(5); passivePool --= a              // 0.042 s
repeat(5){ val a = passivePool.head; passivePool -= a }     // 0.020 s

到底是怎么回事？

事情以这种方式工作的原因是immutable.HashSet被构建为具有优化(有效O(1))添加和删除操作的散列特里,但许多其他方法没有重新实现; 相反,它们继承自不支持添加/删除的集合,因此无法获得免费的有效方法.因此,它们主要从头开始重建整个哈希集.除非你的哈希集中只有少数元素,否则这是个坏主意.(与套装尺寸为1000的50-100x减速相比,一套100的尺寸"仅"减速6-10倍....)

所以,底线:直到库得到改进,以"低效"的方式做到这一点.你会大大加快.