ラムダパフォーマンスの違いは？

Question

Thisは私の質問と重複していません。私はそれをチェックして、内部の匿名のクラスについてもっと詳しく説明します。

• が1万エントリの配列を考えると、何が特定のインデックスを削除するには、より速く、次のようになります：

  は、私は次のラムダ式について興味があったし、テスト内の場合は、テストとラムダ式またはforループ？

最初の結果は、私は私が思い付くするつもりだったのか分からなかったという事実には驚くべきことではありませんでした：

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 

私は、次のような質問があります。この背後にある魔法は何

• を？どのようにインデックスを扱うかがラムダではなく、配列の大きな違いになるのはどうでしょうか？パフォーマンスの面で

• 、どのようにラムダを使用するときに我々は知っていますし、データを操作するための伝統的な方法に固執するとき？

• これはList方法の具体的な行動ですか？他のラムダ式もこのようなランダムな演奏を生み出していますか？

Answer 1

これを測定するためのJMHベンチマークを作成しました。そこには4つの方法があります：

• removeIfArrayListです。
• removeIfオンLinkedList。
• ArrayList上iterator.remove()とイテレータ。
• イテレータiterator.remove()をLinkedListとしています。

ベンチマークの点はremoveIfとイテレータが同じ性能を提供するべきであることを示すことであるが、それはArrayListには当てはまらないこと。

デフォルトでは、removeIfは要素を削除するためにイテレータを使用しているため、removeIfおよびiteratorで同じパフォーマンスが期待されます。

---

ここで、要素を保持するために内部的に配列を使用するArrayListを考えてみましょう。 removeを呼び出すたびに、インデックスの後の残りの要素を1つずらす必要があります。毎回多くの要素をコピーする必要があります。イテレータを使用してArrayListを通過して要素を削除する必要がある場合、このコピーは繰り返し発生する必要があり、非常に遅くなります。 LinkedListの場合、これは当てはまりません。要素が削除された場合、唯一の変更は次の要素へのポインタです。

は、なぜと同じようにArrayListで速いのですか？実際にはオーバーライドされ、イテレータは使用されないため、コードは実際に最初のパスで削除する要素をマークしてから、残りの要素を削除して2番目のパスで削除します。この場合、最適化が可能です。削除する必要があるたびに残りの要素をシフトするのではなく、削除する必要があるすべての要素がわかっているときに一度だけ行います。

---

結論：

• removeIfは、1つの述部に一致するすべての要素を削除する必要があるときに使用されるべきです。
• 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); 
    } 

} 

Answer 2

私はあなたが見ているパフォーマンスの違いは、おそらく内部イテレータのremoveIfの使用によるものよりある対取得し、ループのために削除と思います。このPAQの回答には、イテレータの利点に関するいくつかの良い情報があります。

bayou.ioの答えは、あなたがそれを何度も繰り返し、残りの要素をシフト避けるために2つのパスを行うcode for removeIf hereを見ることができ、その場です。

Answer 3

はremove(index)は非常に高価であるので:)これは、コピーして、残りの要素をシフトする必要があり、これはあなたのケースで複数回行われます。

removeIf(filter)はそれを行う必要はありませんが。これは一度掃引して、削除するすべての要素をマークすることができます。最後の段階で生存者がリストの先頭に1回だけコピーされます。