Javaプログラマーズチートシート7.2典型的なタスク：マップのバイパス、部分文字列の出現回数のカウント

私は趣味があります：私はインターネットで見つけたJavaの典型的なタスクに対するさまざまなソリューションを収集し、サイズ/パフォーマンス/エレガンスで最も最適なものを選択しようとします。 まず第一に、パフォーマンスの面で。 Javaプログラミングでよく見られる「Mapのバイパス」や、行の出現回数、さまざまなソリューション（「美しい」など）とそのパフォーマンスのカウントなど、一般的なタスクを見てみましょう。

英語版はStackoverflowにあります： マップをバイパスし 、部分文字列の出現をカウント します 。

また、おそらく最も有用なJavaライブラリとフレームワークの包括的なコレクションである、私のオープンソースの役立つjava-linksプロジェクトをご覧になることをお勧めします。

1.マップバイパス

したがって、インターネットで検索する場合、キーと値が重要である一般的な場合にマップツアーを実行するさまざまな方法があります（もちろん、キーまたは値だけをバイパスすることは基本的に行われます）。 それらのいくつかは構文糖でのみ異なり、いくつかは根本的に異なります。 実際、もちろん、どのソリューションが遅いか、どのソリューションが速いかは長い間知られていますが、それでもオウムでどれだけ得られるのかと思います。

完全を期すために、通常のMapのバイパスだけでなく、 Apache Collections



IterableMapとEclipse (CS) collections



MutableMapの類似物も検討してみましょう。

オプションを見てみましょう：

問題の条件は、数値のマップがあります。このマップのすべてのキーとすべての値の合計を探します。 このようなタスクは、一方では単純化され、他方では、Javaオプティマイザーがコードの一部を破棄できないことを保証します。

1. iterator 、 Map.Entryおよびwhileループを使用します。 最も美しいオプションではなく、実際にはオプション（2）の類似物ですが、それらの違いを見てみましょう。

   
   
   
   
   
   
   

    long i = 0; Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); while (it.hasNext()) { Map.Entry<Integer, Integer> pair = it.next(); i += pair.getKey() + pair.getValue(); }
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   

2. Map.Entryとforeachループを使用します 。 マップバイパスのクラシックバージョン。

   
   
   
   
   
   
   

    long i = 0; for (Map.Entry<Integer, Integer> pair : map.entrySet()) { i += pair.getKey() + pair.getValue(); }
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   

3. Java 8
   
   
   
   からforeachを使用しJava 8
   
   
   
   。 Java 8で登場した新しいメソッドの生産性を見てみましょう。

   
   
   
   
   
   
   

    final long[] i = {0}; map.forEach((k, v) -> i[0] += k + v);
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   

4. keySetとforeachを使用します。 この方法は非常に遅いと考えられており、問題はどれくらいかです。

   
   
   
   
   
   
   

    long i = 0; for (Integer key : map.keySet()) { i += key + map.get(key); }
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   

5. keySetとiteratorを使用します 。 実際、オプション4には構文糖衣のみがあります。

   
   
   
   
   
   
   

    long i = 0; Iterator<Integer> itr2 = map.keySet().iterator(); while (itr2.hasNext()) { Integer key = itr2.next(); i += key + map.get(key); }
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   

6. forおよびMap.Entryを使用し ます 。 「古いスタイル」のみのアナログ1および2

   
   
   
   
   
   
   

    long i = 0; for (Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator(); entries.hasNext(); ) { Map.Entry<Integer, Integer> entry = entries.next(); i += entry.getKey() + entry.getValue(); }
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   

7. Java 8
   
   
   
   とStream Apiの使用

   
   
   
   
   
   
   

    final long[] i = {0}; map.entrySet().stream().forEach(e -> i[0] += e.getKey() + e.getValue()); //   
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   

   7a。 mapToLongとsumでJava 8
   
   
   
   とStream Apiを使用する

   
   
   
   
   
   
   

   map.entrySet（）。stream（）。mapToLong（e-> e.getKey（）+ e.getValue（））。sum（）;

   
   
   
   
   
   
   

