Cómo particionar los bits en una matriz de bits con un tiempo inferior al lineal

Question

Esta es una pregunta de la entrevista que enfrenté recientemente.

---

Dado un conjunto de 1 y 0, encontrar una manera de dividir los bits in place de manera que 0 de se agrupan, y 1'S están agrupados juntos. No importa si los 1 están por delante de los 0 o los 0 están por delante de los 1.

Una entrada ejemplo es 101010101, y la salida es o bien 111110000 o 000011111.

Resuelve el problema en menos de tiempo lineal.

Simplifique el problema. La entrada es una matriz entera, con cada elemento ya sea 1 o 0. La salida es la misma matriz entera con enteros bien particionados.

---

Para mí, esta es una pregunta fácil si se puede resolver de O (N). Mi enfoque es usar dos punteros, comenzando desde ambos extremos de la matriz. Aumenta y disminuye cada puntero; si no apunta al entero correcto, intercambia los dos.

 
    int * start = array; 
    int * end = array + length - 1; 

    while (start < end) { 
     // Assume 0 always at the end 
     if (*end == 0) { 
      --end; 
      continue; 
     } 

     // Assume 1 always at the beginning 
     if (*start == 1) { 
      ++start; 
      continue; 
     } 

     swap(*start, *end); 
    } 

Sin embargo, la entrevista insiste en que hay una solución sub-lineal. Esto me hace pensar mucho pero aún no obtener una respuesta.

¿Alguien puede ayudar en esta pregunta de la entrevista?

ACTUALIZACIÓN: Al ver las respuestas en SO que indican que el problema no se puede resolver en tiempo sub-lineal, puedo confirmar mi idea original de que no puede haber una solución de sub-lineal.

¿Es posible que el entrevistador juegue un truco?

Answer 1

No veo cómo puede haber una solución más rápida que el tiempo lineal.

Imagine una matriz de bits que es todo 1. Cualquier solución requerirá examinar cada bit de esta matriz antes de declarar que ya está particionada. Examinar cada bit requiere tiempo lineal.

Answer 2

No es posible. Hacerlo en tiempo menos que lineal implica que no se observan todos los elementos de la matriz (como una búsqueda binaria). Sin embargo, como no hay forma de saber qué elemento de la matriz es sin mirarlo, debe observar cada elemento de la matriz al menos una vez.

Puede usar tablas de búsqueda para hacerlo más rápido, pero O (n/8) sigue siendo O (n), por lo que el entrevistador se equivocó o no entendió la pregunta.

Answer 3

Quizás la confusión proviene del "tiempo menos que lineal". Por ejemplo, esta solución cuenta el número de bits, lo que hace que una máscara contenga tantos bits. Sólo cuenta los bits mientras que hay incontables de bits:

// from http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan 
unsigned count_bits(unsigned pX) 
{ 
    unsigned result; 
    for (result = 0; v; ++result) 
    { 
     pX &= pX - 1; 
    } 

    return result; 
} 

unsigned n = /* the number */; 

// r contains 000...111, with number of 1's equal to number of 1's in v 
unsigned r = 1 << count_bits(n); 

A pesar de que esto minimiza el número de bits para contar, sigue siendo lineal. Entonces, si esto es lo que significa "sub-lineal", ahí lo tienes.

Pero si realmente querían decir sub-lineal como en logarítmico o constante, no veo la manera.Posiblemente podría hacer una tabla de consulta para cada valor, pero:/

Answer 4

Como han dicho otros, no creo que esto se pueda hacer en menos tiempo lineal. Para la solución de tiempo lineal, puede STL algoritmos en lugar de su propio bucle de esta manera:

int a1[8] = {1,0,1,0,1,0,1,0}; 
std::fill(std::remove(a1, a1+8, 0), a1+8, 0); 

Answer 5

Técnicamente se podría enviar a cada elemento de la matriz a un procesador separado y luego hacerlo en menos tiempo lineal. Si tienes procesadores N, ¡incluso podrías hacerlo en O (1) vez!

Answer 6

Es posible más rápido que en tiempo lineal dado que tiene suficiente memoria, que se puede hacer en O (1)

Utilice la máscara de bits como índice en un vector que se asigna a la máscara de bits con particiones.

usando su ejemplo, en el índice 341 (101010101) se almacena el valor 496 (111110000).

Answer 7

Bueno ... Se puede hacer el tiempo 'menos que lineal' (método descarado).

if(n % 2) 
{ 
    // Arrange all 1's to the right and DON'T check the right-most bit, because it's 1 
}else{ 
    // Arrange all 0's to the right and DON'T check the right-most bit, because it's 0. 
} 

Así que, técnicamente 'grupo' los bits en menos tiempo lineal: P

Answer 8

Para mí, las interpretaciones más probables son:

• Se supone que los bits de estar en una int en lugar de una matriz, en cuyo caso puede usar algo como http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan o una tabla de búsqueda de 8 bits (o más).

• usaron "sublinear" para significar "menos de n operaciones" en lugar de menos que-O (n). Pero incluso eso parece imposible por las mismas razones enumeradas a continuación.

• Hay otra información incorrecta de la cuestión

• lo contrario, la pregunta es incorrecta, ya que todos los elementos de la matriz deben ser examinadas para determinar la respuesta, y que es por lo menos 'n' operaciones.

inmueble ya sea 0s o 1s primeras, y las referencias a los bits en lugar de Bools me hacen pensar algo así como la primera opción se pretende, a pesar de que, cuando se trata de una sola palabra, no hace mucho diferencia. Tengo curiosidad por saber lo que el entrevistador realmente tenía en mente.

Answer 9

La división de este trabajo entre procesadores paralelos cuesta N/M (u O (N)) solo si se supone que el paralelismo aumenta más lentamente que el tamaño del problema. Durante los últimos diez años, el paralelismo (a través de la GPU) ha estado aumentando más rápidamente que los tamaños de problema típicos, y esta tendencia parece continuar en los próximos años. Para una amplia clase de problemas, es instructivo suponer un "paralelismo infinito" o más precisamente, "un paralelismo mayor que cualquier tamaño de problema esperado", porque la marcha del progreso en las GPU y la computación en la nube lo proporciona a lo largo del tiempo.

Asumiendo paralelismo infinito, este problema puede ser resuelto en el tiempo O (logN) debido a que el operador de suma requerida para sumar todos los bits 0 y 1 es asociativa, y por lo que requiere al menos los pasos de tiempo LOGN a completar.