java - Hilbert ordenar por dividir y conquistar algoritmo?

algorithm sorting (3)

Puede calcular la curva de hilbert desde f (x) = y directamente sin usar recursión o sistemas L o dividir y conquistar. Básicamente es un código gris o recorrido de ruta hamiltoniano. Puede encontrar una buena descripción en el blog espacial de quadtree de hilbert curve del índice espacial de Nick o en el deleite del pirata informático. O eche un vistazo al código gris monotónico n-ario. He escrito una implementación en PHP incluyendo una curva de Moore.

Estoy tratando de ordenar los vectores de datos en dimensión d por su orden de Hilbert, para la carga masiva de un índice espacial.

Sin embargo, no quiero calcular explícitamente el valor de Hilbert para cada punto, lo que en particular requiere establecer una precisión particular. En datos de alta dimensión, esto implica una precisión como 32*d bits, lo que se vuelve bastante complicado de hacer de manera eficiente. Cuando los datos se distribuyen de manera desigual, algunos de estos cálculos son innecesarios y se necesita una precisión adicional para partes del conjunto de datos.

En su lugar, estoy tratando de hacer un enfoque de partición. Cuando miras la curva de hilbert de primer orden 2D

1 4 | | 2---3

Primero dividiría los datos a lo largo del eje x, de modo que la primera parte (¡no necesariamente contenga la mitad de los objetos!) Constará de 1 y 2 (aún no ordenados) y la segunda parte tendrá objetos de 3 y 4 solamente. A continuación, dividiría cada mitad de nuevo, en el eje Y, pero revertiría el orden en 3-4.

Básicamente, quiero realizar una estrategia de dividir y conquistar (muy relacionada con QuickSort, ¡en datos distribuidos uniformemente, esto incluso debería ser óptimo!), Y solo calcular los "bits" necesarios del índice de hilbert según sea necesario. Entonces, asumiendo que hay un solo objeto en "1", entonces no hay necesidad de computar la representación completa de él; y si los objetos están distribuidos uniformemente, los tamaños de partición se reducirán rápidamente.

Conozco el enfoque habitual de los libros de texto de la conversión a un entrelazado de dimensión largo y con codificación gris. Esto no es lo que estoy buscando (hay muchos ejemplos disponibles). Quiero explícitamente una clasificación perezosa de dividir y conquistar solamente. Además, necesito más que 2D.

¿Alguien sabe de un artículo o algoritmo de clasificación de hilbert que funcione de esta manera? ¿O una idea clave de cómo hacer las "rotaciones" correctas, qué representación elegir para esto? En particular en las dimensiones más altas ... en 2D es trivial; 1 se gira + y, + x, mientras que 4 es -y, -x (se gira y se voltea). Pero en dimensiones más altas, esto se vuelve más complicado, supongo.

(Por supuesto, el resultado debe ser el mismo que cuando se ordenan los objetos por orden de su hilbert con una precisión suficientemente grande de inmediato; solo estoy tratando de ahorrar tiempo calculando la representación completa cuando no es necesaria, y tengo que gestionarla. Muchos la gente mantiene un hashmap "objeto para el número de hilbert" que es bastante caro.)

Deben ser posibles enfoques similares para las curvas de Peano y la curva Z, y probablemente un poco más fáciles de implementar ... Probablemente debería probar esto primero (la curva Z ya está funcionando; de hecho, se reduce a algo que se parece mucho a un QuickSort, usando el valor medio / cuadrícula apropiado como pivote virtual y ciclo a través de las dimensiones para cada iteración).

Edición : vea a continuación cómo resolví las curvas Z y Peano. También está trabajando para curvas 2D de Hilbert ya. Pero todavía no tengo las rotaciones y la inversión adecuadas para las curvas de Hilbert.

Usa la ordenación de radix . Divida cada índice unidimensional en d .. 32 partes, cada una de tamaño 1 .. 32/d bits. Luego (desde los bits de orden superior a los bits de orden inferior) para cada pieza de índice, calcule su valor de Hilbert y mezcle los objetos en los compartimientos correspondientes.

Esto debería funcionar bien con los datos distribuidos de manera uniforme y desigual, tanto en el ordenamiento de Hilbert como en el orden Z. Y no se necesitan cálculos de precisión múltiple.

Un detalle sobre la conversión de piezas de índice a orden de Hilbert:

primer extracto de bits necesarios,
luego intercalar bits de todas las dimensiones,
luego convierta los índices de una dimensión al código gris inverso.

Si los índices se almacenan en dobles:

Si los índices pueden ser negativos, agregue algún valor para que todo sea positivo y así simplifique la tarea.
Determine la potencia entera más pequeña de 2, que es mayor que todos los índices y divida todos los índices a este valor
Multiplique el índice a 2 ^ (número necesario de bits para el paso de clasificación actual). Trunque el resultado, conviértalo en entero y utilícelo para ordenar Hilbert (intercale y calcule el código gris inverso)
Reste el resultado, truncado en el paso anterior, del índice: index = index - i

Con respecto a su variante del tipo de radix, sugeriría extender zsort (para hacer hilbertsort a partir de zsort) con dos matrices binarias de tamaño d (una utilizada principalmente como pila, otra se usa para invertir los bits de índice) y el valor de rotación (Se usa para reorganizar las dimensiones).

Si el valor máximo en la pila es 1, cambie pivotear (... ascendente) para pivotear (... descendente), y luego, para la primera parte de la recursión, presione este valor superior a la pila, para la segunda, presione la inversa de este valor. Esta pila debe ser restaurada después de cada recursión. Contiene el "árbol de decisión" de las últimas d recursiones del procedimiento de ordenación de radix (en código de Gris inverso).

Después de d recursiones, esta pila de "árbol de decisión" se debe usar para recalcular tanto el valor de rotación como la matriz de inversiones. La manera exacta de hacerlo no es trivial. Se puede encontrar en los siguientes enlaces: hilbert.c o hilbert.c .

Ya respondí esta pregunta (y otras) pero mi (s) respuesta (s) desaparecieron misteriosamente. La implementación del índice compacto de Hilbert de http://code.google.com/p/uzaygezen/source/browse/trunk/core/src/main/java/com/google/uzaygezen/core/CompactHilbertCurve.java (índice de métodos () ) ya permite limitar el número de bits de índice de hilbert calculados hasta un nivel determinado. Cada iteración del bucle del método mencionado calcula un número de bits igual a la dimensionalidad del espacio. Puede refactorizar fácilmente el bucle for para calcular solo un nivel (es decir, un número de bits igual a la dimensionalidad del espacio) a la vez, yendo tan profundamente como sea necesario para comparar lexicográficamente dos números por su índice de Hilbert compacto.