查找数字在Pai中出现位置
之前使用Go编程实现查找数字在Pai中出现位置【在这里】，查找10亿位的Pai文件。这次使用Rust多线程实现。Rust擅长命令行程序的编写，因此也编译成命令行模式。
先分析源代码:
fn find_pai_from_current_dir() -> Result<String, Box<dyn Error>> { // 1.1
let current_dir = env::current_dir().unwrap();
let entries = match fs::read_dir(¤t_dir) {
Ok(entries) => entries,
Err(e) => {
eprintln!("Error reading directory: {}", e);
return Err(Box::new(e));
}
};
for entry in entries {
match entry {
Ok(entry) => {
let path = entry.path();
if path.is_file() && path.file_name().and_then(|s| s.to_str()) // 1.2
.map_or(false, |s| s.split(std::path::MAIN_SEPARATOR).last()
.map_or(false, |name| name.starts_with("pi-") && name.ends_with(".txt"))) {
return Ok(path.to_string_lossy().into_owned());
}
},
Err(e) => eprintln!("Error reading entry: {}", e),
}
}
Err(Box::from("PAI file not found in the current directory"))
}标记1.1 这个函数是寻找默认pai文件。当命令行没有显式提供pai文件位置，它自动从当前目录寻找
标记1.2 这里使用and_then, and_then作用于Option，对Option中值自动提取，所以path.file_name()返回的是Option，而闭包中的s是解Option后的&OsStr； Rust设计之时没有空值，对可能出错之处就使用Option，这点与Java/Go非常不一样，后者需要不停判断 xyz != Null / xyz != Nil
impl Params { // 2.1
pub fn new(search_number: String, pai_file: String) -> Self {
Params { search_number, pai_file }
}
pub fn check_params(&self) -> Result<(), String> {
// make sure the search_number are all number characters
if !self.search_number.chars().all(|c| c.is_digit(10)) {
return Err("Search number must contain only digits".to_string());
}
// make sure the pai_file exists
if !std::path::Path::new(&self.pai_file).exists() {
return Err(format!("PAI file does not exist: {}", self.pai_file));
}
Ok(())
}
}标记2.1 这里是定义参数结构的，并加方法check_params，注意判断c是否数字的方法is_digit(10), 非常有趣。is_digit还有参数2，8，16，36，可以猜测一下是判断什么的。
const DEFAULT_THREADS_COUNT: usize = 10; // 3.1
const DEFAULT_BLOCK_SIZE: usize = 4096;
pub fn run(params: Params) -> Result<i64, String> {
params.check_params()?;
let mut threads = vec![];
let shared_result = Arc::new(RwLock::new(usize::MAX));
for thread_id in 0..DEFAULT_THREADS_COUNT {
let pai_file_path = params.pai_file.clone();
let search_number = params.search_number.clone();
let shared_result = Arc::clone(&shared_result);
let handle = thread::spawn(move || {
if let Err(e) = process_blocks(thread_id, &search_number, &pai_file_path, shared_result) {
eprintln!("Thread {} encountered an error: {}", thread_id, e);
}
});
threads.push(handle);
}
for t in threads {
t.join().expect("A thread panicked");
}
let result = *shared_result.read().unwrap();
if result == usize::MAX {
Ok(-1) // Not found
} else {
Ok(result as i64)
}
}标记3.1 这一段是启动线程的方法，关于线程数和每次读取Block的size配置，需要着重说一下。在同样搜索000000~000999时，不同配置差别很大。下表中横轴是线程数配置，纵轴是每次读取文本长度配置，中间是找这1000个数字花费的时间(秒)。因为本机是M4 10核+10显卡核，总体看10个线程是最快的，看样操作系统是使用全部核心去调度10个线程任务，这个没有问题。那为什么配置每次读取1M却变慢了呢？这是因为查找的6位数字基本在很靠前的位置就找到了，比如log中显示的000990到000999，最多也就位于2 million的位置，你一个线程读入1 million位，完全发挥不了多线程同时搜索的优势。另外，按照下面最快的配置，找完100万个数字需要 3.5*1000 sec，大约58分钟(实际运行还真是58分钟)。
| 配置 | 1个线程 | 2个线程 | 4个线程 | 10个线程 | 16个线程 |
|---|---|---|---|---|---|
| 1 KB | 14.3 | 7.5 | 4.3 | 3.7 | 4.6 |
| 2 KB | 14.3 | 7.4 | 4.1 | 3.5 | 4.4 |
| 4 KB | 14.1 | 7.3 | 4.1 | 3.5 | 4.4 |
| 16 KB | 14.2 | 7.3 | 4.2 | 3.6 | 4.4 |
| 1024 KB | 14.0 | 13.7 | 15.0 | 22.3 | 28.4 |
这个跟之前使用Go编写的效率有差距，Go一次性读入全部数据到内存，并反复查找各个数字，尽管只用一个线程，但20分钟就全部完成了。这个Rust多线程不是为了尽可能快找多个数字的，而是尽可能快找一个数。如果Rust改变写法，多线程并发寻找这些数，应该不会比Go差。
Search 000990, found it at: 2368408
Search 000991, found it at: 162536
Search 000992, found it at: 495206
Search 000993, found it at: 95967
Search 000994, found it at: 1069448
Search 000995, found it at: 115749
Search 000996, found it at: 48497
Search 000997, found it at: 1954924
Search 000998, found it at: 1341375
Search 000999, found it at: 357702fn process_blocks_more_params (thread_id: usize,
search_number: &str,
pai_file_path: &str,
shared_result: Arc<RwLock<usize>>,
block_size: usize,
threads_count: usize
) -> std::io::Result<()> {
let mut file = File::open(pai_file_path)?;
let file_size = file.metadata()?.len() as usize;
let search_number_len = search_number.len() ;
let mut block_index = thread_id;
let mut buffer = vec![0u8; block_size + search_number_len - 1];
loop {
let block_offset = block_index * block_size;
// 其他线程已经找到结果因此本线程退出
let need_stop = {
let read_guard = shared_result.read().unwrap();
block_offset > *read_guard
};
if need_stop || block_offset >= file_size {
break;
}
let read_size = if block_offset + block_size + search_number_len - 1 > file_size {
file_size - block_offset
} else {
block_size + search_number_len - 1
};
file.seek(SeekFrom::Start(block_offset as u64))?;
file.read_exact(&mut buffer[..read_size])?;
// 检查buffer[..read_size]是否包含search_number
if let Some(pos) = buffer[..read_size]
.windows(search_number_len)
.position(|window| {window == search_number.as_bytes()}) {
let found_index = block_offset + pos - 1; //计算小数点后第x位
let mut write_guard = shared_result.write().unwrap();
if found_index < *write_guard {
*write_guard = found_index;
}
break;
}
block_index += threads_count;
}
Ok(())
}上面一段是具体搜索逻辑，使用读写锁，不在赘述。最后，程序编译后使用如下。如上所述，6位数字全能找到，8位的数字也基本都能找到，但9位10位再多位就有很多找不到了。注意在没有找到的情况下，也就是搜索完全部10亿位，用时2.5sec.
$ ./pai 3
You know where it is :)
$ ./pai 14159
Found it located at: 1
Time Taken: 0 ms
$ ./pai 123456789
Found it located at: 523551502
Time Taken: 1329 ms
$ ./pai 233333333
Not found
Time Taken: 2484 ms
$ ./pai 23333333
Found it located at: 18216167
Time Taken: 68 ms
$ ./pai 000000000
Not found
Time Taken: 2483 ms
$ ./pai 00000000
Found it located at: 172330850
Time Taken: 462 ms
$ ./pai 19990101
Found it located at: 175044975
Time Taken: 473 ms
$ ./pai 66666666
Found it located at: 45681781
Time Taken: 139 ms
$ ./pai abad
Error: Search number must contain only digitsp.s. 为了探索找到100万个数字的最小时间，重写了搜索函数。主要思想是从pai文件中依次取6位数，看它是否已经被找到。如果已被找到，则跳过，没被找到，则记录位置；实际上，最多查到1400万位就全部找到了。之前说使用Go写的类似方法，需要20分钟(当然是多年前的机器)，然后开始的那种多线程搜索，花费58分钟，但是使用下面函数搜索，只用了3.1秒！
pub fn find_all_6_digits_quickly() -> Result<HashMap<i32, i32>> {
const FIND_6_DIGITS_BLOCK_SIZE: usize = 1024 * 1024;
const PAI_FILE_PATH: &str = "/Users/peter/data/pi-billion.txt";
let mut map: HashMap<i32,i32> = HashMap::new();
let mut file = File::open(PAI_FILE_PATH)?;
let file_size = file.metadata()?.len() as usize;
let mut loopnum = 0;
let start_time = Instant::now();
loop {
println!("checking the {} MB", loopnum);
let block_offset = loopnum * FIND_6_DIGITS_BLOCK_SIZE;
if block_offset > file_size - 6 {
break;
}
let read_size = if block_offset + FIND_6_DIGITS_BLOCK_SIZE + 5 > file_size {
file_size - block_offset
} else {
FIND_6_DIGITS_BLOCK_SIZE + 5
};
let mut buffer = vec![0u8; read_size];
file.seek(SeekFrom::Start(block_offset as u64))?;
file.read_exact(&mut buffer)?;
for i in 0..=buffer.len().saturating_sub(6) {
let slice = &buffer[i..i+6];
if let Ok(num_str) = std::str::from_utf8(slice) {
if let Ok(num) = num_str.parse::<i32>() {
map.entry(num).or_insert((block_offset + i -1) as i32);
}
}
}
//检查是否全部找到了
if map.keys().len() >= 1_000_000 {
break;
}
loopnum += 1;
}
let elapsed_time = start_time.elapsed().as_millis();
println!("Time Taken: {:.2?} ms", elapsed_time);
Ok(map)
}进一步分析，在10亿位的PI中，所有6位数和7位数都可以找到，所有8位数找到了99995573个，找到率达99.99%；9位数找到率63.2%；10位数找到率是2%.
欢迎fork: https://github.com/metaphy/pai