Hoạt động nhạy cảm với đơn đặt hàng nhanh nhất

Bất cứ gì $v$ nhiều $b$vectơ -bit $(\mathbf{x}_0, \mathbf{x}_1, \ldots, \mathbf{x}_{v-1}) \in \{\{0, 1\}^b\}^v$, cái gì nhanh nhất cách kết hợp $\mathbf{x}_0, \mathbf{x}_1, \ldots, \mathbf{x}_{v-1}$ thành một số duy nhất, sao cho hoạt động là nhạy cảm với đơn đặt hàng?

Ví dụ. nói rằng $\mũ+$ là một số phương pháp kết hợp các số (không nhất thiết phải cộng, nhưng chúng ta có thể định nghĩa nó theo cách chúng ta muốn). Mục tiêu là có $\mathbf{x}_0 \hat+ \mathbf{x}_1 \hat+ \ldots \hat+ \mathbf{x}_{v-1}$ dẫn đến một số duy nhất khác với bất kỳ thứ tự nào khác, chẳng hạn như, $\mathbf{x}_{v-1} \hat+ \mathbf{x}_{v-2} \hat+ \ldots \hat+ \mathbf{x}_0$.

Đối với nhanh nhất, tốc độ được đo trên các CPU có mục đích chung. Ví dụ. x86-64.

Suy nghĩ của tôi cho đến nay là:

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

ở đâu:

• biến b_bits là một biến có chính xác $b$ nhiều bit. Ví dụ. nếu $b=16$, thì chúng ta có thể sử dụng uint16_t trong ngôn ngữ lập trình C.
• v Là $v$ (số lượng vectơ như trong câu hỏi trên).
• x_i Là $\mathbf{x}_i$ (một vectơ giữa các $v$ nhiều cái như trong câu hỏi trên).
• tôi ++ $= i+1$.
• ^ là bit-khôn ngoan XOR.
• + là phép cộng thường được sử dụng trong các ngôn ngữ lập trình, sẽ tràn nếu số lớn hơn $2^b - 1$. Tôi nghĩ tràn như vậy về cơ bản là modulo $2^b$ phép cộng. I E. xor + x_i $=\text{xor} + \mathbf{x}_i \mod 2^b$.

Đây là một ý tưởng đơn giản.

tôi sẽ sử dụng $x_i$ cho vectơ trong $d$ kích thước và sử dụng $a_i$ cho số nguyên tương ứng Trong $\{0,1,\ldots, 2^d-1\}$.

Sắp xếp các $a_i$ từ nhỏ đến lớn. Để cho $r_i$ là thứ hạng của $a_i$ sử dụng cấp bậc từ $\{0,1,\ldots,v-1\}$. Phá vỡ các ràng buộc tùy ý trong quá trình phân loại.

Ví dụ: $(a_1,a_2,a_3)=(1,7,2)$ có véc tơ hạng $(r_1,r_2,r_3)=(0,2,1).$ Có ba mục được đánh số từ 0 đến 2 và mục ở giữa 7 là mục lớn nhất với thứ hạng 2.

Bây giờ hãy xem xét danh sách hoán vị của 3 đối tượng theo thứ tự từ điển tiêu chuẩn và chỉ mục của chúng

$$ 012~~0\\ 021~~1\\ 102~~2\\ 120~~3\\ 201~~4\\ 210~~5\\ $$ và lưu ý rằng hoán vị này là 021 nên có vị trí 1 trong danh sách các hoán vị. Mã hóa vị trí dưới dạng vectơ nhị phân mất $r=\lceil \log_2 v\rceil$ chút ít.

Nếu $r\leq d,$ chúng ta có thể xác định $$ x_1+x_2+\cdots+x_v=x_1\oplus x_2\oplus \cdots\oplus x_v \oplus index(hoán vị(x_1,\ldots,x_v)), $$ vì vậy, cuối cùng, chúng tôi xor chỉ số của hoán vị sẽ thay đổi nếu $x_i$ được sắp xếp lại.