ironstorm_lookup

概述

此库包含由 ironstorm 项目使用的内部数据结构

要了解更多关于 ironstorm_lookup 的信息，请阅读此 README.md 和 Crate 文档

由于使用了不稳定特性，只能与 rust 的 nightly 版本编译。

设计目标

• 闪电般的自动完成/快速输入查找 (~200 微秒/查找！)
• 每个条目可搜索的文本不多，例如：地点的街道名称或电影的名称
• 可能的候选人数众多（多个千兆字节）
• 可以推荐，但不必将整个数据集放入物理内存
• LookupTable 应使用虚拟内存和 OS 级优化来处理更大的数据集
• 全文搜索功能
• 针对几乎不变的数据集进行优化，例如：一个国家的所有街道
• 如果不是绝对必要，则不使用多线程 => 用内存换取查找速度！
• 针对返回少量匹配项进行优化，例如：在 200 万部电影中找到包含 'hero' 的前 10 部
• 只需要一维粗略排序，例如：奇幻书籍应返回在科幻书籍之前
• 基于懒惰流/迭代器的查找实现

接受的缺点

• 创建用于多个千兆字节数据的 LookupTable 可能需要几分钟
• LookupTable 无法修改，只能重新创建
• 无法进行细粒度排序：例如：按字典顺序排序

基本用法

1. 为要搜索的数据创建一个自定义类型，例如：一个 Movie 结构体
2. 为您的自定义类型实现 Lookup 特征。
3. 创建一个 Iterator，该迭代器将遍历您希望放入 LookupTable 的所有元素
4. 通过调用 LookupTable::from_iter(myMoviesIterator) 创建一个新的 LookupTable
5. 调用 myMoviesLookupTable.find("hero") 获取所有匹配元素的懒 'Iterator'

示例

让我们构建一个 LookupTable 来通过名称查找餐馆。

use std::iter::FromIterator;
use ironstorm_lookup::{LookupTable, Lookup, Bucket};

// 1. Create a custom struct representing a restaurant
struct Restaurant<'a> {
    name: &'a str,
    cuisine: &'a str
}

// 2. Implement the `Lookup` trait for `Restaurant` references
impl <'a> Lookup for &'a Restaurant<'a> {
    // Make the restaurant name searchable
    fn searchable_text(&self) -> String {
        self.name.to_string()
    }
    // Decide, based on cuisine, to which `Bucket` a restaurant belongs.
    // `Bucket` is just a type alias for an unsigned integer aka usize.
    // Matches in lower buckets will be returned before matches in higher buckets.
    fn bucket(&self) -> Bucket {
        match self.cuisine {
            "italian"   => 0,
            "german"    => 0,
            "chinese"   => 1,
            _           => 5
        }
    }
}

// 3. Create some restaurants and the according iterator
let restaurants = vec![
    Restaurant{name:"India Man", cuisine:"indian"},
    Restaurant{name:"Ami Guy", cuisine:"american"},
    Restaurant{name:"Italiano Pizza", cuisine:"italian"},
    Restaurant{name:"Sushi House", cuisine:"chinese"},
    Restaurant{name:"Brezel Hut", cuisine:"german"}
];
let iter = restaurants.iter();

// 4. Create the `LookupTable`
let lookup_table = ironstorm_lookup::LookupTable::from_iter(iter);

// 5. Find restaurants containing `i`
let mut result_iter = lookup_table.find("i");

// two times 'Italiano pizza', because it's in the lowest bucket
// two times because it has two lower case `i` in the name
assert_eq!(result_iter.next().unwrap().name, "Italiano Pizza");
assert_eq!(result_iter.next().unwrap().name, "Italiano Pizza");

// 'Sushi House', because it's in the second lowest bucket
assert_eq!(result_iter.next().unwrap().name, "Sushi House");

// 'Ami Guy' or ' India Man'
// They are in the same bucket and there is no order within the same bucket
let indian_or_american_1 = result_iter.next().unwrap().name;
assert!(indian_or_american_1=="India Man" || indian_or_american_1=="Ami Guy");

// The other one of 'Ami Guy' or ' India Man'
let indian_or_american_2 = result_iter.next().unwrap().name;
assert!(indian_or_american_2=="India Man" || indian_or_american_2=="Ami Guy");
assert!(indian_or_american_1 != indian_or_american_2);

// No more matches
// "Brezel Hut" doesn't contain an "i" and was not part of the result.
assert!(result_iter.next().is_none());

许可证

根据您的选择许可

• Apache License，版本 2.0 https://apache.ac.cn/licenses/LICENSE2.0
• MIT 许可证 http://opensource.org/licenses/MIT

可选

贡献

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