gpt4 book ai didi

arrays - 计算排序数组与循环移位交集的快速算法

转载 作者:行者123 更新时间:2023-12-05 02:25:57 33 4
gpt4 key购买 nike

我正在寻找一种更快的算法来解决以下问题:

  • 输入:两个整数数组 AB[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 的顺序上.

我目前的算法基本上如下(注意,dN 是在编译时定义的常量):

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 代码的研究中:数组表示生成奇偶校验矩阵的循环 block 的二进制向量的支持,并且这个条件与循环移位的交集定义了一类具有某些密码含义的“弱 key ”。 (我最初没有提到这一点,因为这个问题单独看来很有趣,并且不需要任何编码理论或密码学知识。)

编辑 2:修正了代码中的一些拼写错误,并改用更好的方法来计算排序列表的交集。 (奇怪的是,我实际上在早期版本中使用了该改进的算法并且代码运行速度较慢,但​​这可能是由于代码中其他地方的实现错误或现在已修复的问题。)

编辑 3:为了将来遇到类似问题的任何人引用,这是我当前的实现,使用下面 virchau13 的回答中的关键思想加上一些小的额外优化。这在实践中似乎非常有效。 (为清楚起见,我重命名了一些变量——arr1arr2 用于输入数组,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
}

几个实现说明:

  1. 这可以很容易地修改以产生最大可能的交集作为一个值(通过取最大值而不是在超过阈值时短路)或一组索引对(通过还将索引对 (i, j) 附加到与每个类次关联的列表 s 计算)。
  2. 我们不需要假设数组已经排序就可以工作。就此而言,我认为我们也不需要假设数组的长度相同,尽管我还没有对不同长度的数组进行测试。

最佳答案

我认为可以将算法降低到 O(d^2)。这只是(未经测试的)推测。

对于两个元素 A[i]B[j]循环相等,(B[j] + s) % N必须等于 A[i] .如果s = s_orig满足这个方程,那么s = s_orig % n也满足这个等式,意味着我们可以限制s0 <= s < N .使用此限制,我们可以证明两个元素循环相等当且仅当 B[j] + s等于 A[i]A[i] + N (自 0 <= A[i],B[i] < N 开始),这等同于说 s必须等于 A[i] - B[j]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 的值时,对都重叠对于它们中的每一个都是相同的。

所以这是最终的算法:

  1. 首先枚举所有可能的 s A 之间的循环差异和 B并将它们放入二维数组中:possible_values: [[usize; d]; d] possible_values[i][j] = (N + A[i] - B[j]) % N .这是 O(d^2)。

  2. 接下来,找到所有唯一的 s值(即 possible_values[i][j] 的唯一值)并存储每个索引列表 s HashMap 中的值 unique_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]值(value)。这是 O(d^2)。

  1. 然后,对于每个唯一的 s value ( for (s, indexes) in &unique_possible_values ),计算它具有的循环相等元素的数量。这等于独特的数量 i -值和独特的数量j -values,可以在 O(indexes.len()) 中计算时间。我不打算为此编写代码,但这应该不难,而且它是 O(d^2)(因为您迭代的每个 2D 索引恰好出现一次)。

  2. 取第 3 步中所有计数的最大值。这是最坏情况下的 O(d^2),平均情况下要低得多。这个最终值对应于 A 和 B 循环交集的最大可能大小。

  3. 检查该值是否超过 threshold .如果是,则返回 true;否则,返回 false。

这个算法基本上枚举了所有可能的s - 以高效的方式计算最大交叉点长度。

关于arrays - 计算排序数组与循环移位交集的快速算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/74168192/

33 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com