如何在处理数据流时高效地构建向量和该向量的索引?

11

我有一个结构体 Foo

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

我想处理一个数据流并将结果保存到Vec<Foo>中,并在字段Foo::v上为这个Vec<Foo>创建一个索引。

我想使用一个HashMap<&str, usize>来作为索引,其中键将是&Foo::v,值是Vec<Foo>中的位置,但我也可以接受其他建议。

我希望尽可能快地处理数据流,这需要不重复执行显而易见的操作。

例如,我希望:

  • 每次读取数据流时只分配一次String
  • 不要两次搜索索引,一次用于检查键是否存在,一次用于插入新键。
  • 不要通过使用RcRefCell增加运行时间。

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

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 借用了键,因此 s 的生命周期必须比 hash 更长
  2. 我想在第 (b) 行移动 s,但在第 (a) 行只有一个只读引用

那么,我应该如何实现这个简单的算法,而不需要额外调用 String::clone 或在调用 HashMap::insert 后调用 HashMap::get


这里有一个可测试的例子:playground - user4815162342
1
你如何处理碰撞?你想要所有的索引,只要第一个,只要最后一个,还是让它崩溃? - Matthieu M.
3个回答

10

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

这种情况下,程序员知道的有两个额外的信息,但编译器并不知道:

  1. 有一个额外的间接性——String 是在堆上分配的,因此移动指向该堆分配的指针并不是真正的问题。
  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方法中放置这段代码,而是希望从某个函数中返回它。这将会是一个问题,因为你很快就会遇到为什么不能在同一个结构体中存储值和对该值的引用?


老实说,有些代码风格不太适合 Rust 的限制。如果你遇到这种情况,你可以:

  • 决定 Rust 不适合你或你的问题。
  • 使用unsafe代码,最好经过充分测试并只公开安全的 API。
  • 研究替代表示方法。

例如,我可能会重写代码,让索引成为键的主要所有者:

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"));
}

另一种选择是,如何以惯用的方式创建一个查找表,该表使用项的字段作为键?所示,您可以将类型包装并存储在集合容器中:

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"));
}

通过使用RcRefCell不会增加运行时间。

在没有进行性能分析的情况下猜测性能特征从未是一个好主意。如果需要克隆或丢弃值时递增整数,我真的不相信会有明显的性能损失。如果问题需要同时使用索引和向量,则我会选择某种共享所有权。


1
我在想是否可以使用owning_ref库来获取一个指向安全移动的内存的指针?我尝试了显而易见的方法,v:OwningRef <String,str>替换v:String,但它仍然无法编译,几乎是相同的错误。我想知道我是否误解了owning_ref,或者这是借用检查器检测到的#2情况,即String更改的可能性。 - user4815162342
1
@user4815162342 是的,我感觉每次想使用 owning_ref 时,我都不是完全理解它。 - Shepmaster
可能是一个愚蠢的问题,但如果我想要有不同的索引(按名字、姓氏等),应该怎么办?使用Arc在不同的索引之间共享数据所有权,或者还有其他优雅的解决方案吗? - yageek
@yageek,RcArc是一种内存高效的技术。您还可以使用类似于字符串池或者内存池的东西。 - Shepmaster
什么是字符串内部器或者字符串池? - yageek
1
@yageek 字符串驻留; 区域 - Shepmaster

6
不使用 RcRefCell,可以避免增加运行时间。@Shepmaster已经展示了如何使用unsafe实现这一点,一旦完成后,建议您检查使用Rc实际上会花费多少。以下是使用Rc的完整版本:
use std::{
    collections::{hash_map::Entry, HashMap},
    rc::Rc,
};

#[derive(Debug)]
struct Foo {
    v: Rc<str>,
}

#[derive(Debug)]
struct Collection {
    vec: Vec<Foo>,
    index: HashMap<Rc<str>, usize>,
}

impl Foo {
    fn new(s: &str) -> Foo {
        Foo {
            v: s.into(),
        }
    }
}

impl Collection {
    fn new() -> Collection {
        Collection {
            vec: Vec::new(),
            index: HashMap::new(),
        }
    }

