4 个版本

0.1.3 2020 年 6 月 12 日
0.1.2 2020 年 6 月 3 日
0.1.1 2020 年 6 月 3 日
0.1.0 2020 年 6 月 1 日

Rust 模式 中排名 1094

每月下载量 23
bset 中使用

MIT/Apache

86KB
1.5K SLoC

@NikolaiVazquez 提供的 Rust 的有效字节集!

主角是 ByteSet:一个无分配的有序集合。它是在各种场景下替代 HashSet<u8>BTreeSet<u8> 等类型的 更快 替代品。在"实现" 中了解其内部工作原理。

如果您觉得这个库很有用,请考虑在 GitHub 上赞助我

目录

  1. 用法
  2. 示例
    1. ByteSet 类型
      1. 插入
      2. 扩展
      3. 移除
      4. 迭代
      5. 包含
      6. 子集
      7. 最小和最大值
    2. byte_set!
  3. 实现
  4. 基准测试
  5. 生态系统集成
    1. rand
    2. serde
  6. 许可

用法

此库可在 crates.io 上找到,并且可以通过将以下内容添加到您的项目的 Cargo.toml 中使用。

[dependencies]
byte_set = "0.1.3"

要导入 byte_set! 宏,请将其添加到您的crate根目录(main.rslib.rs)。

use byte_set::byte_set;

如果您不是使用 Rust 2018 版本,则必须以不同的方式导入。

#[macro_use]
extern crate byte_set;

示例

ByteSet 类型

首先,让我们导入 ByteSet

use byte_set::ByteSet;

以下是创建空集合的方法

let bytes = ByteSet::new();

同样容易创建一个包含所有字节数据(0到255)的集合

let bytes = ByteSet::full();

好的,让我们看看我们可以用这个做什么。请注意,这并不是唯一的功能。请参阅ByteSet以获取完整的功能列表。

插入

使用insert通过修改ByteSet来包含单个字节

let mut bytes = ByteSet::new();
bytes.insert(255);

使用inserting作为不可变替代方案,通过值传递调用ByteSet

let bytes = ByteSet::new().inserting(255);

使用insert_all通过修改ByteSet来包含另一个ByteSet的所有字节

let mut alphabet = ByteSet::ASCII_UPPERCASE;
alphabet.insert_all(ByteSet::ASCII_LOWERCASE);

assert_eq!(alphabet, ByteSet::ASCII_ALPHABETIC);

使用inserting_all作为不可变替代方案,通过值传递调用ByteSet

let alphabet = ByteSet::ASCII_UPPERCASE.inserting_all(ByteSet::ASCII_LOWERCASE);

assert_eq!(alphabet, ByteSet::ASCII_ALPHABETIC);

扩展

而不是在循环中调用insert,可以使用extend简化从迭代器插入的过程

fn take_string(bytes: &mut ByteSet, s: &str) {
    bytes.extend(s.as_bytes());
}

由于它遍历整个输入,因此在插入另一个ByteSet时,使用insert_all而不是extend会更有效率。

移除

使用remove通过修改集合来排除单个字节

let mut bytes = ByteSet::full();
bytes.remove(255);

使用removing作为不可变替代方案,通过值传递调用ByteSet

let bytes = ByteSet::full().removing(255);

使用remove_all通过修改集合来排除另一个ByteSet的所有字节

let mut alphabet = ByteSet::ASCII_ALPHANUMERIC;
alphabet.remove_all(ByteSet::ASCII_DIGIT);

assert_eq!(alphabet, ByteSet::ASCII_ALPHABETIC);

使用removing_all作为不可变替代方案,通过值传递调用ByteSet

let alphabet = ByteSet::ASCII_ALPHANUMERIC.removing_all(ByteSet::ASCII_DIGIT);

assert_eq!(alphabet, ByteSet::ASCII_ALPHABETIC);

迭代

迭代可以通过简单的for循环完成,并且按顺序从最小到最大进行

fn small_to_big(bytes: ByteSet) {
    for byte in bytes {
        do_work(byte);
    }
}

反向迭代稍微有点冗长,并且按顺序从最大到最小进行

fn big_to_small(bytes: ByteSet) {
    for byte in bytes.into_iter().rev() {
        do_work(byte);
    }
}

包含

如果不能检查集合中是否有特定项,那么这就不算是一个集合。

使用contains来检查单个字节

