Tôi có nên đổ java.util.HashSet để ủng hộ CompactHashSet không?

Question

tôi thấy rằng có một thi hành một Set sử dụng băm (với tất cả những hậu quả hữu ích, như O (1) cho vv) mà là tuyên bố được hiệu quả hơn java.util.HashSet trong mọi khía cạnh:

http://ontopia.wordpress.com/2009/09/23/a-faster-and-more-compact-set/

http://alias-i.com/lingpipe/docs/api/com/aliasi/util/CompactHashSet.html

nó sẽ sau đó là một ý tưởng tốt để bỏ sử dụng java.util.HashSet hoàn toàn bất cứ nơi nào tôi cần một java.util.Set ủng hộ com.aliasi.util.CompactHashSet?

Answer 1

Hãy bắt đầu một trò chơi điểm chuẩn nhỏ.

Điểm chuẩn dựa trên điểm chuẩn từ bài viết gốc, nhưng sử dụng các công cụ hiện đại.

package tests; 

import com.carrotsearch.hppc.ObjectOpenHashSet; 
import com.carrotsearch.hppc.cursors.ObjectCursor; 
import com.google.common.collect.GuavaCompactHashSet; 
import net.ontopia.utils.CompactHashSet; 
import net.openhft.koloboke.collect.set.hash.HashObjSet; 
import net.openhft.koloboke.collect.set.hash.HashObjSets; 
import org.openjdk.jmh.annotations.*; 

import java.util.Arrays; 
import java.util.HashSet; 
import java.util.Set; 
import java.util.concurrent.TimeUnit; 
import java.util.function.Consumer; 

import static java.util.Arrays.stream; 
import static org.openjdk.jol.info.GraphLayout.parseInstance; 

@BenchmarkMode(Mode.AverageTime) 
@OutputTimeUnit(TimeUnit.NANOSECONDS) 
@OperationsPerInvocation(TestHashSet.TIMES) 
@Threads(1) 
@Fork(1) 
@State(Scope.Thread) 
public class TestHashSet { 
    public static final int TIMES = 1000000; 
    private static final int MAX = 5000000; 
    private static long ELEMENTS_SIZE; 

    static Long[] add = new Long[TIMES], lookup = new Long[TIMES], remove = new Long[TIMES]; 
    static { 
     for (int ix = 0; ix < TIMES; ix++) 
      add[ix] = new Long(Math.round(Math.random() * MAX)); 
     ELEMENTS_SIZE = stream(add).distinct().count() * parseInstance(add[0]).totalSize(); 
     for (int ix = 0; ix < TIMES; ix++) 
      lookup[ix] = new Long(Math.round(Math.random() * MAX)); 
     for (int ix = 0; ix < TIMES; ix++) 
      remove[ix] = new Long(Math.round(Math.random() * MAX)); 
    } 

    @Benchmark 
    public int hashSet() { 
     Set<Long> set = new HashSet<Long>(); 
     for (Long o : add) { 
      set.add(o); 
     } 
     int r = 0; 
     for (Long o : lookup) { 
      r ^= set.contains(o) ? 1 : 0; 
     } 
     for (Long o : set) { 
      r += o.intValue(); 
     } 
     for (Long o : remove) { 
      set.remove(o); 
     } 
     return r + set.size(); 
    } 

    @Benchmark 
    public int compactHashSet() { 
     Set<Long> set = new CompactHashSet<Long>(); 
     for (Long o : add) { 
      set.add(o); 
     } 
     int r = 0; 
     for (Long o : lookup) { 
      r ^= set.contains(o) ? 1 : 0; 
     } 
     for (Long o : set) { 
      r += o.intValue(); 
     } 
     for (Long o : remove) { 
      set.remove(o); 
     } 
     return r + set.size(); 
    } 

    @Benchmark 
    public int hppcSet() { 
     ObjectOpenHashSet<Long> set = new ObjectOpenHashSet<Long>(); 
     for (Long o : add) { 
      set.add(o); 
     } 
     int r = 0; 
     for (Long o : lookup) { 
      r ^= set.contains(o) ? 1 : 0; 
     } 
     for (ObjectCursor<Long> cur : set) { 
      r += cur.value.intValue(); 
     } 
     for (Long o : remove) { 
      set.remove(o); 
     } 
     return r + set.size(); 
    } 

    @Benchmark 
    public int kolobokeSet() { 
     Set<Long> set = HashObjSets.newMutableSet(); 
     for (Long o : add) { 
      set.add(o); 
     } 
     int r = 0; 
     for (Long o : lookup) { 
      r ^= set.contains(o) ? 1 : 0; 
     } 
     for (Long o : set) { 
      r += o.intValue(); 
     } 
     for (Long o : remove) { 
      set.remove(o); 
     } 
     return r + set.size(); 
    } 

    @Benchmark 
    public int guavaCompactHashSet() { 
     // fair comparison -- growing table 
     Set<Long> set = new GuavaCompactHashSet<>(10); 
     for (Long o : add) { 
      set.add(o); 
     } 
     int r = 0; 
     for (Long o : lookup) { 
      r ^= set.contains(o) ? 1 : 0; 
     } 
     for (Long o : set) { 
      r += o.intValue(); 
     } 
     for (Long o : remove) { 
      set.remove(o); 
     } 
     return r + set.size(); 
    } 

