オブジェクトの大きなリストを繰り返しループするときのパフォーマンスを最適化する方法

Question

私は、1行に2つの整数値（ソース整数とターゲット整数）を含む単純なファイルを持っています。各行は2つの値の間の関係を表します。ファイルはソートされておらず、実際のファイルには約400万行が含まれています。並べ替え後は、次のようになります。

sourceId;targetId 
1;5  
2;3 
4;7 
7;4 
8;7 
9;5 

私の目標は、一意の識別子と、リスト内のすべての独特の関連整数を表します新しいオブジェクトを作成することです。この例の期待される出力は、次の3つのオブジェクトであるべきである。

0, [1, 5, 9] 
1, [2, 3] 
2, [4, 7, 8] 

だからのgroupId 0は、関係の群（1,5および9）を含みます。

以下は、これらのオブジェクトのリストを作成する現在の方法です。 Relationオブジェクトのリストには、メモリ内のすべての行が含まれます。 GroupedRelationのリストは最終結果でなければなりません。

この小さなサンプルプログラムを実行すると、1000 GroupedRelationオブジェクトの作成に15秒かかります。 100万GroupedRelationを作成するには250分かかります。

私は自分のコードを最適化するための助けを求めていますが、私は望む結果を得るには時間がかかります。

期待される結果が同じであるが期待される結果を得るのにかかる時間が大幅に短縮されるように反復を最適化することは可能ですか？これが可能であれば、どうやってそれについてやりますか？

Answer 1

の宣言。

import java.io.*; 
import java.util.*; 

/** 
* Created by peter on 10/07/16. 
*/ 
public class GroupedRelationBuilder { 

    public static List<List<Integer>> load(File file) throws IOException { 
     Map<Integer, Group> idToGroupMap = new HashMap<>(); 
     try (BufferedReader br = new BufferedReader(new FileReader(file))) { 
      br.readLine(); 
      for (String line; (line = br.readLine()) != null;) { 
       String[] parts = line.split(";"); 
       Integer source = Integer.parseInt(parts[0]); 
       Integer target = Integer.parseInt(parts[1]); 
       Group grp0 = idToGroupMap.get(source); 
       Group grp1 = idToGroupMap.get(target); 
       if (grp0 == null) { 
        if (grp1 == null) { 
         Group grp = new Group(); 
         List<Integer> list = grp.ids; 
         list.add(source); 
         list.add(target); 
         idToGroupMap.put(source, grp); 
         idToGroupMap.put(target, grp); 
        } else { 
         grp1.ids.add(source); 
         idToGroupMap.put(source, grp1); 
        } 
       } else if (grp1 == null) { 
        grp0.ids.add(target); 
        idToGroupMap.put(target, grp0); 
       } else { 
        grp0.ids.addAll(grp1.ids); 
        grp1.ids = grp0.ids; 
       } 
      } 
     } 
     Set<List<Integer>> idsSet = Collections.newSetFromMap(new IdentityHashMap<>()); 
     for (Group group : idToGroupMap.values()) { 
      idsSet.add(group.ids); 
     } 
     return new ArrayList<>(idsSet); 
    } 

    static class Group { 
     List<Integer> ids = new ArrayList<>(); 
    } 

    public static void main(String[] args) throws IOException { 
     File file = File.createTempFile("deleteme", "txt"); 
     Set<String> pairs = new HashSet<>(); 
     try (PrintWriter pw = new PrintWriter(file)) { 
      pw.println("source;target"); 
      Random rand = new Random(); 
      int count = 1000000; 
      while (pairs.size() < count) { 
       int a = rand.nextInt(count); 
       int b = rand.nextInt(count); 
       if (a < b) { 
        int t = a; 
        a = b; 
        b = t; 
       } 
       pairs.add(a + ";" + b); 
      } 
      for (String pair : pairs) { 
       pw.println(pair); 
      } 
     } 
     System.out.println("Processing"); 
     long start = System.currentTimeMillis(); 
     List<List<Integer>> results = GroupedRelationBuilder.load(file); 
     System.out.println(results.size() + " took " + (System.currentTimeMillis() - start)/1e3 + " sec"); 
    } 
} 

百万ペアの場合、これは

Processing 
105612 took 12.719 sec 

Answer 2

現在の実装は、ids.containsステップのために低速です。 ArrayList.containsメソッドの時間複雑さは、要素が1つずつチェックされているかどうかをチェックするためにO(n)： であり、最悪の場合はリスト全体をスキャンします。

idsのタイプをList<String>からSet<String>に変更し、HashSet<String>インスタンスを使用すると、パフォーマンスが大幅に向上します。 Set.containsの実装の予想される時間の複雑さは、リストと比較してかなり速いO(1), です。

Answer 3

Integer.toString()の使用により実装が遅くなります。 タイプを変更すると、オブジェクトとメモリの割り当てを意味します。これは現在、サブループ内で4〜5回実行されます。

変更すると、126msから35msに短縮されました：4倍速くなりました！私が見

いくつかの他のものは以下のとおりです。

• ループのための第一、第二のループはイテレータfor (Iterator<Relation> iterator = relations.iterator(); iterator.hasNext();)を使用することによって行うことができるwhile(!relations.isEmpty())
• に変更することができます。アイテムを削除すると、次のアイテムをスキップします。
• プレイスIソースから単一パスでそれをしようと可能な限りループ内ids