Proceso de selección binaria

Question

He estado trabajando en lo que parece ser una tarea simple que me está volviendo loco. Entonces, si te apetece un desafío de programación ... sigue leyendo.

Quiero ser capaz de tomar un rango de números, p. [1:20] e imprima los valores usando un mecanismo similar a un algoritmo de búsqueda binario. Entonces, imprima primero el valor más bajo (en este caso 1) y luego el valor medio (por ejemplo, en este caso 10) y luego divida el rango en trimestres e imprima los valores en 1/4 y 3/4 (en este caso, 5 y 15) y luego divida en ochos y así sucesivamente hasta que todos los valores en el rango hayan sido impresos.

La aplicación de esto (que no es realmente necesario entender aquí) es para un mecanismo de acceso a la página de memoria que se comporta de manera más eficiente cuando se accede a las páginas en los rangos medios primero.

Para este problema, sería suficiente tomar cualquier rango de números e imprimir los valores de la manera descrita anteriormente.

¿Alguna idea de esto? Una solución de código psuedo estaría bien. Mostraría un intento de esto, pero todo lo que he intentado hasta ahora no lo corta. Gracias.

Actualización: Según lo solicitado, la salida deseada para el ejemplo [1:20] sería algo como esto: 1, 10, 5, 15, 3, 7, 12, 17, 2, 4, 6, 8, 11, 13, 16, 18, 9, 19, 20

Esta salida se podría presentar de muchas maneras similares según el algoritmo utilizado. Pero la idea es mostrar primero los valores medios, luego los trimestres, luego los ochos, luego los decimosexto, etc., omitiendo los valores presentados anteriormente.

Answer 1

Aquí hay un código Python producir una salida similar a su ejemplo:

def f(low, high): 
    ranges = collections.deque([(low, high)]) 
    while ranges: 
     low, high = ranges.popleft() 
     mid = (low + high) // 2 
     yield mid 
     if low < mid: 
      ranges.append((low, mid)) 
     if mid + 1 < high: 
      ranges.append((mid + 1, high)) 

Ejemplo:

>>> list(f(0, 20)) 
[10, 5, 15, 2, 8, 13, 18, 1, 4, 7, 9, 12, 14, 17, 19, 0, 3, 6, 11, 16] 

La gama low, high excluye el punto final, como es la convención en Python, por lo que el resultado contiene el números del 0 al 19.

El código utiliza un FIFO para almacenar los subintervalos que aún deben procesarse. El FIFO se inicializa con el rango completo. En cada iteración, el siguiente rango aparece y se produce el punto medio. Luego, el subrango inferior y superior del rango actual se agrega al FIFO si no están vacíos.

Editar: Aquí es una aplicación completamente diferente en C99:

#include <stdio.h> 

int main() 
{ 
    const unsigned n = 20; 
    for (unsigned i = 1; n >> (i - 1); ++i) { 
     unsigned last = n; // guaranteed to be different from all x values 
     unsigned count = 1; 
     for (unsigned j = 1; j < (1 << i); ++j) { 
      const unsigned x = (n * j) >> i; 
      if (last == x) { 
       ++count; 
      } else { 
       if (count == 1 && !(j & 1)) { 
        printf("%u\n", last); 
       } 
       count = 1; 
       last = x; 
      } 
     } 
     if (count == 1) 
      printf("%u\n", last); 
    } 
    return 0; 
} 

Esto evita la necesidad de un FIFO mediante el uso de algunos trucos para determinar si un entero ya se ha producido en una iteración anterior.

También podría implementar fácilmente la solución original en C. Dado que conoce el tamaño máximo de FIFO (supongo que es algo así como (n + 1)/2, pero tendría que verificarlo dos veces), puede use un buffer de anillo para mantener los rangos en cola.

Editar 2: Aquí hay otra solución en C99. Está optimizado para hacer solo la mitad de iteraciones de bucle y para usar solo opraciones y adiciones de bit, sin multiplicación o divisiones. También es más sucinto, y no incluye 0 en los resultados, por lo que puede hacer que esto vaya al principio como lo pretendía inicialmente.

for (int i = 1; n >> (i - 1); ++i) { 
    const int m = 1 << i; 
    for (int x = n; x < (n << i); x += n << 1) { 
     const int k = x & (m - 1); 
     if (m - n <= k && k < n) 
      printf("%u\n", x >> i); 
    } 
} 

(Este es el código tenía la intención de escribir desde el principio, pero me tomó un tiempo para envolver mi cabeza alrededor de ella.)

Answer 2

Binary Heap como un array que ya tiene esta estructura. Es posible que desee almacenar su matriz en este formulario e imprimirla secuencialmente. Para el nodo i, los hijos son 2i + 1, 2i + 2.

Answer 3

Hmmm ... básicamente estás buscando algún tipo de curva de relleno de espacio. Estoy casi seguro de que puedes hacer eso con astucia inteligente. Tal vez le interese observar la forma en que se calculan los índices para el orden Z de Morton o la indexación de Ahnentafel que se usa en algunos algoritmos de galería de símbolos ajenos a la caché. Eché un vistazo a esto hace algunos años, y la indexación fue similar a lo que estás describiendo y hecho con un poco de tictac.

Answer 4

Es fácil para 1/2, ¿verdad?

¿Por qué no hacerlo recursivamente, de modo que 1/4 es 1/2 de 1/2, y 1/8 es 1/2 de 1/4?