mayda

mayda 是一个Rust库，用于压缩整数数组（支持所有原始整数类型）。其设计优先考虑解压缩速度和索引压缩数组的能力，而牺牲压缩比，其原则是使用压缩数组时运行时惩罚应尽可能小。

此包提供了一种压缩算法的三个变体。在2.6 GHz Intel Core i7-6700HQ处理器上，Uniform 类型可以每秒解压缩大约六十亿个 u32，或者24 GiB/s的解压缩整数（下面将具体说明）。Monotone 和 Unimodal 类型解压缩速度略低一半，但根据整数的分布，可以具有更好的压缩比。总体性能与任何语言中最快的（已知）库相当。

编译 mayda 需要 nightly 编译器和CPU对SSE2指令集的支持（任何2003年之后制造的Intel或AMD处理器）。编译器版本在 ./rust-toolchain 中进一步指定，以确保可重复性。基本方法在 Zukowski2006 和 Lemire2015 中描述。

文档

模块文档 提供了更多示例以及涉及算法的更详细描述。

使用方法

将此添加到您的 Cargo.toml

[dependencies]
mayda = "0.2"

并将此添加到您的crate根目录

extern crate mayda;

示例：编码和解码

Uniform 结构建议用于通用整数压缩。使用 Encode 特性来编码和解码数组。

extern crate mayda;

use mayda::{Uniform, Encode};

fn main() {
	// Integers in some interval of length 255, require one byte per integer
	let input: Vec<u32> = (0..128).map(|x| (x * 73) % 181 + 307).collect();

	let mut uniform = Uniform::new();
	uniform.encode(&input).unwrap();

	let i_bytes = std::mem::size_of_val(input.as_slice());
	let u_bytes = std::mem::size_of_val(uniform.storage());
	
	// 128 bytes for encoded entries, 12 bytes of overhead
	assert_eq!(i_bytes, 512);
	assert_eq!(u_bytes, 140);

	let output: Vec<u32> = uniform.decode();
	assert_eq!(input, output);
}

示例：索引

使用 Access 和 AccessInto 特性来索引压缩数组。这与 Index 类似，但返回一个向量而不是切片。

extern crate mayda;

use mayda::{Uniform, Encode, Access};

fn main() {
	// All primitive integer types supported
	let input: Vec<isize> = (-64..64).collect();

	let mut uniform = Uniform::new();
	uniform.encode(&input).unwrap();

	let val: isize = uniform.access(64);
	assert_eq!(val, 0);

	// Vector is returned to give ownership to the caller
	let range: Vec<isize> = uniform.access(..10);
	assert_eq!(range, (-64..-54).collect::<Vec<_>>());
}

性能

考虑以下三个向量

extern crate rand;

use rand::distributions::{IndependentSample, Range, Normal};

let mut rng = rand::thread_rng();
let length: usize = 1024;

// `input1` contains random integers
let mut input1: Vec<u32> = Vec::with_capacity(length);
let range = Range::new(0, 1024);
for _ in 0..length {
  input1.push(range.ind_sample(&mut rng));
}

// `input2` contains monotone increasing integers
let mut input2: Vec<u32> = input1.clone();
input2.sort();

// `input3` contains Gaussian distributed integers with outliers
let mut input3: Vec<u32> = Vec::with_capacity(length);
let gaussian = Normal::new(4086., 128.);
for _ in 0..length {
  input3.push(gaussian.ind_sample(&mut rng) as u32);
}
let index = Range::new(0, length);
let outliers = Range::new(0, std::u32::MAX);
for _ in 0..(length / 16) {
  input3[index.ind_sample(&mut rng)] = outliers.ind_sample(&mut rng);
}

以下是在2.6 GHz Intel Core i7-6700HQ处理器上对三个向量进行Uniform、Monotone和Unimodal类型性能的测试结果。使用decode_into的编码和解码速度以每秒数十亿个整数报告，索引最后一个条目所需时间以纳秒报告，压缩以每整数比特报告。原生编码和解码速度测量执行memcpy操作。香农熵是每整数比特的合理目标。

对于input1，香农熵为10.00。在通用情况下，Uniform在各方面都是首选。

对于input2，香农熵为10.00，但Monotone使用了额外的结构来提高压缩。

对于input3，香农熵为12.46，但由于存在异常值，压缩比较困难。Unimodal提供了最稳健的压缩。

许可证

mayda的许可证可以是以下之一

• Apache许可证版本2.0（LICENSE-APACHE 或 https://www.apache.org/licenses/LICENSE-2.0）
• MIT许可证（LICENSE-MIT 或 https://opensource.org/licenses/MIT）

由您选择。

贡献

除非您明确声明，否则根据Apache-2.0许可证定义的，您有意提交以包含在工作中的任何贡献，都应如上双许可，不附加任何额外条款或条件。

贡献者

Jeremy Mason - 原始作者 Francis Lalonde - 当前维护者