Sự khác biệt trong các buổi biểu diễn lambda?

Question

This không trùng lặp với câu hỏi của tôi. Tôi đã kiểm tra nó và nó là nhiều hơn về các lớp ẩn danh bên trong.

tôi rất tò mò về các biểu thức Lambda và thử nghiệm như sau:

• Với một mảng của vạn mục, những gì sẽ là nhanh hơn để xóa các chỉ số nhất định: Lamba biểu hiện hoặc cho-loop với nếu kiểm tra bên trong ?

Kết quả đầu tiên là không đáng ngạc nhiên trong thực tế là tôi không biết những gì tôi đã đi để đến với:

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

Nhưng sau đó, tôi quyết định thay đổi liên tục NUMBER_OF_LIST_INDEXES đến một triệu và ở đây là kết quả:

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

để làm cho mọi việc đơn giản hơn để đọc, sau đây là kết quả:

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

Tôi có câu hỏi sau:

• kỳ diệu là gì đằng sau này? Làm thế nào để chúng tôi đến một sự khác biệt lớn cho mảng và không cho lambda khi các chỉ số để làm việc với là * 100.

• Về mặt hiệu suất, làm thế nào để chúng tôi biết khi nào nên sử dụng Lambdas và khi nào phải tuân theo các cách truyền thống để làm việc với dữ liệu?

• Đây có phải là hành vi cụ thể của phương pháp List không? Có phải biểu thức Lambda khác cũng tạo ra những màn trình diễn ngẫu nhiên như thế này không?

Answer 1

Tôi đã viết một điểm chuẩn JMH để đo lường điều này. Có 4 phương pháp trong đó:

• removeIf trên ArrayList.
• removeIf trên LinkedList.
• trình lặp với iterator.remove() trên số ArrayList.
• trình lặp với iterator.remove() trên số LinkedList.

Điểm của điểm chuẩn là chỉ ra rằng removeIf và trình lặp sẽ cung cấp cùng một hiệu suất nhưng không phải là trường hợp cho ArrayList.

Theo mặc định, removeIf sử dụng trình lặp nội bộ để xóa các phần tử, vì vậy chúng tôi sẽ mong đợi cùng một hiệu suất với removeIf và với iterator.

---

Bây giờ hãy xem xét một ArrayList sử dụng mảng nội bộ để giữ các phần tử. Mỗi lần chúng tôi gọi remove, các yếu tố còn lại sau khi chỉ mục phải được dịch chuyển bởi một; vì vậy mỗi lần có rất nhiều phần tử phải được sao chép. Khi một iterator được sử dụng để đi qua các ArrayList và chúng ta cần phải loại bỏ một phần tử, sao chép này cần phải xảy ra một lần nữa và một lần nữa, làm cho điều này rất chậm. Đối với một LinkedList, đây không phải là trường hợp: khi một phần tử bị xóa, thay đổi duy nhất là con trỏ đến phần tử tiếp theo.

Vậy tại sao là removeIf nhanh như trên ArrayList như trên LinkedList? Bởi vì nó thực sự là overriden và nó không sử dụng một iterator: mã thực sự đánh dấu các yếu tố được xóa trong một pass đầu tiên và sau đó xóa chúng (chuyển các phần tử còn lại) trong một pass thứ hai. Tối ưu hóa có thể trong trường hợp này: thay vì chuyển các phần tử còn lại mỗi lần cần xóa, chúng tôi chỉ thực hiện một lần khi chúng tôi biết tất cả các yếu tố cần xóa.

---

Kết luận:

• removeIf nên được sử dụng khi người ta cần phải loại bỏ tất cả các yếu tố phù hợp với một vị ngữ.
• remove nên được sử dụng để xóa một phần tử đã biết.

---

Kết quả benchmark:

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 

Benchmark:

@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 2

Tôi nghĩ sự khác biệt về hiệu suất mà bạn đang xem có thể là do sử dụng một trình lặp nội bộ nhiều hơn so với nhận và loại bỏ trong vòng lặp của bạn. Các câu trả lời trong số PAQ này có một số thông tin tốt về lợi ích của trình lặp.

câu trả lời của bayou.io là tại chỗ, bạn có thể thấy code for removeIf here nó thực hiện hai lần để tránh thay đổi các phần tử còn lại.

Answer 3

Vì remove(index) rất tốn kém :) Cần sao chép và chuyển phần còn lại của các phần tử và việc này được thực hiện nhiều lần trong trường hợp của bạn.

Trong khi removeIf(filter) không cần phải làm điều đó. Nó có thể quét một lần và đánh dấu tất cả các yếu tố cần xóa; sau đó giai đoạn cuối cùng sao chép những người sống sót vào đầu danh sách chỉ một lần.