Массив из 10000 с 16-битными элементами, набор бит (неограниченное ОЗУ) - интервью Google

Ответ 1

Грубая сила: 10000 * 16 * 4 = 640 000 операций. (сдвиг, сравнение, приращение и итерация для каждого 16-битного слова)

Более быстрый способ:

Мы можем построить таблицу 00-FF → количество бит. 256 * 8 * 4 = 8096 ops

т.е. мы создаем таблицу, в которой для каждого байта вычисляется количество бит.

Затем для каждого 16-битного int мы разбиваем его на верхний и нижний

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 операций в общей сложности на итерации. То есть Всего 68096 операционных. Это O (n), хотя и с меньшей константой (~ 9 раз меньше).

Другими словами, мы вычисляем количество бит для каждого 8-битного числа, а затем разбиваем каждое 16-разрядное число на два 8-битовых, чтобы подсчитывать биты, заданные с использованием предварительно построенной таблицы.

Ответ 2

Там (почти) всегда более быстрый способ. Прочитайте таблицы поиска.

Ответ 3

Я не знаю, какой был правильный ответ, когда был задан этот вопрос, но я считаю, что самым разумным способом решить эту проблему сегодня является использование инструкции POPCNT. В частности, вы должны использовать 64-разрядную версию. Поскольку нам просто нужно общее количество заданных битов, границы между 16-битными элементами нам не интересны. Поскольку 32-разрядные и 64-разрядные команды POPCNT одинаково быстрые, вы должны использовать 64-разрядную версию для подсчета стоимости четырех элементов бит за цикл.

Ответ 4

Я только что реализовал его в 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);
    }

}
}

Также на https://github.com/leitao/bits-in-a-16-bits-integer-array/blob/master/Main.java

Ответ 5

Вы можете предварительно вычислить количество бит в байтах, а затем использовать это для поиска. Это быстрее, если вы сделаете определенные предположения.

Количество операций (только вычисление, а не чтение ввода) должно принимать следующие

Сдвиг-подход:

Для каждого байта:  2 ops (shift, add) times 16 bits = 32 ops, 0 времен доступа к памяти 10000 = 320 000 ops + 0 mem доступ

Подготовительный подход:

255 раз 2 ops (shift, add) times 8 bits = 4080 ops + 255 mem access (записать результат)

Для каждого байта: 2 ops (адреса вычислений) + 2 mem доступ + op (добавить результаты) = 30 000 ops + 20 000 mem доступ

Всего 30 480 ops + 20 255 mem доступ

Таким образом, намного больше доступа к памяти с меньшим количеством операций

Таким образом, если предположить, что все остальное равняется, предварительный расчет на 10 000 байтов происходит быстрее, если мы можем предположить, что доступ к памяти быстрее, чем операция в размере (320 000 - 30 480)/20 255 = 14,29

Скорее всего, это правда, если вы одиноки в выделенном ядре на достаточно современной коробке, так как 255 байтов должны вписываться в кеш. Если вы начинаете получать пропуски кэша, предположение может больше не выполняться.

Кроме того, эта математика предполагает арифметику указателей и прямой доступ к памяти, а также атомные операции и доступ к атомной памяти. В зависимости от выбранного вами языка (и, по-видимому, на основе предыдущих ответов, выбора переключателей компилятора) это предположение может не выполняться.

Наконец, все становится интереснее, если вы рассматриваете масштабируемость: сдвиг может быть легко распараллелен на до 10000 ядер, но предварительное вычисление не обязательно. Однако при увеличении числа байтов поиск становится все более выгодным.

Итак, короче. Да, предварительный расчет быстрее при довольно разумных предположениях, но нет, это не гарантируется быстрее.