lambda表现的差异？

Question

这不是我的问题的重复.我检查了它,它更多的是关于内部匿名类.

我对Lambda表达式很好奇并测试了以下内容:

• 给定一万个条目的数组,删除某些索引的速度会更快:Lamba表达式或带有if测试的For-Loop内部？

第一个结果并不令人惊讶,因为我不知道我会想出什么:

final int NUMBER_OF_LIST_INDEXES = 10_000;
List<String> myList = new ArrayList<>();
String[] myWords = "Testing Lamba expressions with this String array".split(" ");

for (int i = 0 ; i < NUMBER_OF_LIST_INDEXES ; i++){
    myList.add(myWords[i%6]);
}

long time = System.currentTimeMillis();

// BOTH TESTS WERE RUN SEPARATELY OF COURSE
// PUT THE UNUSED ONE IN COMMENTS WHEN THE OTHER WAS WORKING

// 250 milliseconds for the Lambda Expression
myList.removeIf(x -> x.contains("s"));

// 16 milliseconds for the traditional Loop
for (int i = NUMBER_OF_LIST_INDEXES - 1 ; i >= 0 ; i--){
    if (myList.get(i).contains("s")) myList.remove(i);
}
System.out.println(System.currentTimeMillis() - time + " milliseconds");

但后来,我决定将常数更改NUMBER_OF_LIST_INDEXES为一百万,结果如下:

final int NUMBER_OF_LIST_INDEXES = 1_000_000;
List<String> myList = new ArrayList<>();
String[] myWords = "Testing Lamba expressions with this String array".split(" ");

for (int i = 0 ; i < NUMBER_OF_LIST_INDEXES ; i++){
    myList.add(myWords[i%6]);
}

long time = System.currentTimeMillis();

// BOTH TESTS WERE RUN SEPARATELY OF COURSE
// PUT THE UNUSED ONE IN COMMENTS WHEN THE OTHER WAS WORKING

// 390 milliseconds for the Lambda Expression
myList.removeIf(x -> x.contains("s"));

// 32854 milliseconds for the traditional Loop
for (int i = NUMBER_OF_LIST_INDEXES - 1 ; i >= 0 ; i--){ 
    if (myList.get(i).contains("s")) myList.remove(i);
}
System.out.println(System.currentTimeMillis() - time + " milliseconds");

为了使事情更简单,以下是结果:

|        |  10.000 | 1.000.000 |
| LAMBDA |  250ms  |   390ms   | 156% evolution
|FORLOOP |   16ms  |  32854ms  | 205000+% evolution

我有以下问题:

• 这背后的魔力是什么？当使用的索引是*100时,我们如何为数组而不是lambda带来如此大的差异.

• 在性能方面,我们如何知道何时使用Lambdas以及何时坚持使用传统方式处理数据？

• 这是该方法的特定行为List吗？其他Lambda表达式是否也会产生像这样的随机性能？

Answer 1

因为remove(index)非常昂贵:)它需要复制和移动其余的元素,这在你的情况下多次完成.

虽然removeIf(filter)不需要这样做.它可以扫描一次并标记要删除的所有元素; 然后最后阶段将幸存者复制到列表头部一次.

Answer 2

我写了一个JMH基准来测量它.它有4种方法:

• removeIf在...上ArrayList.
• removeIf在...上LinkedList.
• 迭代器iterator.remove()上的ArrayList.
• 迭代器iterator.remove()上的一个LinkedList.

基准测试的要点是显示removeIf和迭代器应该提供相同的性能,但事实并非如此ArrayList.

默认情况下,removeIf在内部使用迭代器来删除元素,因此我们应该期望使用removeIf和使用相同的性能iterator.

现在考虑在ArrayList内部使用数组来保存元素.每次调用时remove,索引后的剩余元素都必须移动一个; 所以每次都要复制很多元素.当迭代器用于遍历ArrayList并且我们需要删除元素时,这种复制需要一次又一次地发生,这使得它非常慢.对于a LinkedList,情况并非如此:当删除元素时,唯一的变化是指向下一个元素的指针.

那么,为什么是removeIf快上ArrayList作为一个LinkedList？因为它实际上被覆盖并且它不使用迭代器:代码实际上标记了要在第一遍中删除的元素,然后在第二遍中删除它们(移动其余元素).在这种情况下可以进行优化:每次需要移除剩余元素时,我们只会在知道需要删除的所有元素时执行一次.

结论:

• removeIf 当需要删除与谓词匹配的每个元素时,应该使用它.
• remove 应该用于删除单个已知元素.

基准结果:

Benchmark                            Mode  Cnt      Score      Error  Units
RemoveTest.removeIfArrayList         avgt   30      4,478 ±   0,194  ms/op
RemoveTest.removeIfLinkedList        avgt   30      3,634 ±   0,184  ms/op
RemoveTest.removeIteratorArrayList   avgt   30  27197,046 ± 536,584  ms/op
RemoveTest.removeIteratorLinkedList  avgt   30      3,601 ±   0,195  ms/op

基准测试:

@Warmup(iterations = 5, time = 1000, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 10, time = 1000, timeUnit = TimeUnit.MILLISECONDS)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Fork(3)
@State(Scope.Benchmark)
public class RemoveTest {

    private static final int NUMBER_OF_LIST_INDEXES = 1_000_000;
    private static final String[] words = "Testing Lamba expressions with this String array".split(" ");

    private ArrayList<String> arrayList;
    private LinkedList<String> linkedList;

    @Setup(Level.Iteration)
    public void setUp() {
        arrayList = new ArrayList<>();
        linkedList = new LinkedList<>();
        for (int i = 0 ; i < NUMBER_OF_LIST_INDEXES ; i++){
            arrayList.add(words[i%6]);
            linkedList.add(words[i%6]);
        }
    }

    @Benchmark
    public void removeIfArrayList() {
        arrayList.removeIf(x -> x.contains("s"));
    }

    @Benchmark
    public void removeIfLinkedList() {
        linkedList.removeIf(x -> x.contains("s"));
    }

    @Benchmark
    public void removeIteratorArrayList() {
        for (ListIterator<String> it = arrayList.listIterator(arrayList.size()); it.hasPrevious();){
            if (it.previous().contains("s")) it.remove();
        }
    }

    @Benchmark
    public void removeIteratorLinkedList() {
        for (ListIterator<String> it = linkedList.listIterator(linkedList.size()); it.hasPrevious();){
            if (it.previous().contains("s")) it.remove();
        }
    }

    public static void main(String[] args) throws Exception {
         Main.main(args);
    }

}