Confronto efficiente di vettori di numeri interi piccoli

Question

Ho piccoli vettori. Ciascuno di essi è composto da 10 numeri interi compresi tra 0 e 15. Ciò significa che ogni elemento di un vettore può essere scritto utilizzando 4 bit. Quindi posso concatenare i miei elementi vettoriali e memorizzare l'intero vettore in un singolo tipo long (in C, C++, java ...)

Vector v1 domina vettore v2 se per ogni i in 0, ..., 9, v1 [i]> = v2 [i]

Voglio scrivere un metodo compare(long v1, long v2) che restituirebbe 0 se non dei vettori domina l'altro, 1 se il primo domina e -1 se il secondo domina.

Esiste un modo efficace per implementare un confronto diverso dall'ottenere ogni componente i e fare 10 volte il normale confronto tra interi?

EDIT

se v1 è esattamente lo stesso di v2 ritorno 1 o -1 sono entrambi bene

Answer 1

È possibile farlo utilizzando la manipolazione dei bit. Spazia i tuoi valori in modo che ciascuno occupi 5 bit, con 4 bit per il valore e uno 0 vuoto nella posizione più significativa come una sorta di bit di spaziatura.

Posizionando un bit di spaziatura tra ogni valore, i fermi/portatori si spostano dalla propagazione tra valori adiacenti e significa che è possibile eseguire determinate operazioni aritmetiche SIMD sul vettore semplicemente utilizzando l'aggiunta o la sottrazione di un intero normale. Possiamo usare la sottrazione per fare un confronto vettoriale.

Per eseguire il test è possibile impostare tutti i bit di spaziatura su 1 in uno dei vettori e quindi sottrarre il secondo. Se il valore nei 4 bit al di sotto del bit di spaziatura è maggiore nel secondo, esso trasporterà il bit dal bit di spaziatura e lo imposterà a zero nel risultato, altrimenti se rimarrà uno (il primo valore è maggiore uguale o uguale al secondo). Se il primo vettore domina il secondo, tutti i bit di spaziatura saranno uno dopo la sottrazione.

semplice dimostrazione utilizzando int:

#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; 
} 

qui può allungare di utilizzare i valori a 64 bit utilizzando 50 bit per memorizzare i 10 valori. È inoltre possibile integrare le chiamate su vectorDominates nella funzione di confronto.

Demo

Answer 2

Beh, in C si può probabilmente leva vettorializzazione di fare questo. Non penso sia possibile confrontare direttamente su operandi a 4 bit, quindi dovrai reimballare (o al volo o mantenere i tuoi dati in un formato più adatto) fino a 8-bit prima di fare il confronto. Poiché 10 * 8 = 80, che è più di 64, avrai bisogno di istruzioni vettoriali a 128 bit.

Non sono sicuro che le macchine virtuali Java lo supportino ancora, ma this question suggests that JNI is the answer, ad esempio chiamata codice C da Java.