Lambda表现有差异吗？

Question

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

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

• 给定一万个条目的数组，删除某些索引的更快方法是什么：在内部进行if测试的Lamba表达式或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产生如此大的差异。

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

• 这是该方法的特定行为List吗？其他Lambda表达式还会产生这种随机表现吗？

Answer 1

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

• removeIf在ArrayList。
• removeIf在LinkedList。
• 迭代器iterator.remove()上ArrayList。
• 迭代器iterator.remove()上LinkedList。

基准测试的目的是表明removeIf和迭代器应提供相同的性能，但对于而言并非如此ArrayList。

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

现在考虑一个ArrayList在内部使用数组保存元素的。每次调用时remove，索引后的其余元素都必须移动一个；因此每次必须复制很多元素。当使用迭代器遍历the
ArrayList且我们需要删除一个元素时，此复制需要一次又一次地进行，这会非常缓慢。对于a
LinkedList，情况并非如此：删除元素时，唯一的更改是指向下一个元素的指针。

那么，为什么在a
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);
    }

}