Rust并行迭代与扫描库rayon-scan的使用,rayon-scan提供高性能并行扫描和累积操作功能

Rust并行迭代与扫描库rayon-scan的使用,rayon-scan提供高性能并行扫描和累积操作功能

这个crate提供了Rayon的ParallelIterator上的Iterator scan方法的并行版本。

扫描是一个高阶函数,类似于fold,但在每一步累积中间结果。具体来说,扫描迭代器的第n个元素是使用给定操作减少输入的前n个元素的结果。

并行扫描的主要区别是操作符必须是关联的。在顺序扫描中,操作从左到右应用于输入,但在并行扫描中,顺序是未指定的。

用法

// Iterate over a sequence of numbers `x0, ..., xN`
// and use scan to compute the partial sums
use rayon::prelude::*;
use rayon_scan::ScanParallelIterator;

let partial_sums = [1, 2, 3, 4, 5]
                    .into_par_iter()       // iterating over i32
                    .scan(|a, b| *a + *b,  // add (&i32, &i32) -> i32
                          0)               // identity
                    .collect::<Vec<i32>>();
assert_eq!(partial_sums, vec![1, 3, 6, 10, 15]);

性能

对于整数上的常规前缀和或乘积,并行开销太大,无法看到并行版本的任何改进。然而,足够复杂的操作(如大型矩阵乘法)可以看到巨大的性能优势。

为了最大化性能,最好限制拆分的数量,例如使用.with_min_len()。并行扫描有一个顺序部分,其时间与拆分数量成线性关系。

有关实现和性能的更多详细信息。

测试和基准测试

运行测试:

cargo test

运行基准测试:

cargo +nightly test --features "bench"

许可证

根据Apache 2.0和MIT许可。

注意:这个功能正在合并到Rayon中,如果合并,这个crate应该会过时。

完整示例代码

// 使用rayon-scan进行并行扫描操作的完整示例
use rayon::prelude::*;
use rayon_scan::ScanParallelIterator;

fn main() {
    // 创建一个数字数组
    let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    
    // 使用并行扫描计算部分和
    let partial_sums = numbers
        .into_par_iter()           // 转换为并行迭代器
        .scan(|a, b| *a + *b,      // 关联操作:加法
              0)                   // 初始值(恒等元素)
        .collect::<Vec<i32>>();    // 收集结果
    
    println!("原始数组: {:?}", numbers);
    println!("部分和: {:?}", partial_sums);
    
    // 验证结果
    let expected = vec![1, 3, 6, 10, 15, 21, 28, 36, 45, 55];
    assert_eq!(partial_sums, expected);
    
    // 另一个示例:计算部分乘积
    let partial_products = numbers
        .into_par_iter()
        .scan(|a, b| *a * *b,      // 关联操作:乘法
              1)                   // 乘法的恒等元素
        .collect::<Vec<i32>>();
    
    println!("部分乘积: {:?}", partial_products);
}

1 回复

Rust并行迭代与扫描库rayon-scan的使用指南

rayon-scan是一个基于Rayon的高性能并行扫描和累积操作库,提供了高效的并行前缀扫描功能。它特别适合处理大规模数据集的累积计算任务。

核心功能

  • 并行前缀扫描(前缀和、前缀乘积等)
  • 支持自定义二元操作和初始值
  • 与Rayon并行迭代器无缝集成
  • 提供原地(in-place)和生成新集合两种操作模式

基本使用方法

首先在Cargo.toml中添加依赖:

[dependencies]
rayon = "1.5"
rayon-scan = "0.1"

示例代码

1. 基本前缀和计算

use rayon_scan::ScanParallelIterator;
use rayon::prelude::*;

fn main() {
    let data = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    
    // 并行计算前缀和
    let prefix_sums: Vec<i32> = data
        .par_iter()
        .scan(|a, b| a + b, 0)
        .collect();
    
    println!("前缀和结果: {:?}", prefix_sums);
    // 输出: [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
}

