13次发布
| 0.0.13 | 2023年4月30日 |
|---|---|
| 0.0.12 | 2023年4月30日 |
在数据结构中排名383
每月下载204次
50KB
1K SLoC
这是类型为 usize 和固定容量的映射的堆上实现的一个替代品。由于它一次性为所有键分配内存，因此比标准的 HashMap 快得多，因为 get() 的成本是 O(1)。显然，由于这种设计，iter() 的成本会增加，因为迭代器必须跳过空键。然而，有一个辅助函数 next_key()，它返回映射中的下一个可用键。建议使用它以确保键的顺序，这将为迭代器中的 next() 保证 O(1) 成本。
如果将 usize 键顺序放置，那么我们的唯一真正竞争对手是 std::vec::Vec。我们也打败了它，请参阅下面的基准测试结果。
首先，将此添加到 Cargo.toml
[dependencies]
emap = "0.0.11"
然后，像使用标准哈希映射一样使用它...嗯，几乎是这样
use emap::Map;
let mut m : Map<&str> = Map::with_capacity_init(100); // allocation on heap
m.insert(m.next_key(), "foo");
m.insert(m.next_key(), "bar");
assert_eq!(2, m.len());
如果向映射中添加超过100个键，它将恐慌。映射不会像 Vec 那样自动增加其大小（这是我们更快的一个原因）。
阅读API文档。结构体 emap::Map 被设计为尽可能类似于 std::collections::HashMap。
基准测试
以下是一个简单基准测试的总结，其中我们比较了emap::Map与Vec，并改变了它们的总容量CAP（水平轴）。我们对它们都应用了相同的交互（benchmark.rs）并测量了它们的性能。在下表中，大于1.0的数字表示Map相对于Vec的性能提升，而小于1.0的数字表示性能下降。
| 4 | 16 | 256 | 4096 | |
|---|---|---|---|---|
i ∈0..CAP {M.插入(i, &"大家好")} |
1.17 | 2.89 | 1.26 | 1.27 |
i ∈0..CAP {M.插入(i, &"Hello, world!");s ∈ M.值() {总和+=s.长度()}} |
1.05 | 0.73 | 0.65 | 0.51 |
i ∈0..CAP {M.插入(i, &42);s ∈ M.into_values() {总和+=s}} |
1.05 | 0.91 | 0.61 | 0.68 |
i ∈0..CAP {M.插入(i, &42);s ∈ M.键() {总和+=s}} |
0.98 | 0.69 | 0.34 | 0.34 |
i ∈0..CAP {M.插入(i, &42);s ∈ M.值() {总和+=s}} |
1.07 | 0.81 | 0.51 | 0.51 |
i ∈0..CAP {M.插入(i, &42)};M.清除();M.长度(); |
1.20 | 2.72 | 5.17 | 9.30 |
i ∈0..CAP {M.插入(i, &42)};i ∈CAP-1..0 {M.删除(&i)} |
1.23 | 2.19 | 1.34 | 1.03 |
实验于2023年4月30日进行。重复循环次数为10000次。整个基准测试耗时486秒。
如何贡献
首先，安装Rust，然后
$ cargo test -vv
如果一切顺利，创建仓库分支，进行修改，向我们发送pull request。我们将审查您的更改，并在不违反我们的质量标准的情况下，尽快将它们应用到master分支上。为了避免失望，在发送pull request之前，请再次运行cargo test。同时，运行cargo fmt和cargo clippy。
另外，在您开始修改之前，运行基准测试
$ rustup run nightly cargo bench
然后，在您做出更改后，再次运行。比较结果。如果您的更改降低了性能，在提交pull request之前请三思。
依赖
~170KB