logo标签列表

数组访问优化

javaandroidarraysoptimization
3

我有一个10x10的Java数组，其中一些项目未被使用，我需要遍历所有元素作为方法的一部分。做什么比较好：

  1. Go through all elements with 2 for loops and check for the nulltype to avoid errors, e.g.

    for(int y=0;y<10;y++){
    for(int x=0;x<10;x++){
       if(array[x][y]!=null)
            //perform task here
    }
}

  2. Or would it be better to keep a list of all the used addresses... Say an arraylist of points?

  3. Something different I haven't mentioned.

我期待任何回答 :)

2
取决于情况。但是最好将您的for循环放在另一个方向上。 - Tom Hawtin - tackline
循环结构换一下顺序可能更好？如果它们大小相等的话，不确定是否有任何区别。另外，忘了说，我正在开发Android平台。 - Ljdawson
1
从性能方面来看，最好将所有内容提取到本地变量中，避免查找。 - Ljdawson
根据编译器和CPU的不同，调整循环顺序可能会带来很大的性能提升。详见http://lbrandy.com/blog/2009/03/more-cache-craziness/。 - Michael Myers
我认为在ArrayList中查找的成本比空指针检查更高，因为分支预测器在if语句中的工作效果更好。如果数组大小是固定的，那么JIT可能会展开循环。 - Denis Tulskiy
噢，关于Android指南中提到的增强型for循环。上次我检查时，它在数组中比常规for循环慢得多，甚至在ArrayLists中更慢。 - Denis Tulskiy
6个回答
5
任何你尝试的解决方案都需要在尽可能接近生产环境的受控条件下进行测试。由于Java的特性，你需要运行你的代码一段时间以获取可靠的性能统计数据，但我相信你已经知道了这一点。
话虽如此，还是有几个可以尝试的优化方法，我用过并且成功地优化了我的Java代码（但不适用于Android JVM）。
for(int y=0;y<10;y++){
    for(int x=0;x<10;x++){
       if(array[x][y]!=null)
            //perform task here
    }
}

应该在任何情况下重新制作

for(int x=0;x<10;x++){
    for(int y=0;y<10;y++){
       if(array[x][y]!=null)
            //perform task here
    }
}

通常，通过缓存行引用可以提高性能。假设数组的类型为Foo[][]：

for(int x=0;x<10;x++){
    final Foo[] row = array[x];
    for(int y=0;y<10;y++){
       if(row[y]!=null)
            //perform task here
    }
}

使用final修饰变量本来是为了帮助JVM优化代码的，但我认为现代JIT Java编译器在许多情况下可以自行判断变量在代码中是否被更改。另一方面，有时这可能更有效率，尽管这肯定会使我们进入微观优化领域：

Foo[] row;
for(int x=0;x<10;x++){
    row = array[x];
    for(int y=0;y<10;y++){
       if(row[y]!=null)
            //perform task here
    }
}

如果您不需要知道元素的索引来执行任务，可以这样编写：

for(final Foo[] row: array){
    for(final Foo elem: row
       if(elem!=null)
            //perform task here
    }
}

另一种尝试是将数组展平并将元素存储在 Foo[] 数组中，确保最大的引用局部性。您无需担心内部循环，但在引用特定数组元素时需要进行一些索引算术运算（而不是循环整个数组）。根据您执行此操作的频率，它可能有益也可能没有益处。
由于大多数元素都不为空，将它们保留为稀疏数组对您没有好处，因为您会失去引用局部性。
另一个问题是空值测试。空值测试本身的成本不高，但其后面的条件语句成本很高，因为代码中会出现分支，并且在错误的分支预测上浪费时间。您可以使用“null 对象”，在此对象上执行任务将成为非操作或其他同样良性的操作。根据您要执行的任务，它可能有效也可能无效。
希望这有所帮助。
干杯，看到另一个关于这种事情的观点总是很好的，以确保。也感谢其他所有人！ - Ljdawson
我认为在没有进行任何分析的情况下给出这样的建议有些危险。对JVM优化行为做出广泛的断言往往会导致错误。我的理解是，'final'不再是一个重要的优化关键字，即使没有使用该关键字，JVM也能够进行相同的优化。我也怀疑Dawson通过删除if-null检查能够实现收益。它必须是非常简洁的代码才能克服BNE的成本，特别是因为元素通常不会为空。最重要的是，先进行分析，然后再做断言 :) - sooniln
请仅返回翻译的文本：PS. 关于最后一段，我写道空值检查本身应该很便宜。 - quant_dev
1

