interview - data structures and algorithms pdf

Conjunto de 10000 con elementos de 16 bits, conjunto de bits de búsqueda(RAM ilimitada)-entrevista a Google

Question

Esto se me preguntó en mi entrevista de Google recientemente y ofrecí una respuesta que implicó un cambio de bit y fue O (n), pero ella dijo que esta no es la forma más rápida de hacerlo. No entiendo, ¿hay una manera de contar los bits establecidos sin tener que iterar sobre todos los bits proporcionados?

Answer 1

Acabo de implementarlo en 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);
    }

}
}

También en https://github.com/leitao/bits-in-a-16-bits-integer-array/blob/master/Main.java

Answer 2

Fuerza bruta: 10000 * 16 * 4 = 640,000 operaciones. (desplazamiento, comparación, incremento e iteración para cada palabra de 16 bits)

Manera más rápida:

Podemos construir la tabla 00-FF -> número de bits establecidos. 256 * 8 * 4 = 8096 operaciones

Es decir, construimos una tabla donde para cada byte calculamos un número de bits establecidos.

Luego, por cada int de 16 bits, lo dividimos en superior e inferior

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 operaciones en total en la iteración. Es decir, 68096 operaciones en total. Sin embargo, es O (n), pero con menos constante (~ 9 veces menos).

En otras palabras, calculamos el número de bits para cada número de 8 bits, y luego dividimos cada número de 16 bits en dos de 8 bits para contar los bits establecidos utilizando la tabla preconstruida.

Answer 3

Hay (casi) siempre una manera más rápida. Lea acerca de las tablas de búsqueda .

Answer 4

No sé cuál fue la respuesta correcta cuando se hizo esta pregunta, pero creo que la forma más sensata de resolver esto hoy es usar la instrucción POPCNT . Específicamente, debes usar la versión de 64 bits . Como solo queremos el número total de bits establecidos, los límites entre los elementos de 16 bits no nos interesan. Como las instrucciones POPCNT 32 bits y 64 bits son igualmente rápidas , debe usar la versión de 64 bits para contar el valor de cuatro elementos de bits por ciclo.

Answer 5

Puede pre-calcular los conteos de bits en bytes y luego usarlos para la búsqueda. Es más rápido, si haces ciertas suposiciones.

El número de operaciones (solo el cálculo, no la entrada de lectura) debe tomar lo siguiente

Enfoque por turnos :

Para cada byte: 2 ops (shift, add) veces 16 bits = 32 ops, 0 tiempos de acceso mem 10000 = 320 000 ops + 0 acceso mem

Enfoque de precálculo:

255 veces 2 operaciones (desplazar, agregar) veces 8 bits = 4080 operaciones + 255 acceso mem (escriba el resultado)

Para cada byte: 2 ops (direcciones de cálculo) + 2 acceso mem + op (agregar los resultados) = 30 000 ops + 20 000 acceso mem

Total de 30 480 ops + 20 255 mem de acceso

Así que mucho más acceso a la memoria con muchas menos operaciones.

Por lo tanto, suponiendo que todo lo demás sea igual, el cálculo previo para 10 000 bytes es más rápido si podemos asumir que el acceso a la memoria es más rápido que una operación por un factor de (320 000 - 30 480) / 20 255 = 14.29

Lo que probablemente sea cierto si está solo en un núcleo dedicado en una caja razonablemente moderna, ya que los 255 bytes deben caber en un caché. Si comienza a obtener errores de caché, la suposición ya no se mantendrá.

Además, esta matemática asume aritmética de punteros y acceso directo a la memoria, así como operaciones atómicas y acceso a la memoria atómica. Dependiendo de su idioma de elección (y, aparentemente, basado en respuestas anteriores, de su elección de compiladores), esa suposición podría no ser válida.

Finalmente, las cosas se vuelven más interesantes si considera la escalabilidad: los cambios se pueden paralizar fácilmente en hasta 10000 núcleos, pero no es necesario el cálculo previo. Sin embargo, a medida que aumenta el número de bytes, la búsqueda se vuelve cada vez más ventajosa.

Así que, en definitiva. Sí, el cálculo previo es más rápido bajo suposiciones bastante razonables, pero no, no se garantiza que sea más rápido.