fn has_null(bytes: &ByteSet) -> bool {
    bytes.contains(0)
}

使用contains_any来检查另一个ByteSet中是否有任何匹配项

fn intersects(a: &ByteSet, b: &ByteSet) -> bool {
    a.contains_any(b)
}

子集

使用is_subset来检查一个ByteSet中的所有字节是否都包含在另一个中

fn test(a: &ByteSet, b: &ByteSet) {
    assert!(a.is_subset(b));

    // Always passes because every set is a subset of itself.
    assert!(a.is_subset(a));
}

使用 is_strict_subset 来检查 is_subset 集合是否不相同

fn test(a: &ByteSet, b: &ByteSet) {
    assert!(a.is_strict_subset(b));

    // `a` is equal to itself.
    assert!(!a.is_strict_subset(a));
}

为了完整性,还有 is_supersetis_strict_superset,它们通过交换 ab 来调用这些函数。

最小和最大值

使用 first 获取最小的字节,并使用 last 获取最大的字节

fn sanity_check(bytes: &ByteSet) {
    if let (Some(first), Some(last)) = (bytes.first(), bytes.last()) {
        assert!(first <= last);
    } else {
        // `bytes` is empty.
    }
}

这些是在迭代时返回的第一个和最后一个字节。

byte_set!

byte_set! 允许您使用与 vec! 或数组表达式相同的语法来创建 ByteSet

let bytes = byte_set![1, 2, 3, b'x', b'y', b'z'];

它甚至可以在 const 表达式中在编译时工作

const WHOA: ByteSet = byte_set![b'w', b'h', b'o', b'a'];

static ABC: ByteSet = byte_set![b'a', b'c', b'c'];

实现

ByteSet 实现为一个 256 位的掩码,其中每个位对应一个字节值。掩码中的第一个(最低有效)位表示集合中的第一个字节(0)。同样,最后一个(最高有效)位表示最后一个字节(255)。

给定以下 ByteSet

let bytes = byte_set![0, 1, 4, 5, 244];

bytes 的内存表示看起来像

 Byte: 0 1 2 3 4 5 6 7 ... 253 244 255
Value: 1 1 0 0 1 1 0 0 ...  0   1   0

这个位掩码由 [u64; 4][u32; 8] 组成,具体取决于目标 CPU(见 #3)。因为这将只有 32 字节,所以 ByteSet 实现了 Copy

基准测试

我很快就会上传从我机器上运行的结果。

在此期间,您可以通过运行以下命令来对这个库进行基准测试:

cargo bench

默认情况下,这将基准测试 ByteSet 以及各种其他类型以比较性能。请注意,这将花费很长时间(大约1小时30分钟)。

通过运行以下命令来仅基准测试 ByteSet

cargo bench ByteSet

这需要大约15分钟,所以您可以在这段时间里喝杯咖啡。

通过运行以下命令来基准测试特定的 ByteSet 操作

cargo bench $operation/ByteSet

请参阅 /benches/benchmarks 以获取可用于 $operation 的字符串。

请注意,cargo bench 接受正则表达式,所以 Contains (Random) 不会正常工作,因为括号被视为捕获组。要匹配括号,请将其转义:Contains \(Random\)

生态系统集成

此库扩展了一些流行crate的功能。

rand

在您的Cargo.toml中使用rand(或rand_core)功能来启用随机ByteSet生成

[dependencies.byte_set]
version = "0.1.3"
features = ["rand"]

这使得以下成为可能

let bytes = rand::random::<ByteSet>();

// Same as above.
let bytes = ByteSet::rand(rand::thread_rng());

// Handle failure instead of panicking.
match ByteSet::try_rand(rand::rngs::OsRng) {
    Ok(bytes)  => // ...
    Err(error) => // ...
}

serde

在您的Cargo.toml中使用serde功能来为ByteSet启用SerializeDeserialize

[dependencies.byte_set]
version = "0.1.3"
features = ["serde"]

这使得以下成为可能

use serde::{Serialize, Deserialize};

#[derive(Serialize, Deserialize)]
struct MyValue {
    bytes: ByteSet
}

ByteSet可以被序列化为一个u8序列,也可以从&[u8]或一个u8序列反序列化。

关于使用serde的更多信息,请访问serde.rs

许可

该项目可以选择以下任一许可证发布

任您选择。

依赖项

~0–290KB