8. Java 8
   
   
   
   とParallel Stream Apiの使用

   
   
   
   
   
   
   

     final long[] i = {0}; map.entrySet().stream().parallel().forEach(e -> i[0] += e.getKey() + e.getValue()); //   ,      ,     ,   8
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   

   8a。 mapToLongおよびsumでJava 8
   
   
   
   およびパラレルストリーム APIを使用する

   
   
   
   
   
   
   

     map.entrySet().parallelStream().mapToLong(e -> e.getKey() + e.getValue()).sum();
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   

9. Apache Collections
   
   
   
   IterableMapを使用しApache Collections
   
   
   
   。 このマップは、通常とは異なる方法で移動します。

   
   
   
   
   
   
   

    long i = 0; MapIterator<Integer, Integer> it = iterableMap.mapIterator(); while (it.hasNext()) { i += it.next() + it.getValue(); }
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

   
   
   

10. Eclipse collections
    
    
    
    （以前のGSコレクション）からMutableMapを使用します。 このマップは、Java 8が登場するよりもはるかに早くforEachメソッドを取得しました。

    
    
    
    
    
    
    

     final long[] i = {0}; mutableMap.forEachKeyValue((key, value) -> { i[0] += key + value; });
          
          
    
            
            
            
          
    
        
            
            
            
          
          
    
            
            
            
          
    
        
         

    
    
    

性能試験

典型的な警告 ：すべての結果はそのままで、パフォーマンス測定は複雑なものです。システムではすべての数値が完全に異なる場合があるため、 github'eのソースコードを信じてはいけません。常に自分で結果を取得できます。 パフォーマンスを測定するときに私がどこかで間違えたと思うなら（そしてこれは常に可能です）、個人的なメッセージやコメントを書いていただければありがたいです。

モード=平均時間（AverageTime）、システム= Win 8.1 64ビット、Intel i7-4790 3.60GHz 3.60GHz、16 GB、スコアが低いほど良い）

1）小さなマップ（100要素）の場合、スコア0.312が最良の値です。

  Benchmark Size Mode Cnt Score Error Units 3. ForEachAndJava8 100 avgt 100 0.312 ± 0.003 us/op 10. EclipseMap 100 avgt 100 0.354 ± 0.003 us/op 2. ForEachAndMapEntry 100 avgt 100 0.403 ± 0.005 us/op 1. WhileAndMapEntry 100 avgt 100 0.427 ± 0.006 us/op 6. ForAndIterator 100 avgt 100 0.427 ± 0.006 us/op 7a Java8StreamApi2 100 avgt 100 0.509 ± 0.036 us/op 7. Java8StreamApi 100 avgt 100 0.529 ± 0.004 us/op 9. ApacheIterableMap 100 avgt 100 0.585 ± 0.008 us/op 4. KeySetAndForEach 100 avgt 100 0.937 ± 0.011 us/op 5. KeySetAndIterator 100 avgt 100 0.94 ± 0.011 us/op 8. Java8StreamApiParallel 100 avgt 100 6.066 ± 0.051 us/op 8a. Java8StreamApiparallel2 100 avgt 5 9.468 ± 0.333 us/op
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

2）10,000個の要素を持つ中規模マップの場合、スコア35.301が最適な値です

  Benchmark Size Mode Cnt Score Error Units 10. EclipseMap 10000 avgt 100 35.301 ± 0.697 us/op 3. ForEachAndJava8 10000 avgt 100 39.797 ± 0.309 us/op 2. ForEachAndMapEntry 10000 avgt 100 43.149 ± 0.313 us/op 1. WhileAndMapEntry 10000 avgt 100 43.295 ± 0.314 us/op 6. ForAndIterator 10000 avgt 100 44.009 ± 0.379 us/op 7. Java8StreamApi 10000 avgt 100 49.378 ± 0.415 us/op 5. KeySetAndIterator 10000 avgt 100 97.844 ± 0.896 us/op 4. KeySetAndForEach 10000 avgt 100 99.317 ± 0.862 us/op 8. Java8StreamApiParallel 10000 avgt 100 112.364 ± 0.167 us/op 9. ApacheIterableMap 10000 avgt 100 138.379 ± 1.387 us/op
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

