Không gian Python + thời gian hiệu quả Cấu trúc dữ liệu để lưu trữ mảng bit 2D

Question

Tôi muốn tạo một mảng nhị phân 2D (bit) trong Python theo cách không gian và thời gian hiệu quả như bitmap 2D của tôi sẽ là khoảng 1 triệu (hàng) * 50000 (các cột 0 hoặc 1) và tôi cũng sẽ thực hiện các hoạt động bitwise trên các phần tử khổng lồ này. mảng của tôi sẽ giống như thế:

0 1 0 1 
1 1 1 0 
1 0 0 0 
... 

Trong C++ cách hiệu quả nhất (không gian) đối với tôi sẽ là để tạo ra một loại mảng các số nguyên trong đó mỗi yếu tố đại diện cho 32 bit và sau đó tôi có thể sử dụng các toán tử chuyển đổi kết hợp với các nhà khai thác bit-khôn ngoan để thực hiện các hoạt động.

Bây giờ tôi biết rằng có một mô-đun bitarray trong python. Nhưng tôi không thể tạo ra một cấu trúc 2D bằng cách sử dụng danh sách các mảng bit. Tôi có thể làm cái này như thế nào?

Một cách khác tôi biết trong C++ là tạo bản đồ giống như map<id, vector<int> > nơi tôi có thể thao tác vectơ như tôi đã đề cập ở trên. Tôi có nên sử dụng từ điển tương đương trong python? Thậm chí nếu bạn đề xuất cho tôi một số cách để sử dụng mảng bit cho nhiệm vụ này nó sẽ là tuyệt vời Nếu tôi có thể biết liệu tôi có thể có nhiều chủ đề hoạt động trên một mối nối của bitarray để tôi có thể làm cho nó đa luồng. Cảm ơn đã giúp đỡ!!

CHỈNH SỬA:

Tôi thậm chí có thể tạo cấu trúc dữ liệu riêng cho điều này nếu cần thiết. Tuy nhiên chỉ muốn kiểm tra trước khi phát minh lại bánh xe.

Answer 1

Theo nhận xét của tôi, bạn có thể sử dụng bộ

0 1 0 1 
1 1 1 0 
1 0 0 0 

có thể được biểu diễn dưới dạng

set([(1,0), (3,0), (0,1), (1,1), (2, 1), (0,2)]) 

hoặc

{(1,0), (3,0), (0,1), (1,1), (2, 1), (0,2)} 

AND là tương đương với một giao điểm của 2 bộ
HOẶC là liên minh của 2 bộ

Answer 2

Làm thế nào về những điều sau đây:

In [11]: from bitarray import bitarray 

In [12]: arr = [bitarray(50) for i in xrange(10)] 

này tạo ra một mảng 10x50cm chút, mà bạn có thể truy cập như sau:

In [15]: arr[0][1] = True 

In [16]: arr[0][1] 
Out[16]: True 

Gấu nhớ rằng một mảng 1Mx50K sẽ cần khoảng 6GB bộ nhớ (và xây dựng một bản Python 64 bit trên hệ điều hành 64 bit).

liệu tôi có thể có nhiều chủ đề hoạt động trên một mối nối của bitarray để tôi có thể làm cho nó đa luồng

Đó không phải là một vấn đề, hãy cẩn thận với bình thường. Xin lưu ý rằng do số GIL, bạn không thể đạt được các cải thiện hiệu suất thông qua đa luồng.

Answer 3

Bạn có thể sử dụng gọn gàng không?

>>> import numpy 
>>> A = numpy.zeros((50000, 1000000), dtype=bool) 

CHỈNH SỬA: Dường như không phải là không gian hiệu quả nhất. Sử dụng 50GB (1 byte cho mỗi bool). Có ai biết nếu numpy có một cách để sử dụng bool đóng gói?