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开发者提供了简单而强大的并行扫描功能,特别适合科学计算、数据分析和并行算法实现等场景。