Tengo pequeños vectores. Cada uno de ellos está formado por 10 números enteros que están entre 0 y 15. Esto significa que cada elemento de un vector se puede escribir usando 4 bits. Por lo tanto, puedo concatenar mis elementos vectoriales y almacenar todo el vector en un solo tipo long (en C, C++, java...)
El vector v1 domina al vector v2 si para cada i en 0,...,9, v1[i] >= v2[i]
Quiero escribir un método de compare(long v1, long v2) que devuelva 0 si ninguno de los vectores domina al otro, 1 si domina el primero y -1 si domina el segundo.
¿Hay alguna forma eficiente de implementar la comparación que no sea obtener cada componente i y hacer 10 veces la comparación normal de enteros?
EDITAR
si v1 es exactamente lo mismo que v2 devolviendo 1 o -1 ambos están bien
Es posible hacer esto usando manipulación de bits. Espacie sus valores para que cada uno ocupe 5 bits, con 4 bits para el valor y un 0 vacío en la posición más significativa como una especie de bit de espaciado.
Colocar un bit de espaciado entre cada valor evita que los préstamos/transportes se propaguen entre valores adyacentes y significa que puede realizar ciertas operaciones aritméticas similares a SIMD en el vector simplemente usando sumas o restas regulares de enteros. Podemos usar la resta para hacer una comparación de vectores.
Para hacer la prueba, puede establecer todos los bits de espaciado en 1 en uno de los vectores y luego restar el segundo. Si el valor de los 4 bits debajo del bit de espaciado es mayor en el segundo, llevará el bit del bit de espaciado y lo pondrá a cero en el resultado, si no, seguirá siendo uno (el primer valor es mayor que o igual al segundo). Si el primer vector domina al segundo, todos los bits de espaciado serán uno después de la resta.
Demostración simple usando ints:
#define SPACING_BITS ((1<<4)|(1<<9)|(1<<14)|(1<<19)) int createVector(int v0, int v1, int v2, int v3) { return v0 | (v1 << 5) | (v2 << 10) | (v3 << 15); } int vectorDominates(int vectorA, int vectorB) { // returns 1 if vectorA dominates vectorB: return (((vectorA | SPACING_BITS) - vectorB) & SPACING_BITS) == SPACING_BITS; } int compare(int vectorA, int vectorB) { if(vectorDominates(vectorA, vectorB)) return 1; else if(vectorDominates(vectorB, vectorA)) return -1; return 0; } Puede extenderlo para usar valores de 64 bits usando 50 bits para almacenar los 10 valores. También puede alinear las llamadas a vectorDominates en la función de comparación.
Bueno, en C probablemente puedas aprovechar la vectorización para hacer esto. No creo que sea directamente posible comparar operandos de 4 bits, por lo que tendrá que volver a empaquetar (ya sea sobre la marcha o simplemente mantener sus datos en un formato más adecuado) hasta 8 bits antes de hacer la comparación. Dado que 10 * 8 = 80, que es más de 64, necesitará instrucciones vectoriales de 128 bits.
No estoy seguro de si las VM de Java lo admiten todavía, pero esta pregunta sugiere que JNI es la respuesta , es decir, llamar al código C desde Java.