mayda

mayda是一个用于压缩整数数组的Rust库（支持所有原始整数类型）。设计上更注重解压缩速度和索引压缩数组的能力，而不是压缩比，基于压缩数组的使用在运行时应该尽可能小的原则。

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

编译mayda需要一个nightly编译器和支持SSE2指令集的CPU（任何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 License，版本2.0，(LICENSE-APACHE 或 http://apache.ac.cn/licenses/LICENSE-2.0)
• MIT许可证 (LICENSE-MIT 或 https://opensource.org/licenses/MIT)

自由选择。

贡献

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

贡献者

Francis Lalonde

lib.rs:

此crate的目的是将mayda_macros的encode!、decode!、encode_simd!、decode_simd!和encode_util!语法扩展生成的函数归入一个单独的编译单元。更详细的文档可以在mayda_macros crate中找到。