2

さまざまなサイズの 3 つのハッシュセットの共通部分を見つけようとしています。セットが交差する順序を変更することによって、交差を見つけることができる速度に違いはありますか? プログラムの例は次のようになります。

public class RetainTest {
    static Set<Integer> large =new HashSet<>();
    static Set<Integer> medium =new HashSet<>();
    static Set<Integer> small =new HashSet<>();

    static int largeSize=10000;
    static int midSize=5000;
    static int smallSize=1000;      

    public static void main(String[] args){
        preamble()
        large.retainAll(medium);
        large.retainAll(small);

        System.out.println(large.size());
    }


    public static void preamble(){
        large =new HashSet<>();
        medium =new HashSet<>();
        small =new HashSet<>();

        Random rnd=new Random(15);
        for(int i=0;i<largeSize;i++){
            large.add(rnd.nextInt(largeSize*10));
        }

        for(int i=0;i<midSize;i++){
            medium.add(rnd.nextInt(largeSize*10));
        }
        for(int i=0;i<smallSize;i++){
            small.add(rnd.nextInt(largeSize*10));
        }

    }

}
4

2 に答える 2

3

プロファイリングによると、複数のセットを結合する最も速い方法はretainAll、大きいセットを小さいセットにすることです。さらに、これらの保持の順序も最小から最大にする必要があります。そう

    small.retainAll(medium);
    small.retainAll(large);

プロファイリングは、違いが大きいことを示唆しています。このデータセットでは、最も遅い注文は最も遅い注文の約 10 倍の時間がかかりました。

ここに画像の説明を入力

テストプログラム

これらの結果は、20 分間実行したままにした次のテスト プログラムを使用して作成されます。

public class RetainTest {
    
    static Set<Integer> large =new HashSet<>();
    static Set<Integer> medium =new HashSet<>();
    static Set<Integer> small =new HashSet<>();
    
    static int largeSize=10000;
    static int midSize=5000;
    static int smallSize=1000;      
    
    public static void main(String[] args){
        while(true){
            preamble();
            int size1=largeMediumSmall().size();
            preamble();
            int size2=largeSmallMedium().size();
            preamble();
            int size3=smallMediumLarge().size();
            preamble();
            int size4=smallLargeMedium().size();
            preamble();
            int size5=mediumSmallLarge().size();
            preamble();
            int size6=mediumLargeSmall().size();
            
            //sanity check + ensuring the JIT can't optimise out
            if (size1!=size2 || size1!=size3 || size1!=size4 || size1!=size5 || size1!=size6){
                System.out.println("bad");
            }
        }
        

    }
    
    public static Set<Integer> largeMediumSmall(){
        large.retainAll(medium);
        large.retainAll(small);
        
        return large;
    }
    
    public static Set<Integer> smallMediumLarge(){
        small.retainAll(medium);
        small.retainAll(large);
        
        return small;
    }
    public static Set<Integer> smallLargeMedium(){
        small.retainAll(large);
        small.retainAll(medium);
        
        return small;
    }
    public static Set<Integer> mediumSmallLarge(){
        medium.retainAll(small);
        medium.retainAll(large);
        
        return medium;
    }
    public static Set<Integer> mediumLargeSmall(){
        medium.retainAll(large);
        medium.retainAll(small);
        
        return medium;
    }
    public static Set<Integer> largeSmallMedium(){
        large.retainAll(small);
        large.retainAll(medium);
        
        return large;
    }
    
    
    public static void preamble(){
        large =new HashSet<>();
        medium =new HashSet<>();
        small =new HashSet<>();
        
        Random rnd=new Random(15);
        for(int i=0;i<largeSize;i++){
            large.add(rnd.nextInt(largeSize*10));
        }
        
        for(int i=0;i<midSize;i++){
            medium.add(rnd.nextInt(largeSize*10));
        }
        for(int i=0;i<smallSize;i++){
            small.add(rnd.nextInt(largeSize*10));
        }
        
    }
    
}
于 2014-01-29T12:34:15.397 に答える