    fn insert(&mut self, foo: Foo) {
        match self.index.entry(foo.v.clone()) {
            Entry::Occupied(o) => panic!(
                "Duplicate entry for: {}, {:?} inserted before {:?}",
                foo.v,
                o.get(),
                foo
            ),
            Entry::Vacant(v) => v.insert(self.vec.len()),
        };
        self.vec.push(foo)
    }
}

fn main() {
    let mut collection = Collection::new();

    for foo in vec![Foo::new("Hello"), Foo::new("World"), Foo::new("Go!")] {
        collection.insert(foo)
    }

    println!("{:?}", collection);
}

@Shepmaster:就我个人而言,我希望能够使用Rc<str>。唯一真正缺失的是一个Rc::clone_from(&T) where T: ?Sized + Clone,不过如何以通用的方式猜测所需的目标大小似乎有些复杂 :x 另一种方法是直接像[u8]一样操作str,但这也不太容易。 - Matthieu M.
@Shepmaster:是的,这就是我所说的“泛化”clone_from的困难之处。对于非Sized类型,您需要某种特定的trait,以便为您提供(1)所需内存缓冲区的大小和(2)将/克隆到该缓冲区的方法。 - Matthieu M.

1
错误是:

error: `s` does not live long enough
  --> <anon>:27:5
   |
16 |         let idx: usize = match hash.entry(&s) { //a
   |                                            - borrow occurs here
...
27 |     }
   |     ^ `s` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

注意:答案在结尾处。

s 必须hash 存活的时间长,因为你正在使用 &s 作为 HashMap 中的键。当 s 被丢弃时,这个引用将变得无效。但是,正如注意中所说,hash 将在 s 之后被丢弃。一个快速的解决方法是交换它们的声明顺序:

let s = "aaa".to_string();
let mut hash = HashMap::<&str, usize>::new();

但现在你又遇到了另一个问题:
error[E0505]: cannot move out of `s` because it is borrowed
  --> <anon>:22:33
   |
17 |         let idx: usize = match hash.entry(&s) { //a
   |                                            - borrow of `s` occurs here
...
22 |                 l.push(Foo { v: s }); //b
   |                                 ^ move out of `s` occurs here

这个更明显。 sEntry 借用,它将一直存在于块的末尾。克隆 s 将解决这个问题:

l.push(Foo { v: s.clone() }); //b

我只想分配一次 s,而不是克隆它

但是 Foo.v 的类型是 String,这意味着它将拥有自己的 str 副本。只是这种类型意味着你必须复制 s

你可以用 &str 替换它,这将允许它保持作为对 s 的引用:

struct Foo<'a> {
    v: &'a str,
}

pub fn main() {
    // s now lives longer than l
    let s = "aaa".to_string();
    let mut l = Vec::<Foo>::new();
    {
        let mut hash = HashMap::<&str, usize>::new();

        let idx: usize = match hash.entry(&s) {
            Occupied(ent) => {
                *ent.get()
            }
            Vacant(ent) => {
                l.push(Foo { v: &s });
                ent.insert(l.len() - 1);
                l.len() - 1
            }
        };
    }
}

请注意,以前我不得不将s的声明移动到hash之前,以便它能够生存。但是现在,l持有对s的引用,因此必须更早地声明它,以便它比l更长寿。

实际上,我在循环中执行此操作,并且实际代码会动态生成“String”,因此您建议创建一个用于“String”的容器,但这是不可能的,因为我无法同时扩展容器并引用字符串。 - user1244932
我不完全理解你的问题。你能否补充一下代码示例,以便更清楚地说明你想要做什么? - Peter Hall
我不明白为什么借用检查器不允许这段代码编译。即使向向量推送了不同的字符串,借用检查器仍然会抱怨 - user4815162342
2
如果@user1244932认为这个方法对你不起作用是因为你的真实代码使用了循环,那么在你的代码示例中包含循环可能会有所帮助。 - Peter Hall
@PeterHall 我在代码中添加了注释,以显示循环的位置和创建顺序对我很重要。我创建了 l 来保存生成的 s,反转顺序是不可能的,就像先创造鸡再创造蛋一样。 - user1244932
显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接