rust 带循环移位的有序数组求交的快速算法

mftmpeh8  于 2022-11-12  发布在  其他
关注(0)|答案(2)|浏览(140)

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

  • 输入:[0, N)范围内的两个整数数组AB,长度都是固定的d,假定按排序顺序给出,没有重复的元素。
  • 输出:AB的循环移位之间的最大可能交集(即公共元素的数量)是否大于某个指定的阈值t

如果有必要的话,我会在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代码研究中出现:这些数组表示生成奇偶校验矩阵的循环块的二进制向量的支持,而这个与循环移位相交的条件定义了一类具有某种密码学含义的“弱密钥”(我最初没有提到这一点,因为这个问题在孤立的情况下似乎很有趣,而且不需要任何编码理论或密码学知识)。
编辑2:修正了代码中的一些错别字,并改用了一种更好的方法来计算排序列表的交集(奇怪的是,我在早期版本中实际上使用了这种改进的算法,代码运行得更慢,但这可能是由于实现中的bug或代码中其他地方现在已经修复的问题。
编辑三:为了给以后遇到类似问题的人提供参考,这里是我目前的实现,使用了virchau 13的关键思想,再加上一些小的额外优化。(为了清楚起见,我重命名了一些变量--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.这可以容易地被修改以产生最大可能的交集作为值(通过在超过阈值时取最大值而不是短路)或索引对的集合(还通过在计算每个移位s时将索引对(i, j)附加到与每个移位s关联的列表)。
1.我们不需要假设数组是排序的,也不需要假设数组的长度是一样的,虽然我还没有对不同长度的数组做过测试.

brccelvz

brccelvz1#

我认为有可能把算法的时间复杂度降到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]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
注意,由于每个(i,j)对正好有一个s值,两个(i1,j1)(i2,j2)对当且仅当它们中的每一个的s值都相同时才重叠。
这是最终的算法:
1.首先,枚举AB之间所有可能的s循环差异,并将它们放入二维数组中:这个时间复杂度是O(d^2)。
1.接下来,找到所有唯一的s值(即possible_values[i][j]的唯一值),并将每个s值的索引列表存储在散列表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));
    }
}

换句话说,哈希Map的每个条目都存储了共享相同possible_values[i][j]值的二维索引(i,j)的列表,这是O(d^2)。
1.然后,对于每个唯一的s值(for (s, indexes) in &unique_possible_values),计算它所拥有的循环相等元素的数量。这等于唯一i值的数量和唯一j值的数量,这可以在O(indexes.len())时间内计算出来。我不打算写代码,但这应该不难,它的时间复杂度是O(d^2)(因为迭代的每个二维索引只出现一次)。
1.求步骤3中所有计数的最大值,这是最坏情况下的O(d^2),而平均情况下的O(d^2)要低得多,这个最终值对应于A和B循环交集的最大可能大小。
1.检查该值是否超过threshold,如果超过,则返回true;否则,返回false。
该算法基本上枚举所有可能的s值,并计算最大交集长度,但是是以有效的方式。

d4so4syb

d4so4syb2#

您可以将每个输入数组转换为长度为N的新向量,其中出现在中的值为1,其他值为0。
然后计算两个向量之间的循环互相关,并找到最大值--这是最大交集的大小。
时间主要由相关性计算决定,使用FFT技术需要O(N log N)时间。这比d3要好,但它非常复杂,所以它是否会更快可能取决于N是否是2的幂以及具体的实现。如果你有一个GPU可用于FFT,那么它会快得多。

相关问题