针对一百个元素，使用任何经典的稀疏数组实现可能不值得。然而，你没有提及你的数组有多稀疏，所以进行分析并查看跳过空项所需花费的时间与其他处理相比如何。

（正如Tom Hawtin - tackline所提到的），当使用一个数组的数组时，尝试循环遍历每个数组的成员，而不是循环遍历不同数组的相同索引。不过，并非所有算法都允许你这样做。

for ( int x = 0; x < 10; ++x ) {
    for ( int y = 0; y < 10; ++y ) {
       if ( array[x][y] != null )
            //perform task here
    }
}

或者

for ( Foo[] row : array ) {
    for ( Foo item : row ) {
       if ( item != null )
            //perform task here
    }
}

根据您所执行的操作的复杂性，使用空对象而不是测试null可能更好。不要使用模式的多态版本 - 多态分派至少会花费与测试和分支相同的代价 - 但如果您正在对属性求和，则具有零值的对象在许多CPU上可能更快。

double sum = 0;

for ( Foo[] row : array ) {
    for ( Foo item : row ) {
       sum += item.value();
    }
}

关于适用于Android的情况，我不确定；你需要进行测试和分析以进行任何优化。
1

使用 List 要比数组更好，尤其是你可能不会使用整个数据集。这有几个优点。

  1. 你不需要检查 null 值，并且不会意外地尝试使用 null 对象。
  2. 在不分配可能不会使用的内存的情况下更加内存高效。
我选择了多维数组，因为很可能会使用到所有的位置。我所做的工作是为Android平台设计的，对象的创建非常昂贵，所以最好提前保留空间以获得实时性能。 - Ljdawson
使用现代JVM，空指针检查非常快，因此这不是一个问题。他只需要记得检查它们即可。 - quant_dev
好的，我明白了。在这种情况下，你正在处理经典的空间与性能之间的问题。如果你需要性能，就得忍受一些影响。 - AlbertoPL
另一方面，代码分支可能会降低性能，因此，使用避免条件执行代码的解决方案可能更好。 - quant_dev
我建议编辑问题并说明您正在优化性能，这样人们就不必深入评论中查看您要寻找的优化类型。 - AlbertoPL
0
持有一个点的ArrayList将是“过度工程”这个问题。您有一个多维数组；最好的迭代方法是使用两个嵌套的for循环。除非您可以更改数据的表示方式，否则这大致上是效率最高的。
只需确保按行顺序而不是列顺序进行操作。
我的想法完全一样，特别是在向ArrayList添加或删除内容时，会将内容复制到新的数组中... - Ljdawson
0

这取决于你的矩阵是多么稀疏/密集。

如果它是稀疏的，最好存储一个点列表；如果它是密集的，使用2D数组。如果介于两者之间，可以采用混合解决方案，存储子矩阵列表。

无论如何，这个实现细节应该隐藏在一个类中，这样你的代码也可以随时在这些表示之间进行转换。

我建议你不要在没有使用真实应用程序进行分析的情况下选择任何一种解决方案。

很可能会很密集，这是一个针对Android平台的泡泡龙克隆游戏。 - Ljdawson
0

我同意使用带有空测试的数组是最好的方法，除非您期望稀疏填充的数组。

原因如下：

1- 对于密集数组来说更节省内存（列表需要存储索引）

2- 对于密集数组来说更计算效率高（您只需要将刚刚检索到的值与NULL进行比较，而不必还要从内存中获取索引）。

此外，一个小建议，在Java中，如果可能的话，您通常最好使用1D数组来模拟多维数组（2D中的正方形/矩形数组）。每次迭代只发生一次边界检查，而不是两次。不确定这是否仍适用于Android VM，但这通常是一个问题。无论如何，如果循环不是瓶颈，则可以忽略它。

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