lambda性能的差异？

Question

这不是重复我的问题，我查了一下，更多的是关于内部匿名类。

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

• 如果给定一个数组中有1000个索引，那么对于一个包含1000个索引的循环，删除哪个条目会更快

最初的结果并不令人惊讶，因为我不知道自己会想出什么：

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

但后来，我决定将常量列表索引的数量改为一百万，结果如下：

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

我认为您看到的性能差异可能更多地是由于removeIf在内部使用迭代器，而不是在for循环中使用get和remove。本PAQ中的答案提供了一些关于迭代器好处的好信息。

河口。io的答案是正确的，您可以在这里看到removeIf的代码。如果它进行两次传递，以避免反复移动其余元素。

Answer 2

我写了一个JMH基准来衡量这一点。其中有4种方法：

• ArrayList上的removeIf
• LinkedList上的removeIf
• 带有迭代器的迭代器。在ArrayList上删除（）
• 带有迭代器的迭代器。在链接列表上删除（）

基准测试的目的是显示RemveIF和迭代器应该提供相同的性能，但是ArrayList的情况并非如此。

默认情况下，RemveIF在内部使用迭代器来删除元素，因此我们应该期望RemveIF和迭代器具有相同的性能。

现在考虑一个<代码> ARAYLISTAB/COD>，它使用数组内部保存元素。每次我们调用remove，索引后的剩余元素必须移位一；所以每次都要复制很多元素。当使用迭代器遍历ArrayList时，我们需要删除一个元素，这种复制需要一次又一次地进行，这使得复制非常缓慢。对于LinkedList，情况并非如此：删除一个元素时，唯一的更改是指向下一个元素的指针。

那么为什么ArrayList上的removeIf与LinkedList上的一样快呢？因为它实际上是被重写的，并且不使用迭代器：代码实际上在第一个过程中标记要删除的元素，然后在第二个过程中删除它们（移动剩余的元素）。在这种情况下，优化是可能的：我们只在知道所有需要删除的元素时才进行一次，而不是每次需要删除的元素时都移动剩余的元素。

结论：

• 当需要删除与谓词匹配的所有元素时，应使用removeIf

基准测试结果：

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

}

Answer 3

因为remove（index）非常昂贵：）它需要复制和移动其余的元素，这在您的情况下会执行多次。

而removeIf（过滤器）不需要这样做。它可以扫描一次并标记所有要删除的元素；最后一个阶段只会将幸存者复制到名单的最前面一次。