2. 自定义累积操作

use rayon_scan::ScanParallelIterator;
use rayon::prelude::*;

fn main() {
    let numbers = vec![2, 3, 4, 5];
    
    // 并行计算前缀乘积
    let prefix_products: Vec<i32> = numbers
        .par_iter()
        .scan(|a, b| a * b, 1)
        .collect();
    
    println!("前缀乘积: {:?}", prefix_products);
    // 输出: [2, 6, 24, 120]
}

3. 字符串连接操作

use rayon_scan::ScanParallelIterator;
use rayon::prelude::*;

fn main() {
    let words = vec!["Hello", " ", "World", "!"];
    
    let concatenated: Vec<&str> = words
        .par_iter()
        .scan(|a, b| if a.is_empty() { *b } else { a }, "")
        .collect();
    
    println!("连接结果: {:?}", concatenated);
    // 输出: ["Hello", "Hello ", "Hello World", "Hello World!"]
}

4. 原地扫描操作

use rayon_scan::ScanParallelIterator;
use rayon::prelude::*;

fn main() {
    let mut data = vec![1, 2, 3, 4, 5];
    
    // 原地进行前缀和计算
    data.par_iter_mut()
        .scan_in_place(|a, b| *a + *b);
    
    println!("原地扫描结果: {:?}", data);
    // 输出: [1, 3, 6, 10, 15]
}

完整示例demo

use rayon_scan::ScanParallelIterator;
use rayon::prelude::*;

fn main() {
    println!("=== rayon-scan 完整使用示例 ===");
    
    // 示例1: 基本前缀和计算
    println!("\n1. 基本前缀和计算:");
    let data = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    let prefix_sums: Vec<i32> = data
        .par_iter()
        .scan(|a, b| a + b, 0)
        .collect();
    println!("输入: {:?}", data);
    println!("输出: {:?}", prefix_sums);
    
    // 示例2: 自定义累积操作 - 前缀乘积
    println!("\n2. 前缀乘积计算:");
    let numbers = vec![2, 3, 4, 5];
    let prefix_products: Vec<i32> = numbers
        .par_iter()
        .scan(|a, b| a * b, 1)
        .collect();
    println!("输入: {:?}", numbers);
    println!("输出: {:?}", prefix_products);
    
    // 示例3: 字符串连接操作
    println!("\n3. 字符串连接操作:");
    let words = vec!["Hello", " ", "World", "!"];
    let concatenated: Vec<&str> = words
        .par_iter()
        .scan(|a, b| if a.is_empty() { *b } else { a }, "")
        .collect();
    println!("输入: {:?}", words);
    println!("输出: {:?}", concatenated);
    
    // 示例4: 原地扫描操作
    println!("\n4. 原地扫描操作:");
    let mut data_in_place = vec![1, 2, 3, 4, 5];
    println!("原始数据: {:?}", data_in_place);
    data_in_place.par_iter_mut()
        .scan_in_place(|a, b| *a + *b);
    println!("原地扫描后: {:?}", data_in_place);
    
    // 示例5: 自定义操作 - 寻找最大值
    println!("\n5. 前缀最大值计算:");
    let values = vec![3, 1, 4, 1, 5, 9, 2, 6];
    let prefix_max: Vec<i32> = values
        .par_iter()
        .scan(|a, b| if a > b { a } else { b }, i32::MIN)
        .collect();
    println!("输入: {:?}", values);
    println!("输出: {:?}", prefix_max);
}

性能注意事项

  • 对于小数据集(通常少于1000个元素),顺序扫描可能更快
  • 大数据集能从并行处理中获得显著性能提升
  • 确保二元操作是结合性的,这是并行扫描正确性的前提条件

错误处理

扫描操作要求二元操作满足结合律,否则结果可能不正确。请确保您的操作满足数学上的结合性要求。

rayon-scan为Rust开发者提供了简单而强大的并行扫描功能,特别适合科学计算、数据分析和并行算法实现等场景。

回到顶部