我正在尋找一種更快的演算法來解決以下問題：
- 輸入：兩個整數陣列，
A范圍B為[0, N)，均為固定長度d，假定按排序順序給出，沒有重復元素。 - 輸出：之間的最大可能交集（即共同元素的數量）
A和回圈移位B是否大于某個指定的閾值t。通過 的回圈移位B，我的意思是[(b s) % N for b in B]某個整數的陣列s。
如果重要的話，我會在 Rust 中實作它（盡管我對一般演算法改進比對特定語言的優化更感興趣），實際上，t它會小于 10，d通常在 15 到 150 之間，并將N大致在2*d*d.
我當前的演算法基本上如下（注意，d并且N是在編譯時定義的常量）：
fn max_shifted_overlap_geq(A: [u32; d], B: [u32; d], threshold: u32) -> bool {
for i in 0..d {
for j in 0..d {
let s = N A[i] - B[j];
let mut B_s = [0; d];
for k in 0..d {
B_s[k] = (B[k] s) % N;
}
B_s.sort();
// Actually, I do an insertion-sort in place as I construct B_s,
// but I'm writing it this way here for simplicity.
if sorted_intersection_count(&A, &B_s) >= threshold {
return true;
}
}
}
false
}
所以我只是從可能的值中選擇移位A[i] - B[j]（因為不是這種形式的移位給出零交集），然后我只是構造回圈移位B并以相當幼稚的方式計算共同元素的數量。
有沒有更有效的演算法，記住陣列的大小相當小？特別是，有沒有更好的方法來找到更可能產生大重疊的變化？
編輯：為了提供額外的背景關系（如下要求），這出現在 QC-MDPC 代碼的研究中：陣串列示生成奇偶校驗矩陣的回圈塊的二進制向量的支持，并且這個條件與回圈移位定義了一類具有一些密碼含義的“弱密鑰”。（我最初沒有提到這一點，因為這個問題看起來很有趣，并且不需要任何編碼理論或密碼學知識。）
編輯 2：修復了代碼中的一些拼寫錯誤，并切換到一種更好的方法來計算排序串列的交叉點。（奇怪的是，我實際上在早期版本中使用了改進的演算法，并且代碼運行速度較慢，但??這可能是由于實作錯誤或代碼中其他地方現已修復的問題。）
編輯 3：對于遇到類似問題的任何人的未來參考，這是我當前的實作，使用下面 virchau13 答案的關鍵思想以及一些小的額外優化。這在實踐中似乎非常有效。（為了清楚起見，我重命名了一些變數——arr1以及arr2輸入陣列，而LEN不是d陣列長度。）
fn relative_shifts(arr1: &[u32; LEN], arr2: &[u32; LEN]) -> [[u32; LEN]; LEN] {
let n = N as u32;
let mut shifts = [[0; LEN]; LEN];
for i in 0..LEN {
for j in 0..LEN {
shifts[i][j] = if arr1[i] < arr2[j] {
n arr1[i] - arr2[j]
} else {
arr1[i] - arr2[j]
}; // this equals (arr1[i] - arr2[j]) % n
}
}
shifts
}
fn max_shifted_overlap_geq(arr1: &[u32; LEN], arr2: &[u32; LEN], threshold: u8) -> bool {
let shifts = relative_shifts(arr1, arr2);
let mut shift_counts = [0; N];
for i in 0..LEN {
for j in 0..LEN {
let count = &mut shift_counts[shifts[i][j] as usize];
*count = 1;
if *count >= threshold {
return true;
}
}
}
false
}
幾個實作說明：
- 這可以很容易地修改為產生最大可能的交集作為一個值（通過在超過閾值時取最大值而不是短路）或一組索引對（通過也將索引對附加
(i, j)到與每個班次關聯的串列中s因為它是計算出來的）。 - 我們不需要假設陣列是排序的。就此而言，我認為我們也不需要假設陣列的長度相同，盡管我還沒有針對不同長度的陣列進行測驗。
uj5u.com熱心網友回復：
我認為可以將演算法降低到 O(d^2)。這只是（未經測驗的）猜測。
對于兩個元素A[i]和B[j]要回圈相等，(B[j] s) % N必須相等A[i]。如果s = s_orig滿足這個方程，那么s = s_orig % n也滿足這個方程，這意味著我們可以限制s為0 <= s < N。使用這個限制，我們可以證明兩個元素回圈相等當且僅當B[j] s等于A[i]or A[i] N（因為0 <= A[i],B[i] < N），這與說s必須等于A[i] - B[j]or相同N A[i] - B[j]。但是，由于0 <= s < N，第一項僅在差為正或為零時才有意義，而第二項僅在差為負時才有意義；即我們可以說s必須等于運算式if A[i] - B[j] < 0 { N A[i] - B[j] } else { A[i] - B[j] }。另一種寫法是s = (N A[i] - B[j]) % N.
請注意，由于s每一對只有一個 的值，當且僅當它們中的每一個的值相同時(i,j)，兩個(i1,j1)和對都重疊。(i2,j2)s
所以這是最終的演算法：
首先列舉和之間所有可能的
s回圈差異A，B并將它們放入一個二維陣列中possible_values: [[usize; d]; d]possible_values[i][j] = (N A[i] - B[j]) % N：這是 O(d^2)。接下來，找到所有唯一
s值（即 的唯一值possible_values[i][j]）并將每個值具有的索引串列存盤s在 hashmapunique_possible_values: HashMap<usize, Vec<(usize, usize)>>中。這句話不是很清楚，所以這就是我的意思：
let unique_possible_values: HashMap<usize, Vec<(usize, usize)>> = HashMap::new();
for i in 0..d {
for j in 0..d {
let indexes_with_same_value =
unique_possible_values
.entry(possible_values[i][j])
.or_insert(Vec::new());
indexes_with_same_value.push((i, j));
}
}
換句話說，hashmap 的每個條目都存盤(i,j)共享相同possible_values[i][j]值的 2D 索引串列。這是 O(d^2)。
然后，對于每個唯一
s值 (for (s, indexes) in &unique_possible_values)，計算它具有的回圈相等元素的數量。這等于唯一值的數量和唯一i值的數量j，可以及時計算O(indexes.len())。我不打算為此撰寫代碼，但這應該不難，而且是 O(d^2) （因為您迭代的每個 2D 索引只發生一次）。取步驟 3 中所有計數的最大值。這是最壞情況 O(d^2) 和平均情況顯著降低。這個最終值對應于 A 和 B 回圈交叉點的最大可能大小。
檢查該值是否超過
threshold. 如果是，則回傳 true；否則，回傳假。
該演算法基本上列舉所有可能s的值并計算最大交叉點長度，但以一種有效的方式。
uj5u.com熱心網友回復：
您可以將每個輸入陣列轉換為長度為 N 的新向量，其中 1 表示出現的值，0 表示其他值。
然后計算兩個向量之間的回圈互相關，找到最大值——即最大交集的大小。
時間以相關計算為主，使用 FFT 技術需要 O(N log N) 時間。這比 d 3好，但它相當復雜，所以它是否會更快可能取決于 N 是否是 2 的冪以及具體實作。如果您有可用于 FFT 的 GPU，那么它會快得多。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/520459.html
標籤：数组算法锈
上一篇：使用遞回生成所有子序列
下一篇：計算到點P的k個最近點的快速方法