3）30,000個の要素を持つマップの場合、スコア122.277が最適な値です。

  Benchmark Size Mode Cnt Score Error Units 8a. Java8StreamApiparallel2 30000 avgt 100 95.444 ± 13.706 us/op 10. EclipseMap 30000 avgt 100 122.277 ± 3.896 us/op 3. ForEachAndJava8 30000 avgt 100 136.906 ± 2.392 us/op 2. ForEachAndMapEntry 30000 avgt 100 145.845 ± 1.895 us/op 1. WhileAndMapEntry 30000 avgt 100 149.186 ± 2.621 us/op 6. ForAndIterator 30000 avgt 100 149.353 ± 2.427 us/op 7a. Java8StreamApi2 30000 avgt 100 180.803 ± 53.062 us/op 7. Java8StreamApi 30000 avgt 100 181.114 ± 3.272 us/op 8. Java8StreamApiParallel 30000 avgt 100 342.546 ± 1.206 us/op 5. KeySetAndIterator 30000 avgt 100 350.564 ± 8.662 us/op 4. KeySetAndForEach 30000 avgt 100 364.362 ± 9.416 us/op 9. ApacheIterableMap 30000 avgt 100 536.749 ± 25.819 us/op
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ケース8a（mapToIntとsumを使用した並列ストリーム）が数値データを処理するために正確な結果を示していることに注意してください;実際の問題では、常に適用できるとは限りません。

グラフ（マップのサイズに応じたテスト）

テーブル（マップサイズに応じたテスト）

  Benchmark 100 500 900 1300 1700 2100 2500 10. EclipseMap 0.354 1.384 3.816 3.304 6.68 7.427 8.712 3. ForEachAndJava8 0.312 1.692 3.143 4.265 6.506 8.343 9.821 6. ForAndIterator 0.427 2.089 3.746 4.776 7.407 9.091 10.753 2. ForEachAndMapEntry 0.403 2.536 3.951 5.028 7.503 9.211 10.918 1. WhileAndMapEntry 0.427 2.026 3.4815 4.937 7.511 9.217 12.22 7. Java8StreamApi 0.529 2.343 4.264 5.399 8.826 12.633 12.918 9. ApacheIterableMap 0.585 2.725 5.574 9.292 13.01 17.719 23.882 5. KeySetAndIterator 0.94 4.592 8.24 12.496 16.077 21.012 24.389 4. KeySetAndForEach 0.937 4.572 8.251 12.522 14.831 20.502 24.881 8. Java8StreamApiParallel 6.066 12.152 16.563 18.512 25.987 28.813 33.336
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

GitHubでのすべてのテスト

警告 ：HashMap、EclipseMap、ApacheIterableMapのバイパスは、衝突がほとんどない典型的な場合にのみ考慮され、衝突が多い場合、結果は完全に異なる可能性があります。 また、要素の追加、ランダムアクセスなどのケースは考慮されていません。つまり、このテストだけでは、どのマップが一般に高速で優れているかを判断することはできません。

2.文字列内の部分文字列の出現回数を数える

したがって、次のサブストリングを取得し、その中のすべてのポイントを見つけます。

  String testString = "abcd";
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

私はすぐに警告したかった：テストのためにStackOverflowトピックで提案されたすべてのオプションを採用しました、常識はそれらのいくつかが私のお気に入りの顕微鏡での最適な釘付けからは程遠いことを示唆しますが、私はそれぞれの場合に何が起こるか興味がありました。 したがって、 以下のオプションのすべてが実際のアプリケーションで使用されるべきではないことに注意してください ！

1） Apache Commonsを使用する

 int apache = StringUtils.countMatches(testString, "."); System.out.println("apache = " + apache);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

2） Spring Frameworkの使用

 int spring = org.springframework.util.StringUtils.countOccurrencesOf(testString, "."); System.out.println("spring = " + spring);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

3） 置換の使用

 int replace = testString.length() - testString.replace(".", "").length(); System.out.println("replace = " + replace);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

4） replaceAllの使用（ケース1）

 int replaceAll = testString.replaceAll("[^.]", "").length(); System.out.println("replaceAll = " + replaceAll);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

