Cele mai rapide operațiuni sensibile la comenzi

Pentru orice $v$ mulți $b$vectori -biți $(\mathbf{x}_0, \mathbf{x}_1, \ldots, \mathbf{x}_{v-1}) \in \{\{0, 1\}^b\}^v$, ce este cel mai rapid mod de a combina $\mathbf{x}_0, \mathbf{x}_1, \ldots, \mathbf{x}_{v-1}$ într-un singur număr, astfel încât operația să fie sensibil la ordine?

De exemplu. spune asta $\călărie+$ este o metodă de combinare a numerelor (nu neapărat adunare, dar o putem defini cum vrem). Scopul este de a avea $\mathbf{x}_0 \hat+ \mathbf{x}_1 \hat+ \ldots \hat+ \mathbf{x}_{v-1}$ rezultă într-un număr unic diferit de orice altă ordine, cum ar fi, $\mathbf{x}_{v-1} \hat+ \mathbf{x}_{v-2} \hat+ \ldots \hat+ \mathbf{x}_0$.

Cât despre cel mai rapid, viteza este măsurată pe CPU-uri de uz general. De exemplu. x86-64.

Gândul meu de până acum este:

b_bits_variable xor = 0;
pentru (i = 0; i < v; i++) {
  xor = xor ^ (xor + x_i);
}

Unde:

• b_bits_variable este o variabilă care are exact $b$ multe biți. De exemplu. dacă $b=16$, atunci putem folosi uint16_t în limbajul de programare C.
• v este $v$ (cantitatea de vectori ca în întrebarea de mai sus).
• x_i este $\mathbf{x}_i$ (un vector printre $v$ multe ca la întrebarea de mai sus).
• i++ $= i+1$.
• ^ este XOR pe biți.
• + este adaosul folosit în mod obișnuit în limbajele de programare, care depășește dacă numărul este mai mare decât 2$^b - 1$. eu gândi un astfel de debordare este practic modulo $2^b$ plus. i.e. xor + x_i $=\text{xor} + \mathbf{x}_i \mod 2^b$.

Aceasta este o idee simplă.

voi folosi $x_i$ pentru vectorul în $d$ dimensiuni si utilizare $a_i$ pentru întregul corespunzător în $\{0,1,\ldots, 2^d-1\}$.

Sortați $a_i$ de la mic la mare. Lăsa $r_i$ fie rangul de $a_i$ utilizați ranguri din $\{0,1,\ldots,v-1\}$. Rupeți legăturile în mod arbitrar în timpul sortării.

Exemplu: $(a_1,a_2,a_3)=(1,7,2)$ are vector de rang $(r_1,r_2,r_3)=(0,2,1).$ Există trei intrări numerotate de la 0 la 2, iar intrarea din mijloc 7 este cea mai mare cu rangul 2.

Acum luați în considerare lista permutărilor a 3 obiecte în ordinea lexicografică standard și indexul acestora

$$ 012~~0\\ 021~~1\\ 102~~2\\ 120~~3\\ 201~~4\\ 210~~5\\ $$ și rețineți că această permutare este 021, deci are poziția 1 în lista de permutări. Codificarea poziției ca vector binar ia $r=\lceil \log_2 v\rceil$ biți.

Dacă $r\leq d,$ putem defini $$ x_1+x_2+\cdots+x_v=x_1\oplus x_2\oplus \cdots\oplus x_v \oplus index(permutare(x_1,\ldots,x_v)), $$ deci la final vom xor indicele permutării care se schimbă dacă $x_i$ sunt reordonate.