rust - 如何在处理数据流时有效地构建向量和该向量的索引？

Question

我有一个结构 Foo :

struct Foo {
    v: String,
    // Other data not important for the question
}

我想处理数据流并将结果保存到 Vec<Foo>并为此 Vec<Foo> 创建索引在球场上Foo::v .

我想使用 HashMap<&str, usize>对于索引，其中的键将是 &Foo::v值是 Vec<Foo> 中的位置，但我愿意接受其他建议。

我想尽可能快地处理数据流，这要求不要重复做明显的事情。

例如，我想:

• 分配一个String每个数据流读取仅一次
• 不搜索索引两次，一次检查键不存在，一次插入新键。
• 使用 Rc 不会增加运行时间或 RefCell .

借用检查器不允许此代码:

let mut l = Vec::<Foo>::new();
{
    let mut hash = HashMap::<&str, usize>::new();
    //here is loop in real code, like: 
    //let mut s: String; 
    //while get_s(&mut s) {
    let s = "aaa".to_string();
    let idx: usize = match hash.entry(&s) { //a
        Occupied(ent) => {
            *ent.get()
        }
        Vacant(ent) => {
            l.push(Foo { v: s }); //b
            ent.insert(l.len() - 1);
            l.len() - 1
        }
    };
    // do something with idx
}

存在多个问题:

1. hash.entry借 key 所以s必须有比 hash 更长的生命周期
2. 我想搬家s在 (b) 行，而我在 (a) 行有一个只读引用

那么我应该如何在不额外调用 String::clone 的情况下实现这个简单的算法？或调用HashMap::get打电话后 HashMap::insert ？

Answer 1

一般，您试图完成的事情是不安全的，Rust 会正确地阻止您做一些您不应该做的事情。举一个简单的例子，考虑一个 Vec<u8> .如果 vector 有一个项目且容量为 1，则向 vector 添加另一个值将导致重新分配和复制 vector 中的所有值，从而使对 vector 的任何引用无效。这会导致索引中的所有键都指向任意内存地址，从而导致不安全行为。编译器会阻止这种情况。

在这种情况下，有两条编译器不知道但程序员不知道的额外信息:

1. 还有一个额外的间接寻址 — String是堆分配的，因此将指针 move 到该堆分配并不是真正的问题。
2. String将永远改变。如果是，那么它可能会重新分配，使引用的地址无效。使用 Box<[str]>而不是 String将是一种通过类型系统强制执行此操作的方法。

在这种情况下，可以使用unsafe。代码，只要您正确记录为什么它不是不安全的。

use std::collections::HashMap;

#[derive(Debug)]
struct Player {
    name: String,
}

fn main() {
    let names = ["alice", "bob", "clarice", "danny", "eustice", "frank"];

    let mut players = Vec::new();
    let mut index = HashMap::new();

    for &name in &names {
        let player = Player { name: name.into() };
        let idx = players.len();

        // I copied this code from Stack Overflow without reading the prose
        // that describes why this unsafe block is actually safe
        let stable_name: &str = unsafe { &*(player.name.as_str() as *const str) };

        players.push(player);
        index.insert(idx, stable_name);
    }

    for (k, v) in &index {
        println!("{:?} -> {:?}", k, v);
    }

    for v in &players {
        println!("{:?}", v);
    }
}

但是，我的猜测是您不想在您的 main 中使用此代码方法，但想从某个函数返回它。这将是一个问题，因为您很快就会遇到 Why can't I store a value and a reference to that value in the same struct?。 .

---

老实说，有些代码风格不符合 Rust 的限制。如果您遇到这些情况，您可以:

• 确定 Rust 不适合您或您的问题。
• 使用unsafe代码，最好经过全面测试并且只公开安全的 API。
• 调查替代表示。

例如，我可能会重写代码以使索引成为 key 的主要所有者:

use std::collections::BTreeMap;

#[derive(Debug)]
struct Player<'a> {
    name: &'a str,
    data: &'a PlayerData,
}

#[derive(Debug)]
struct PlayerData {
    hit_points: u8,
}

#[derive(Debug)]
struct Players(BTreeMap<String, PlayerData>);

impl Players {
    fn new<I>(iter: I) -> Self
    where
        I: IntoIterator,
        I::Item: Into<String>,
    {
        let players = iter
            .into_iter()
            .map(|name| (name.into(), PlayerData { hit_points: 100 }))
            .collect();
        Players(players)
    }

    fn get<'a>(&'a self, name: &'a str) -> Option<Player<'a>> {
        self.0.get(name).map(|data| Player { name, data })
    }
}

fn main() {
    let names = ["alice", "bob", "clarice", "danny", "eustice", "frank"];

    let players = Players::new(names.iter().copied());

    for (k, v) in &players.0 {
        println!("{:?} -> {:?}", k, v);
    }

    println!("{:?}", players.get("eustice"));
}

或者，如 What's the idiomatic way to make a lookup table which uses field of the item as the key? 所示，您可以包装您的类型并将其存储在一个 set 容器中:

use std::collections::BTreeSet;

#[derive(Debug, PartialEq, Eq)]
struct Player {
    name: String,
    hit_points: u8,
}

#[derive(Debug, Eq)]
struct PlayerByName(Player);

impl PlayerByName {
    fn key(&self) -> &str {
        &self.0.name
    }
}

impl PartialOrd for PlayerByName {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for PlayerByName {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.key().cmp(&other.key())
    }
}

impl PartialEq for PlayerByName {
    fn eq(&self, other: &Self) -> bool {
        self.key() == other.key()
    }
}

impl std::borrow::Borrow<str> for PlayerByName {
    fn borrow(&self) -> &str {
        self.key()
    }
}

#[derive(Debug)]
struct Players(BTreeSet<PlayerByName>);

impl Players {
    fn new<I>(iter: I) -> Self
    where
        I: IntoIterator,
        I::Item: Into<String>,
    {
        let players = iter
            .into_iter()
            .map(|name| {
                PlayerByName(Player {
                    name: name.into(),
                    hit_points: 100,
                })
            })
            .collect();
        Players(players)
    }

    fn get(&self, name: &str) -> Option<&Player> {
        self.0.get(name).map(|pbn| &pbn.0)
    }
}

fn main() {
    let names = ["alice", "bob", "clarice", "danny", "eustice", "frank"];

    let players = Players::new(names.iter().copied());

    for player in &players.0 {
        println!("{:?}", player.0);
    }

    println!("{:?}", players.get("eustice"));
}

not increase the run time by using Rc or RefCell

在不执行分析的情况下猜测性能特征绝不是一个好主意。老实说，我不认为在克隆或删除值时增加整数会导致明显的性能损失。如果问题同时需要索引和向量，那么我会寻求某种共享所有权。