< 返回版块

Matheritasiv 发表于 2022-11-25 15:10

Tags:multi-thread

我在使用rust实现一个非递归版本的双调排序算法,以下是单线程版本的代码:

use rand::Rng;
use std::cmp::PartialOrd;

struct SortIndex {
    start: usize,
    end: usize,
    char_num: usize,
    mod_num: usize,
    stop: bool,
}

impl SortIndex {
    fn new(start: usize, end: usize, char_bit: u32, mod_bit: u32) -> Self {
        SortIndex {
            start, end,
            char_num: 1usize.wrapping_shl(char_bit),
            mod_num: 1usize.wrapping_shl(mod_bit).wrapping_sub(1),
            stop: start >= end,
        }
    }
}

impl Iterator for SortIndex {
    type Item = (usize, usize);
    fn next(&mut self) -> Option<(usize, usize)> {
        if self.stop { return None; }
        let out = self.start;
        let mut x = out.wrapping_add(1);
        let _ = (x ^ out) & self.char_num == 0 || x & self.mod_num == 0 || {
            x = x.wrapping_add(self.char_num);
            x & self.mod_num != 0
        } || {
            x = x.wrapping_add(self.char_num);
            true
        };
        if x >= self.end || x <= out {
            self.stop = true;
        } else {
            self.start = x;
        }
        return Some((out, out ^ self.char_num));
    }
}

fn bitonic_sort<T>(data: &mut [T], depth: u32)
where T: Copy + PartialOrd {
    if depth == 0 { return; }
    let n = 1usize << depth;
    for cnt in 1 .. depth + 1 {
        for i in (0 .. cnt).rev() {
            for (ind1, ind2) in SortIndex::new(0, n, i, cnt) {
                if data[ind2] < data[ind1] {
                    data.swap(ind1, ind2);
                }
            }
        }
    }
}

fn main() {
    let mut rng = rand::thread_rng();
    let n = 1000000;
    let mut nums = (0 .. 4096).map(|_| rng.gen_range(-n ..= n)).collect::<Vec<i32>>();
    bitonic_sort(&mut nums, 12);
    println!("{:?}", nums);
}

它的基本原理是由SortIndex迭代器产生元素下标,然后由排序线程对这些下标指向的元素进行比较以及作可能的对换操作。每轮迭代产生的这些下标都是两两不交的,因此每轮对换过程理论上可以并行进行,但用rust线程机制来实现,则需要多个线程同时借用nums的可变引用,这是不被允许的。用chunks_mut()nums切片并分派到各个线程对于这个算法来说也不可行,因为需要对换的下标可能会跨越相当大的范围。请问这个问题有没有什么比较好的、运行开销小的多线程解决方案?

评论区

写评论
作者 Matheritasiv 2022-11-29 15:20

大家帮忙看看这个实现有问题吗:

let shared_indexes = Arc::new(Mutex::new(SortIndex::new(0, n, i, cnt)));
for _ in 0 .. t_n {
    let shared_indexes = shared_indexes.clone();
    thread_list.push(spawn(move || {
        while let Some((ind1, ind2)) = shared_indexes.lock().unwrap().next() {
            let (ind1, ind2) = (ind1 as isize, ind2 as isize);
            unsafe {
                if *data.offset(ind2) < *data.offset(ind1) {
                    (*data.offset(ind1), *data.offset(ind2)) =
                        (*data.offset(ind2), *data.offset(ind1));
                }
            }
        }
    }));
}

我实测这个版本的运行时间大约是单线程版本的20倍,不管是开16个线程还是开2个线程。

Neutron3529 2022-11-25 18:16

直接unsafe

unsafe就是让你处理多个可变借用的

你直接unsafe解引用裸指针就好

1 共 2 条评论, 1 页