在 rust 中将字符串搜索到 Vec<String>

Question

我正在编写一个解释语言的程序。

我需要在 Vec.

中搜索字符串（编译时未知）

fn get_name_index(name: &String, array: &Vec<String>) -> usize {
    match array.binary_search(name) {
        Ok(index) => index,
        Err(_) => {
            eprintln!("Error : variable {:?} not found in name array", name);
            std::process::exit(1)
        }
    }
}

这种情况在执行过程中多次发生，但目前 array.binary_search() 函数没有 return 正确答案。

我搜索了错误，但我的数组是它应该的（打印每个元素，或者用 gdb 检查：相同），错误仍然存在。

有没有其他方法可以在 Vec<String> 中搜索 String？还是我的代码有错误？

谢谢

Answer 1

正如mcarton所说，向量需要先排序才能进行二分查找。这是一个例子：

let mut v = vec![String::from("_res"), String::from("b"), String::from("a")];
println!("{:?}", &v);

v.sort_unstable();
println!("{:?}", &v);

我用你的代码试过了，它在第二个位置找到了 "a"。没有调用 sort_unstable() 它找不到 "a".

Answer 2

首先，几个问题：在使用二进制搜索之前必须对数据进行排序。二分搜索是一种快速搜索算法（O(log n)，或按容器大小的对数缩放），比线性搜索（O(n)，或按容器大小线性缩放）快得多).但是，与对容器进行排序的开销 (O(n log n)).

相比，二分查找带来的任何速度提升都相形见绌。

单一搜索

因此，最佳方法取决于您搜索容器的频率。如果你只打算检查几次，你应该使用线性搜索，如下：

fn get_name_index(name: &String, array: &Vec<String>) -> Option<usize> {
    array.iter().position(|&&x| x == name)
}

重复搜索

如果您要重复调用 get_name_index，您应该使用二进制搜索（或者可能更好，见下文）：

// Sort the array before using
array.sort_unstable();

// Repeatedly call this function
fn get_name_index(name: &String, array: &Vec<String>) -> Option<usize> {
    match array.binary_search(name) {
        Ok(index) => Some(index),
        Err(_)    => None,
    }
}

但是，对于某些情况，这可能不是最佳选择。一些注意事项：对于某些数据集，HashSet 可能更快（O(1) 复杂度最高）。然而，这有点误导，因为名称的所有字符都必须在每次比较时处理 HashSet，而通常只有几个字符必须比较以确定是否向左跳转或向右跳转以进行二分查找。对于高度统一且末尾有几个字符不同的数据，HashSet 可能更好，否则，我通常建议在向量上使用 binary_search。

在 rust 中将字符串搜索到 Vec<String>

Searching a String into Vec<String> in rust

binary-search

rust

单一搜索

重复搜索