1

我正在逐像素检测位图中的数字。每个图形都以一个像素的大小开始。大多数数字都在增长，但有些数字仍然很小。

我按顺序将这些数字收集在一个ArrayList. 在下一步中，我想减少删除小数字的列表。

第一步收集大约 1500 个图形。第二步删除了大约 1/3。

什么表现更好：

  1. 从列表中
    删除项目由于使用 a 删除项目性能更好LinkedList：
    • 我可以LinkedList在第一步中使用 a ，但随后构建此列表的性能比使用 the 更差ArrayList（因为创建LinkedList项目比向 an 添加对象更昂贵ArrayList）
      因此
    • 我仍然使用ArrayListwhich 每次都必须将已删除项目之后的项目复制到已删除项目的位置。为了减少要复制的项目数量，我可以从最后一个索引开始遍历列表。
  2. 建立一个只有更大数字的新列表
    • 我ArrayList用原始数字列表的 3/4 大小创建了一个新的初始化它，然后只将较大的数字添加到新列表中。

我想，使用这么几个项目，没有一个选项会带来可衡量的性能提升。但是对于更大数量的项目，什么表现更好呢？

4

4 回答 4

2

使用以下测试程序，我发现

数组列表

1000 个对象引用，从 arrayList 中删除 25%；

  • 从现有的数组列表中删除；0.565ms
  • 重新创建一个新的arrayList；0.573ms

100000 个对象引用，从 arrayList 中删除 25%；

  • 从现有的数组列表中删除；1028毫秒
  • 重新创建一个新的数组列表；8.66 毫秒
  • 重新创建一个新的数组列表（预先调整大小）；2毫秒

在小范围内这并不重要，在大范围内创建一个新列表是关键，最好是预先调整大小

哈希集

1000 个对象引用，从 arrayList 中删除 25%；

  • 从现有的哈希集中删除；0.602ms
  • 重新创建一个新的哈希集；2.64 毫秒

100000 个对象引用，从 arrayList 中删除 25%；

  • 从现有的哈希集中删除；28ms
  • 重新创建一个新的哈希集；37毫秒

在小规模上，从现有集合中移除似乎更快，但两者在重要的规模上都是可比的。

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import javax.vecmath.Vector3d;

public class Test {

        public static void main(String[] args){
            voidTestArrayList(100000);
            voidTestHashSet(100000);

            
        }
        

        
        public static void voidTestArrayList(int samples){
            {
                Collection<Vector3d> collectionArrayList=new ArrayList<Vector3d>();
                 preamble(collectionArrayList,samples);
                 testRemoveQuarter(collectionArrayList);
            }
            {
                Collection<Vector3d> collectionArrayList2=new ArrayList<Vector3d>();
                Collection<Vector3d> collectionArrayListDestination=new ArrayList<Vector3d>();
                preamble(collectionArrayList2,samples);

                testRetain3Quarter(collectionArrayList2,collectionArrayListDestination);
            }
            {
                Collection<Vector3d> collectionArrayList3=new ArrayList<Vector3d>();
                preamble(collectionArrayList3,samples);
                Collection<Vector3d> collectionArrayListDestination3=new ArrayList<Vector3d>(collectionArrayList3.size());
                testRetain3QuarterPresized(collectionArrayList3,collectionArrayListDestination3);
            }
        }
        
        public static void voidTestHashSet(int samples){
             Collection<Vector3d> collectionHashSet=new HashSet<Vector3d>();
             preamble(collectionHashSet,samples);
             testRemoveQuarter(collectionHashSet);
             
             Collection<Vector3d> collectionHashSet2=new HashSet<Vector3d>();
             Collection<Vector3d> collectionHashSetDestination=new HashSet<Vector3d>();
             preamble(collectionHashSet2,samples);
             
             testRetain3Quarter(collectionHashSet2,collectionHashSetDestination);
             
        }
        
        public static void voidTestRemoveFromArrayList(){
             Collection<Vector3d> collectionArrayList=new ArrayList<Vector3d>();
             preamble(collectionArrayList,1000);
             testRemoveQuarter(collectionArrayList);
        }
        
        
        public static void preamble(Collection<Vector3d> collection, int numberToAdd){
            //not part of timed test
            for(int i=0;i<numberToAdd;i++){
                collection.add(new Vector3d(Math.random(),Math.random(),Math.random()));
            }
        }
        
        public static void testRemoveQuarter(Collection<Vector3d> collection){
            Iterator<Vector3d> iterator=collection.iterator();
            
            int counter=0;
            while(iterator.hasNext()){
                counter++;
                iterator.next();
                if ((counter%4)==0){
                    counter=0;
                    iterator.remove();
                }
            }
        }
        
