从列表中删除不相关的项目与使用相关项目建立新列表

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

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

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

什么表现更好：

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

我想，使用如此多的项目，没有一个选项会导致可衡量的性能提升。但是，对于大量物品，什么表现更好？

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

数组列表

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

从现有数组列表中删除;0.565ms
重新创建新数组列表;0.573ms

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

从现有数组列表中删除;1028ms
重新创建新的数组列表;8.66ms
重新创建一个新的数组列表(预设大小(;2ms

在

小尺度上这并不重要，在大尺度上，创建新列表是关键，最好是预设大小

哈希集

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

从现有哈希集中删除;0.602ms
重新创建新的哈希集;2.64ms

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

从现有哈希集中删除;28ms
重新创建新的哈希集;37ms

在小尺度上，

从现有集合中删除似乎更快，但在重要的尺度上两者都是可比较的。

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);
                }
            }
        }
        
}

注意

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

你应该对

不同的java.util.List实现进行基准测试，专注于addig和删除元素。

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

我建议像这样的基准测试：

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

数组列表

哈希集

编辑

相关内容

最新更新

热门标签：