在Java中防止ArrayList迭代器的分配

3
我正在编写我的第一个Android游戏,读了一篇有关优化游戏的长篇演示之后,我开始检查我的分配情况。我已经成功地除掉了除了ArrayList在创建for(Object o : m_arrayList)约定的隐式迭代器时所做的所有游戏内分配。
由于我所有的游戏对象、AI实体等都是为了方便而存储在这些ArrayList中,因此有相当多的这些迭代/分配。
那么我的选择是什么?
1.理论上,我可以指定合理的上限并使用数组,但我喜欢ArrayList的特性,例如存在和删除操作,使代码更加简洁明了。
2.重写ArrayList并提供自己的iterator()实现,返回一个类成员而不是每次使用时分配新的迭代器类型。
为了方便起见,我更愿意选择选项2,但我试着做了一下,遇到了问题。有人有上述第二个选项的示例吗?我曾在继承泛型类时遇到了类型冲突的问题。
第二个问题是还有其他避免这些分配的方法吗?
附加问题是,是否有人知道ArrayList预先分配一定数量的内存槽以适应一定量(在ctor中指定或作为可移动值指定),只要保持在这些界限内就永远不需要进行其他分配?即使在clear()之后?
提前感谢您的帮助,抱歉内容很多,但我认为这些信息对许多人可能有用。

我没有看到任何关于测试/分析的提及。这是否真的是性能瓶颈? - Thomas
根据您的额外问题,在没有初始容量参数构造的ArrayList中,列表最初会为10个对象分配空间,并在需要时按初始容量增长。您可以调用 trimToSize 来节省空间。 - Pedantic
对于奖励问题,ArrayList默认分配容量为10。http://stackoverflow.com/a/4666050/340068 - Alok Kulkarni
@Thomas。有可能,也有可能不会,在低规格手机上偶尔会出现暂停,我只能将其归因于垃圾回收,但不能100%确认。但是我认为,如果我可以用其他类型替换ArrayList,那么这将是一个快速解决方案,而且没有负面影响。 - makar
2个回答

6
使用位置迭代。
for ( int i = 0, n = arrayList.size( ); i < n; ++i )
{
   Object val = arrayList.get( i );
}

Java 5之前是这样做的。

为了预分配。

ArrayList arrayList = new ArrayList( numSlots );

或者在运行时

arrayList.ensureCapacity( numSlots );

作为奖励-> http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html

(含义是给出了一个有用的链接)

谢谢,我确实考虑过这种方法,事实上以前也用过类似的方法,但在做了一些研究后就放弃了。似乎与迭代器相比,使用get(i)函数进行迭代速度较慢。权衡之后可能会节省分配……也许需要进行实验。 - makar
2
@makar。实际上对于 ArrayListget 方法会比使用迭代器更快,因为它直接引用基础数组的位置元素。 - Alexander Pogrebnyak
在Java 5之前,它并不是以这种方式完成的。在Java中,迭代器已经存在了很长时间。 - jtahlborn
有趣,我会尝试找出让我产生其他想法的原因,如果我确实曾经这样想过的话。也许我当时是在想其他集合。 - makar
@jtahlborn。您是正确的!在Java 5之前就有迭代器了,但for(Object obj:collection)循环不是。 - Alexander Pogrebnyak
当然我意识到了,但在那之前我会使用迭代器而不是你展示的“int i”循环。 - jtahlborn

2
我先回答奖励问题:是的,ArrayList会预先分配插槽。它有一个构造函数,可以将所需的插槽数作为参数传递,例如new ArrayList(1000)。clear不会释放任何插槽。
返回共享迭代器引用存在一些问题。主要问题是你无法知道何时将迭代器重置为第一个元素。考虑下面的代码:
CustomArrayList<Whatever> list = ...
for (Whatever item : list) {
    doSomething();
}
for (Whatever item : list) {
    doSomethingElse();
}

CustomArrayList类不知道它的共享迭代器在两个循环之间应该被重置。如果您只是在每次调用iterator()时重置它,那么您将在这里遇到问题:

for (Whatever first : list) {
    for (Whatever second : list) {
        ...
    }
}

在这种情况下,您不需要在调用之间重置迭代器。
@Alexander Progrebnyak的答案可能是在不使用迭代器的情况下遍历列表的最佳方法;只需确保您具有快速的随机访问(即永远不要使用LinkedList)。
我还想指出,您正在进行一些相当繁重的微观优化。我建议您对代码进行分析,找出是否分配迭代器是一个真正的问题,然后再投入大量时间。即使在游戏中,您也应该只优化需要优化的部分,否则您可能会花费很多天时间将几毫秒从一分钟的操作中削减下来。

感谢您提供详细的答案。我知道返回单个实例迭代器所带来的风险,但如果这意味着停止分配,我很乐意遵守所需的规则。至于您提到的另一点,我一直非常小心,不在游戏中进行任何迭代,因此看到所有这些隐式分配都在喷出,有点令人沮丧!我一直抵制过早进行大量优化的冲动,但是觉得如果我能够将我的ArrayLists换成另一种类型,那么这将是一个快速修复,对其他任何事情都没有影响。但是我接受了您的观点! - makar
不要进行任何分配。不要进行迭代。 - makar

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接