Mảng 10000 có 16bit phần tử, tìm bit thiết lập (RAM không giới hạn) - Google phỏng vấn

Question

Điều này đã được hỏi trong cuộc phỏng vấn Google gần đây và tôi đưa ra câu trả lời liên quan đến bit shift và O (n) nhưng cô ấy nói đây không phải là cách nhanh nhất để thực hiện. Tôi không hiểu, có cách nào để đếm các bit được thiết lập mà không cần phải lặp qua toàn bộ các bit được cung cấp không?

Answer 1

Lực lượng vũ phu: 10000 * 16 * 4 = 640.000 ops. (Shift, so sánh, increment và lặp đi lặp lại cho mỗi từ 16 bit)

cách nhanh hơn:

Chúng tôi có thể xây dựng bảng 00-FF -> số bit được thiết lập. 256 * 8 * 4 = 8096 ops

I.e. chúng tôi xây dựng một bảng cho mỗi byte chúng tôi tính toán một số bit được thiết lập.

Sau đó cho mỗi int 16-bit chúng ta chia nó để trên và dưới

for (n in array) 
    byte lo = n & 0xFF; // lower 8-bits 
    byte hi = n >> 8; // higher 8-bits 
    // simply add number of bits in the upper and lower parts 
    // of each 16-bits number 
    // using the pre-calculated table 
    k += table[lo] + table[hi]; 
} 

60000 ops trong tổng số trong lần lặp. I E. Tổng cộng 68096 ops. Đó là O (n) mặc dù, nhưng với ít liên tục (~ 9 lần ít hơn).

Nói cách khác, chúng tôi tính số bit cho mỗi số 8 bit, sau đó chia mỗi số 16 bit thành hai 8 bit để đếm số bit được đặt bằng bảng được tạo trước.

Answer 2

Có (gần như) luôn luôn là một cách nhanh hơn. Đọc lên khoảng lookup tables.

Answer 3

tôi chỉ thực hiện nó trong Java:

import java.util.Random; 


public class Main { 

static int array_size = 1024; 
static int[] array = new int[array_size]; 
static int[] table = new int[257]; 
static int total_bits_in_the_array = 0; 

private static void create_table(){ 
    int i; 
    int bits_set = 0; 

    for (i = 0 ; i <= 256 ; i++){ 
     bits_set = 0; 
     for (int z = 0; z <= 8 ; z++){ 
      bits_set += i>>z & 0x1; 
     } 
    table[i] = bits_set; 
    //System.out.println("i = " + i + " bits_set = " + bits_set); 
    } 



} 

public static void main(String args[]){ 
     create_table(); 
     fill_array(); 
     parse_array(); 
     System.out.println("The amount of bits in the array is: " + total_bits_in_the_array); 
} 


private static void parse_array() { 
    int current; 

    for (int i = 0; i < array.length; i++){ 
     current = array[i]; 

     int down = current & 0xff; 
     int up = current & 0xff00; 

     int sum = table[up] + table[down]; 

     total_bits_in_the_array += sum; 
    }  
} 

private static void fill_array() { 
    Random ran = new Random(); 

    for (int i = 0; i < array.length; i++){ 
     array[i] = Math.abs(ran.nextInt()%512); 
    } 

} 
} 

Cũng tại https://github.com/leitao/bits-in-a-16-bits-integer-array/blob/master/Main.java

Answer 4

Tôi không biết những gì các câu trả lời đúng là khi câu hỏi này được hỏi, nhưng tôi tin rằng cách hợp lý nhất để giải quyết hôm nay là sử dụng hướng dẫn POPCNT. Cụ thể, bạn nên sử dụng phiên bản 64 bit. Vì chúng ta chỉ muốn tổng số bit thiết lập, ranh giới giữa các phần tử 16-bit không quan tâm đến chúng ta. Vì các hướng dẫn POPCNT 32 bit và 64 bit are equally fast, bạn nên sử dụng phiên bản 64 bit để tính giá trị của bốn phần tử cho mỗi chu kỳ.

Answer 5

Bạn có thể tính toán trước số bit theo byte và sau đó sử dụng tính năng đó để tra cứu. Nó nhanh hơn, nếu bạn đưa ra những giả định nhất định.

Số hoạt động (chỉ cần tính toán, không đọc đầu vào) nên sau

phím Shift cách tiếp cận:

Đối với mỗi byte: 2 ops (shift, thêm) lần 16 bit = 32 ops , 0 mem lần truy cập 10000 = 320 000 ops + 0 mem truy cập

Pre-tính cách tiếp cận:

255 lần 2 ops (shift, add) lần 8 bit = 4080 ops + 255 mem truy cập (ghi kết quả)

Đối với mỗi byte: 2 ops (tính toán địa chỉ) + 2 mem truy cập + op (thêm kết quả) = 30 000 ops + 20 000 truy cập mem

Tổng số 30 480 ops + 20 255 mem truy cập

Vì vậy, rất nhiều truy cập bộ nhớ với các hoạt động ít nhiều

Như vậy, giả sử tất cả mọi thứ khác là như nhau, tính toán trước cho 10 000 byte nhanh hơn nếu chúng ta có thể giả sử truy cập bộ nhớ nhanh hơn hoạt động theo hệ số (320 000 - 30 480)/20 255 = 14.29

Điều này có thể đúng nếu bạn ở một mình trên một lõi chuyên dụng trên một hộp hợp lý hiện đại vì 255 byte phải vừa với bộ đệm. Nếu bạn bắt đầu nhận được bộ nhớ cache bỏ lỡ, giả định có thể không còn giữ.

Ngoài ra, toán học này giả định số học con trỏ và truy cập bộ nhớ trực tiếp cũng như hoạt động nguyên tử và truy cập bộ nhớ nguyên tử. Tùy thuộc vào ngôn ngữ của bạn lựa chọn (và, rõ ràng, dựa trên câu trả lời trước đó, lựa chọn của bạn về chuyển mạch trình biên dịch), giả định đó có thể không giữ.

Cuối cùng, mọi thứ trở nên thú vị hơn nếu bạn xem xét khả năng mở rộng: chuyển dịch có thể dễ dàng song song lên tới 10000 lõi nhưng tính toán trước không nhất thiết. Tuy nhiên, khi số byte tăng lên, tra cứu ngày càng thuận lợi hơn.

Vì vậy, trong ngắn hạn. Có, tính toán trước nhanh hơn theo các giả định khá hợp lý nhưng không, nó không được đảm bảo nhanh hơn.