    public static void main(String[] argv) { 
     HashSet hashSet = new HashSet(); 
     test("HashSet", hashSet, hashSet::add); 
     CompactHashSet compactHashSet = new CompactHashSet(); 
     test("CompactHashSet", compactHashSet, compactHashSet::add); 
     HashObjSet<Object> kolobokeSet = HashObjSets.newMutableSet(); 
     test("KolobokeSet", kolobokeSet, kolobokeSet::add); 
     ObjectOpenHashSet hppcSet = new ObjectOpenHashSet(); 
     test("HPPC set", hppcSet, hppcSet::add); 
     GuavaCompactHashSet guavaCompactHashSet = new GuavaCompactHashSet(10); 
     test("GuavaCompactHashSet", guavaCompactHashSet, guavaCompactHashSet::add); 
    } 

    public static void test(String name, Object set, Consumer setAdd) { 
     for (Long o : add) { 
      setAdd.accept(o); 
     } 
     System.out.printf("%s: %.1f bytes per element\n", name, 
       ((parseInstance(set).totalSize() - ELEMENTS_SIZE) * 1.0/TIMES)); 

    } 
} 

Kết quả:

Set implementation Speed   Memory footprint 
        Score Units  +UCOops -UseCompressedOops 
CompactHashSet  828 ns/op  8.4  16.8 bytes/elem 
HashSet    676 ns/op  37.4 60.3 bytes/elem 
HPPC Set    853 ns/op  10.5 18.9 bytes/elem 
Koloboke Set   587 ns/op  8.4  16.8 bytes/elem 
GuavaCompactHashSet 874 ns/op  25.9 37.4 bytes/elem 

Dường rằng CompactHashSet thậm chí còn hơn chậm hơn cũ tốt HashSet, mặc dù nó sử dụng ít dung lượng bộ nhớ.

Answer 2

Điều đó tùy thuộc.

Bạn đang xử lý các Bộ rất lớn và nhiều thao tác chèn hoặc đọc? Điều này thực hiện mới cắt giảm thời gian trong một nửa cho một triệu hoạt động. Đó là một cải tiến tuyệt vời, nhưng nếu bạn chỉ làm một vài nghìn hoạt động hoặc một chục thì điều này nhanh chóng biến thành một tối ưu hóa vi mô.

Các thử nghiệm được hiển thị cũng chèn Long vào bộ này. Hiệu suất cho cả thời gian chạy và sử dụng bộ nhớ có thể thay đổi nếu bạn đang lưu trữ một thứ khác trong tập hợp.

Nếu bạn có trường hợp sử dụng có lợi ích đáng kể từ sự thay đổi theo cách có ý nghĩa thống kê, thì hãy sử dụng nó.

Answer 3

Tùy chọn 1: Đừng quan tâm. Nếu bạn nhìn vào việc thực hiện java HashSet bạn phát hiện ra rằng nó chỉ đơn giản là sử dụng một HashMap nội bộ:

public class HashSet<E> 
    extends AbstractSet<E> 
    implements Set<E>, Cloneable, java.io.Serializable 
{ 
    static final long serialVersionUID = -5024744406713321676L; 

    private transient HashMap<E,Object> map; 
.... 

Đó là một thực hiện nhanh chóng, tuy nhiên, mỗi mục thiết có một tham chiếu đến một giá trị, đó không phải là cần thiết. Do đó tiêu thụ bộ nhớ. Lựa chọn đầu tiên của tôi là "không quan tâm", vì tôi hy vọng rằng đôi khi trong tương lai ai đó sẽ cung cấp một HashSet cải tiến trong JDK. Kỹ sư phần mềm nên luôn luôn có hy vọng và thái độ tích cực :)

Trong logic chương trình bình thường, tôi luôn tuân thủ các tiêu chuẩn được cung cấp càng nhiều càng tốt và sử dụng những gì có sẵn. Điều này tránh được hiệu quả mà mỗi lập trình viên sử dụng "cài đặt Bộ yêu thích" của riêng mình, hoặc thậm chí tệ hơn, thực hiện một nghiên cứu kéo dài thực hiện HashSet thực sự tốt nhất để sử dụng là gì;)

Oracle có vé lỗi mở cho người nghèo Bản đồ băm? Không thể tìm thấy một ...

Tùy chọn 2: Chăm sóc. Nếu bạn không có giá trị logic kinh doanh nhưng trong một số mã phần mềm trung gian kỹ thuật, thì hiệu suất có thể quan trọng. Sau đó, có nhiều tùy chọn khác nhau. Bản đồ CompactHashMap trong Google Guava là một. Một thư viện thú vị khác là High Performance Primitive Collections. Trong HPPC, bạn cũng tìm thấy các bộ cho mọi kiểu nguyên thủy. Tôi nghĩ bạn cũng sẽ tìm thấy những thứ khác phù hợp với mục đích cụ thể của bạn. Không phải mọi thay thế HashMap đều có thể có cùng ngữ nghĩa giống như HashMap gốc.

Vì vậy, cá nhân tôi sẽ không bao giờ thay thế java.util.HashMap chỉ "theo mặc định".