我有一个结构 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
}
存在多个问题:
-
hash.entry
借 key 所以s
必须有比hash
更长的生命周期 - 我想搬家
s
在 (b) 行,而我在 (a) 行有一个只读引用
那么我应该如何在不额外调用 String::clone
的情况下实现这个简单的算法?或调用HashMap::get
打电话后 HashMap::insert
?
最佳答案
一般,您试图完成的事情是不安全的,Rust 会正确地阻止您做一些您不应该做的事情。举一个简单的例子,考虑一个 Vec<u8>
.如果 vector 有一个项目且容量为 1,则向 vector 添加另一个值将导致重新分配和复制 vector 中的所有值,从而使对 vector 的任何引用无效。这会导致索引中的所有键都指向任意内存地址,从而导致不安全行为。编译器会阻止这种情况。
在这种情况下,有两条编译器不知道但程序员不知道的额外信息:
- 还有一个额外的间接寻址 —
String
是堆分配的,因此将指针 move 到该堆分配并不是真正的问题。 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
orRefCell
在不执行分析的情况下猜测性能特征绝不是一个好主意。老实说,我不认为在克隆或删除值时增加整数会导致明显的性能损失。如果问题同时需要索引和向量,那么我会寻求某种共享所有权。
关于rust - 如何在处理数据流时有效地构建向量和该向量的索引?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43460483/