在 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()函数没有返回正确的答案。

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

还有其他方法可以String在 a 中搜索 a 吗Vec<String>？或者我的代码有错误？

谢谢

Answer 1

首先，有几个问题：在使用二分搜索之前必须对数据进行排序。二分搜索是一种快速搜索算法（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,
    }
}

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