为什么我的并行合并算法会在输出中除第一个位置之外的所有位置上产生正确的值? [英] Why does my parallel merge algorithm produce the correct values in all positions of the output except the first?

问题描述

我正在使用 scoped-threadpool 在Rust中编写并行合并算法，但是似乎在输出中除第一个位置之外的所有位置都产生正确的值.

I am writing a parallel merging algorithm in Rust using scoped-threadpool, but it seems to be producing the correct values in all positions of the output except the first.

我正在尝试从合并算法维基百科页面中修改伪代码:

I am attempting to adapt the pseudocode from the merge algorithm Wikipedia page:

fn parallel_merge(first: &[i32], second: &[i32], output: &mut [i32]) {
    let mut n = first.len();
    let mut m = second.len();
    let a;
    let b;

    // Make sure that 'first' is the largest of the two to be merged
    if m < n {
        a = first;
        b = second;
    } else {
        a = second;
        b = first;

        let tmp = n;
        n = m;
        m = tmp;
    }

    if m <= 0 {
        return;
    }

    let pivot = n / 2;
    let s = bisect(a[pivot], b);
    let t = pivot + s;

    output[t] = a[pivot];

    let mut pool = Pool::new(2);
    pool.scoped(|scoped| {
        let (left, right) = output.split_at_mut(t);
        scoped.execute(move || {
            parallel_merge(&a[..pivot], &b[..s], left);
        });

        scoped.execute(move || {
            parallel_merge(&a[pivot..], &b[s..], right);
        });
    });
}

以 first 作为切片 [1、3、5、7、9] ，以 second 作为 [2]调用时、、 4、6、8、10] 和一个十个零的切片作为初始输出， output 保留为 [0、2、3、4、5、6，7、8、9] .

When called with first as the slice [1, 3, 5, 7, 9], second as [2, 4, 6, 8, 10] and a slice of ten zeroes as the initial output, output is left as [0, 2, 3, 4, 5, 6, 7, 8, 9].

出了什么问题?据我所知，除了不必要的索引跟踪外，它还与伪代码匹配.

What is going wrong? As far as I can see, it matches the pseudocode aside from the unnecessary tracking of indexes.

推荐答案

您误读了该算法. m 是 A 的长度:

You've misread the algorithm. m is the length of A:

algorithm merge(A[i...j], B[k...ℓ], C[p...q]) is

    let m = j - i,
        n = ℓ - k

您将其作为 B 的长度:

let mut m = second.len();

完整的示例:

use scoped_threadpool::Pool; // 0.1.9

fn parallel_merge(a: &[i32], b: &[i32], output: &mut [i32]) {
    let (a, b) = if a.len() >= b.len() { (a, b) } else { (b, a) };

    if a.is_empty() {
        return;
    }

    let pivot = a.len() / 2;
    let s = match b.binary_search(&a[pivot]) {
        Ok(x) => x,
        Err(x) => x,
    };
    let t = pivot + s;

    let (a_left, a_tail) = a.split_at(pivot);
    let (a_mid, a_right) = a_tail.split_first().unwrap();

    let (b_left, b_right) = b.split_at(s);

    let (o_left, o_tail) = output.split_at_mut(t);
    let (o_mid, o_right) = o_tail.split_first_mut().unwrap();

    *o_mid = *a_mid;

    let mut pool = Pool::new(2);
    pool.scoped(|scoped| {
        scoped.execute(move || parallel_merge(a_left, b_left, o_left));
        scoped.execute(move || parallel_merge(a_right, b_right, o_right));
    });
}

#[test]
fn exercise() {
    let first = [1, 3, 5, 7, 9];
    let second = [2, 4, 6, 8, 10];
    let mut output = [0; 10];

    parallel_merge(&first, &second, &mut output);
    assert_eq!(output, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
}

这篇关于为什么我的并行合并算法会在输出中除第一个位置之外的所有位置上产生正确的值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！