boolean [] và BitSet: Cái nào hiệu quả hơn?

Question

Điều gì là hiệu quả hơn về mặt bộ nhớ và sử dụng CPU - một mảng của boolean s hoặc một BitSet? Các phương thức BitSet cụ thể không được sử dụng, chỉ nhận/set/clear (==, =, Arrays.fill tương ứng cho một mảng).

Answer 1

Từ một số tiêu chuẩn với Sun JDK số nguyên tố 1,6 máy tính với một cái rây (tốt nhất là 10 lần lặp để làm ấm lên, cung cấp cho các trình biên dịch JIT một cơ hội, và loại trừ sự chậm trễ lịch trình ngẫu nhiên, Core 2 Duo T5600 1.83GHz):

BitSet là bộ nhớ hiệu quả hơn boolean [] ngoại trừ kích thước rất nhỏ. Mỗi boolean trong mảng lấy một byte. Các số từ runtime.freeMemory() là một bit bị rối cho BitSet, nhưng ít hơn.

boolean [] có hiệu suất CPU cao hơn ngoại trừ các kích thước rất lớn, thậm chí chúng ở đâu. Ví dụ: đối với kích thước 1 triệu boolean [] nhanh gấp bốn lần (ví dụ: 6ms so với 27 mili giây), đối với mười và một trăm triệu, thậm chí là khoảng một triệu.

Answer 2

Tôi tin rằng BitSet có nhiều bộ nhớ hơn và hiệu quả CPU, nó có thể đóng gói các bit thành int, longs hoặc kiểu dữ liệu gốc, trong khi boolean [] yêu cầu byte cho mỗi bit dữ liệu. Ngoài ra, nếu bạn đã sử dụng các phương thức khác (và, hoặc, vv), bạn sẽ thấy rằng BitSet là hiệu quả hơn, vì không cần phải lặp qua mọi phần tử của một mảng; toán bitwise được sử dụng thay thế.

Answer 3

Đi từ Java sang CPU hoàn toàn là VM cụ thể. Ví dụ, nó từng là một boolean đã thực sự được thực hiện như một giá trị 32-bit (có lẽ hoàn toàn đúng với ngày này).

Trừ khi bạn biết điều quan trọng là bạn nên viết mã để rõ ràng, lược tả, sau đó sửa các phần chậm hoặc tiêu tốn nhiều bộ nhớ.

Bạn có thể thực hiện việc này khi di chuyển. Ví dụ tôi đã từng quyết định không gọi .intern() trên Strings bởi vì khi tôi chạy mã trong profiler nó làm chậm nó xuống quá nhiều (mặc dù sử dụng ít bộ nhớ hơn).

Answer 4

Nó phụ thuộc như mọi khi. Có BitSet có hiệu quả bộ nhớ cao hơn, nhưng ngay sau khi bạn yêu cầu truy cập đa luồng boolean [] có thể là lựa chọn tốt hơn. Ví dụ: đối với các số nguyên máy tính, bạn chỉ đặt boolean thành true và do đó bạn không thực sự cần đồng bộ hóa. Hans Boehm đã viết một số bài báo về điều này và kỹ thuật tương tự có thể được sử dụng để đánh dấu các nút trong biểu đồ.

Answer 5

• Boolean[] sử dụng khoảng 4-20 byte cho mỗi giá trị boolean.
• boolean[] sử dụng khoảng 1 byte cho mỗi giá trị boolean.
• BitSet sử dụng khoảng 1 bit cho mỗi giá trị boolean.

Kích thước bộ nhớ có thể không phải là vấn đề cho bạn trong trường hợp boolean [] có thể đơn giản hơn để mã.

Answer 6

Một trường còn lại trong câu hỏi của bạn, nhưng nếu lưu trữ là mối quan ngại bạn có thể muốn xem xét Huffman compression. Ví dụ: 00000001 có thể được nén xuống theo tần suất thành một thứ tương đương với {(7)0, (1)1}. Một chuỗi "ngẫu nhiên" hơn 00111010 sẽ yêu cầu một biểu diễn phức tạp hơn, ví dụ: {(2)0, (3)1, (1)0, (1)1, (1)0} và chiếm nhiều không gian hơn. Tùy thuộc vào cấu trúc dữ liệu bit của bạn, bạn có thể nhận được một số lợi ích bộ nhớ từ việc sử dụng nó, ngoài BitSet.

Answer 7

Đối với bộ nhớ, tài liệu dành cho BitSet có ý nghĩa khá rõ ràng.Cụ thể:

Mỗi bit có kích thước hiện tại, là số bit của không gian hiện đang được sử dụng bởi bộ bit. Lưu ý rằng kích thước có liên quan đến việc thực hiện một bộ bit, do đó, nó có thể thay đổi khi triển khai. Chiều dài của bộ bit liên quan đến độ dài hợp lý của một bộ bit và là được xác định độc lập với việc triển khai.

Nguồn cho các lớp thư viện Java hiện có sẵn và có thể dễ dàng check this for themselves. Cụ thể:

The internal field corresponding to the serialField "bits". 
89 
90  private long[] words; 

Còn về tốc độ; nó phụ thuộc vào những gì người ta đang làm. Nói chung, đừng nghĩ về tốc độ trước thời hạn; sử dụng công cụ nào có ý nghĩa nhất về mặt ngữ nghĩa và dẫn đến mã rõ ràng nhất. Chỉ tối ưu hóa sau khi quan sát thấy rằng các yêu cầu về hiệu suất không được đáp ứng và xác định các tắc nghẽn.

Đến với SO và yêu cầu nếu A là nhanh hơn so với B là ngớ ngẩn vì nhiều lý do, bao gồm nhưng chắc chắn không giới hạn:

1. Nó phụ thuộc vào các ứng dụng, mà không ai đáp ứng thường có quyền truy cập vào. Phân tích và cấu hình nó trong ngữ cảnh mà nó đang được sử dụng. Hãy chắc chắn rằng đó là một nút cổ chai thực sự đáng được tối ưu hóa.
2. Các câu hỏi như thế này yêu cầu về tốc độ thường cho thấy OP cho rằng họ quan tâm đến hiệu quả nhưng không sẵn sàng cho tiểu sử và không xác định yêu cầu hiệu suất. Dưới bề mặt, đó thường là một lá cờ đỏ mà OP đang đi xuống con đường sai.

Tôi biết đây là câu hỏi cũ nhưng đã xuất hiện gần đây; và tôi tin rằng điều này đáng để thêm vào.