rust - 在 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在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,
    }
}

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