5） replaceAllの使用（ケース2）

 int replaceAllCase2 = testString.length() - testString.replaceAll("\\.", "").length(); System.out.println("replaceAll (second case) = " + replaceAllCase2);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

6） スプリットを使用する

 int split = testString.split("\\.",-1).length-1; System.out.println("split = " + split);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

7） Java8の使用（ケース1）。 他のオプションとは異なり、部分文字列ではなく文字のみを検索できることに注意してください 。

 long java8 = testString.chars().filter(ch -> ch =='.').count(); System.out.println("java8 = " + java8);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

8） Java8を使用する （ケース2）。おそらく、ユニコード文字列の場合、ケース1よりも少し良いでしょう。他のオプションとは異なり、部分文字列ではなく文字のみを検索できることに注意してください 。

 long java8Case2 = testString.codePoints().filter(ch -> ch =='.').count(); System.out.println("java8 (second case) = " + java8Case2);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

9） StringTokenizerの使用

 int stringTokenizer = new StringTokenizer(" " +testString + " ", ".").countTokens()-1; System.out.println("stringTokenizer = " + stringTokenizer);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

後者のオプションは、2つのポイントが1つと見なされるため、a ... bc ... dまたは... abcdまたはa .... b ...... c ... ..d ...いくつかのポイントは1つと見なされます。

典型的な警告 ：すべての結果はそのままで、パフォーマンス測定は複雑なものです。システムではすべての数値が完全に異なる場合があるため、 github'eのソースコードを信じてはいけません。常に自分で結果を取得できます。 パフォーマンスを測定するときに私がどこかで間違えたと思うなら（そしてこれは常に可能です）、個人的なメッセージやコメントを書いていただければありがたいです。

GitHubでのすべてのテスト

短い行での測定 （ JMHを使用、モード= AverageTime、 0.010



0.351



よりも良い）：

 Benchmark Mode Cnt Score Error Units 1. countMatches avgt 5 0.010 ± 0.001 us/op 2. countOccurrencesOf avgt 5 0.010 ± 0.001 us/op 3. stringTokenizer avgt 5 0.028 ± 0.002 us/op 4. java8_1 avgt 5 0.077 ± 0.005 us/op 5. java8_2 avgt 5 0.078 ± 0.003 us/op 6. split avgt 5 0.137 ± 0.009 us/op 7. replaceAll_2 avgt 5 0.302 ± 0.047 us/op 8. replace avgt 5 0.303 ± 0.034 us/op 9. replaceAll_1 avgt 5 0.351 ± 0.045 us/op
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

2142文字の長さの長い行での測定結果 （ JMHを使用、mode = AverageTime、 0.010



値は0.351



よりも優れています）：

 Benchmark Mode Cnt Score Error Units 1. countMatches avgt 5 2.392 ± 0.172 us/op 2. countOccurrencesOf avgt 5 2.362 ± 0.060 us/op 3. stringTokenizer avgt 5 5.931 ± 0.112 us/op 4. java8 avgt 5 9.626 ± 0.463 us/op 5. java8_1 avgt 5 8.586 ± 0.251 us/op 6. split avgt 5 21.201 ± 1.037 us/op 7. replaceAll2 avgt 5 26.614 ± 1.026 us/op 8. replaceAll1 avgt 5 31.505 ± 1.046 us/op 9. replace avgt 5 33.462 ± 2.329 us/op
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

PS英語版はStackoverflowで見つけることができます： マップをバイパスし 、サブストリングの出現をカウントし ます 。私のプロジェクトのソースコードは、 useful-java-linksです。 もしあなたがこの記事を気に入ってくれて、それにふさわしいと思ったら、SOまたはgithub'eのプラスに感謝します。

PPSまた、私のオープンソースの「 useful-java-links」プロジェクト（おそらく最も有用なJavaライブラリ、フレームワーク、ロシア語の教育ビデオのコレクション）をご覧になることをお勧めします。 このプロジェクトには同様の英語版もあり、1つのMavenプロジェクトでさまざまなJavaライブラリの簡単なサンプルのコレクションを準備するために、オープンソースのHello worldサブプロジェクトを開始しています（ご協力に感謝します）。