        public static void testRetain3QuarterPresized(Collection<Vector3d> collection, Collection<Vector3d> destinationCollection){
            testRetain3Quarter(collection, destinationCollection);
        }
        public static void testRetain3Quarter(Collection<Vector3d> collection, Collection<Vector3d> destinationCollection){
            Iterator<Vector3d> iterator=collection.iterator();
            
            int counter=0;
            while(iterator.hasNext()){
                counter++;
                Vector3d processing=iterator.next();
                if ((counter%4)!=0){
                    counter=0;
                    destinationCollection.add(processing);
                }
            }
        }
        
}

注意重要的是要注意，就集合而言，它包含对对象的引用，因此我对特定对象类的选择是无关紧要的

于 2013-10-02T12:33:09.580 回答
0

您应该对不同的 java.util.List 实现进行基准测试，重点关注添加和删除元素。

于 2013-10-02T12:07:39.430 回答
0

我建议一些这样的基准：

List<Object> arrayRemove = new ArrayList<Object>(initialMax);
List<Object> arrayCopy = new ArrayList<Object>((int) (initialMax * (1+retain)/2));
List<Object> linkedRemove = new LinkedList<Object>();
List<Object> linkedCopy = new LinkedList<Object>();

for (int i = 0; i < initialMax; i++) {
    arrayRemove.add(new Object());
    linkedRemove.add(new Object());
}

Random rnd = new Random();
//Begin benchmarking
for (int i = 0; i < initialMax; i++) {
    if (rnd.nextDouble() < retain) {
        linkedCopy.add(arrayRemove.get(i)); //1.
        // arrayCopy.add(arrayRemove.get(i)); //2. (same code but...)
    } else {
        // linkedRemove.remove(0); //3.
        // arrayRemove.remove(0); //4.
    }
}
// End benchmarking

你在哪里initialMax = 1500; retain = 2/3分别测试所有四种方法。
此外，当您的“数字”可以是随机顺序时，请考虑使用HashSet.

编辑

（基本）测试表明方法4没用，其他的速度差不多：

import java.util.ArrayList;
import java.util.Date;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;


public class Test {
private static final int initialMax = 150000;
private static final double retain = 2/3;

public static void main(String[] args) {
    List<Object> arrayRemove = new ArrayList<Object>(initialMax);
    List<Object> arrayCopy = new ArrayList<Object>((int) (initialMax * (1+retain)/2));
    List<Object> linkedRemove = new LinkedList<Object>();
    List<Object> linkedCopy = new LinkedList<Object>();

    for (int i = 0; i < initialMax; i++) {
        arrayRemove.add(new Object());
        linkedRemove.add(new Object());
    }

    Random rnd = new Random();
    //Begin benchmarking
    Date[] ds = new Date[5];
    ds[0] = new Date();
    for (int i = 0; i < initialMax; i++) {
        if (rnd.nextDouble() < retain) {
            linkedCopy.add(arrayRemove.get(i)); //1.
            // arrayCopy.add(arrayRemove.get(i)); //2. (same code but...)
        } else {
            // linkedRemove.remove(i); //3.
            // arrayRemove.remove(i); //4.
        }
    }
    ds[1] = new Date();
    for (int i = 0; i < initialMax; i++) {
        if (rnd.nextDouble() < retain) {
            // linkedCopy.add(arrayRemove.get(i)); //1.
            arrayCopy.add(arrayRemove.get(i)); //2. (same code but...)
        } else {
            // linkedRemove.remove(i); //3.
            // arrayRemove.remove(i); //4.
        }
    }
    ds[2] = new Date();
    for (int i = 0; i < initialMax; i++) {
        if (rnd.nextDouble() < retain) {
            // linkedCopy.add(arrayRemove.get(i)); //1.
            // arrayCopy.add(arrayRemove.get(i)); //2. (same code but...)
        } else {
            linkedRemove.remove(0); //3.
            // arrayRemove.remove(0); //4.
        }
    }
    ds[3] = new Date();
    for (int i = 0; i < initialMax; i++) {
        if (rnd.nextDouble() < retain) {
            // linkedCopy.add(arrayRemove.get(i)); //1.
            // arrayCopy.add(arrayRemove.get(i)); //2. (same code but...)
        } else {
            // linkedRemove.remove(0); //3.
            arrayRemove.remove(0); //4.
        }
    }
    ds[4] = new Date();
    // End benchmarking
    long[] diff = new long[4];
    System.out.println("Results:");
    for (int i = 0; i < 4; i++) {
        diff[i] = (ds[i + 1].getTime() - ds[i].getTime());
        System.out.println((i+1) + ".: " + diff[i]);
    }
}
}

结果是

结果：
1.：0-15 2.：0
3.：0-15 4.：6895

于 2013-10-02T12:25:43.343 回答
0

如果你坚持ArrayList我会说第二个选项更快。但是您应该自己对其进行基准测试并尝试该LinkedList变体。据我所知， JavaLinkedList是一个双链表，因此在末尾添加元素往往比使用ArrayList. 特别是如果您不知道初始大小。

于 2013-10-02T12:11:06.183 回答