Tạo một trường bit lớn?

Question

Tôi muốn tạo một trường bit lớn trong JavaScript sẽ đại diện cho mảng đánh dấu đa chiều một cách hiệu quả (sử dụng lập chỉ mục để chuyển đến các thứ nguyên khác nhau trong cấu trúc vật lý "1D").

Thay vì một loạt các số, tôi đang xem xét làm thế nào tôi có thể sử dụng một chuỗi như bit, vì vậy tôi có thể phân bổ một chuỗi có độ dài thích hợp đầu tiên. Các cân nhắc như kiểu dữ liệu, Unicode và các chuyển đổi sẽ được phát (cũng không hỗ trợ Unicode trước JavaScript 1.3).

Tuy nhiên tôi đang mở về các đề xuất khác cách sử dụng JavaScript để đạt được trường bit lớn.

Cập nhật:
Chỉ cần cho mục đích thông tin: Trung bình tôi có thể sử dụng ~ 2187 bit/đánh dấu (274 byte), nhưng muốn có một câu trả lời chung chung hơn có thể chứa nhiều bit hơn.

Answer 1

Một vấn đề với chuỗi là chúng không thay đổi được, vì vậy nếu bạn muốn thay đổi bất kỳ thứ gì, bạn cần phải tạo lại chuỗi.

Tôi chỉ muốn sử dụng các số. Sử dụng các toán tử bitwise, bạn có thể phù hợp với 32 bit trong mỗi số.

Bạn có thể vừa với 53 bit vì số JavaScript là điểm nổi chính xác gấp đôi, nhưng toán tử bitwise chuyển đổi toán hạng sang số nguyên 32 bit, vì vậy bạn sẽ không thể sử dụng chúng để nhận được cá nhân bit (nếu bạn muốn, bạn có thể thực hiện điều tương tự với sự kết hợp của phân chia, Math.pow, v.v. nhưng nó sẽ phức tạp hơn).

Dưới đây là một việc thực hiện cơ bản cho phép bạn nhận được, thiết lập, và bit riêng lẻ unset:

function BitField() { 
    this.values = []; // You could set the length here, but it's not necessary 
} 

BitField.prototype.get = function(i) { 
    var index = (i/32) | 0; // | 0 converts to an int. Math.floor works too. 
    var bit = i % 32; 
    return (this.values[index] & (1 << bit)) !== 0; 
}; 

BitField.prototype.set = function(i) { 
    var index = (i/32) | 0; 
    var bit = i % 32; 
    this.values[index] |= 1 << bit; 
}; 

BitField.prototype.unset = function(i) { 
    var index = (i/32) | 0; 
    var bit = i % 32; 
    this.values[index] &= ~(1 << bit); 
}; 

Answer 2

Trong chrome, tôi nhận được khoảng 10.000 bit.

var bitfield = 0; 
var flag1 = 2 << 1; 
var flag2 = 2 << 2; 
var flagmax = 2 << 10000; 
bitfield |= flagmax 
if (bitfield & flagmax) { 
    doSomething(); 
} 

Answer 3

Trong các trình duyệt gần đây, hiệu quả loại mảng số có sẵn. Không có mảng bit, nhưng bạn có thể sử dụng Uint8Array hoặc Uint32Array và tự đóng gói các bit (theo cách tương tự với câu trả lời của Matthew Crumley; chỉ sử dụng một mảng số thay vì []).

---

câu trả lời Obselete nhưng tương đương (CanvasPixelArray đã được thay thế bởi Uint8ClampedArray):

Nếu trình duyệt bạn đang nhắm mục tiêu hỗ trợ <canvas>, sau đó bạn có thể mượn một đối tượng CanvasPixelArray (canvas.getContext("2d").createImageData(...).data; lưu ý rằng nhu cầu này không được cùng kích thước với canvas) (hy vọng) bộ nhớ lưu trữ dữ liệu hiệu quả (mỗi phần tử là một octet). Và nếu dữ liệu của bạn là 2D, bạn có thể trực quan hóa miễn phí!

Answer 4

Đây là một phần mở rộng để Matthew Crumley's post từ năm 2010:

tôi đã đang Matthêu, thêm tiền phân bổ và so sánh nó với gõ triển khai mảng.

This jsperf cho thấy Chrome là nhanh nhất và an toàn nhất (tôi mong đợi Uint32Array để thực hiện nhanh nhất) và IE chỉ xác định giao diện nhưng không quan tâm đến việc tối ưu hóa mảng được nhập. Các kết quả Firefox bị che khuất bởi vì giao diện điều khiển bị tràn ngập các cảnh báo về cách JSPerf "biên dịch" mã kiểm thử.

("Khác" là (hình như rất riêng tư của tôi) IE 11.)

Uint8Array Thực hiện

function BitField8(nSize) { 
    var nBytes = Math.ceil(nSize/8) | 0; 
    this.values = new Uint8Array(nBytes); 
} 

BitField8.prototype.get = function(i) { 
    var index = (i/8) | 0; 
    var bit = i % 8; 
    return (this.values[index] & (1 << bit)) !== 0; 
}; 

BitField8.prototype.set = function(i) { 
    var index = (i/8) | 0; 
    var bit = i % 8; 
    this.values[index] |= 1 << bit; 
}; 

BitField8.prototype.unset = function(i) { 
    var index = (i/8) | 0; 
    var bit = i % 8; 
    this.values[index] &= ~(1 << bit); 
}; 

Uint32Array Thực hiện

function BitField32(nSize) { 
    var nNumbers = Math.ceil(nSize/32) | 0; 
    this.values = new Uint32Array(nNumbers); 
} 

BitField32.prototype.get = function(i) { 
    var index = (i/32) | 0; 
    var bit = i % 32; 
    return (this.values[index] & (1 << bit)) !== 0; 
}; 

BitField32.prototype.set = function(i) { 
    var index = (i/32) | 0; 
    var bit = i % 32; 
    this.values[index] |= 1 << bit; 
}; 

BitField32.prototype.unset = function(i) { 
    var index = (i/32) | 0; 
    var bit = i % 32; 
    this.values[index] &= ~(1 << bit); 
};