草图算法

Swift 中的草图算法集合。

概述

在 Package.swift 中将 Sketching 添加到 dependencies

dependencies: [
    .package(url: "https://github.com/pNre/Sketching", .branch("master")),
]

然后在使用该包的目标中引用它

.target(
    name: "CoolExecutable",
    dependencies: ["Sketching"])

将 Sketching 作为依赖项添加到你的项目的 Cartfile 中

github "pNre/Sketching"

一种类似数组的结构，经过优化可有效地存储位。

//  create a bit set of 100 bits
var s = BitSet(bitWidth: 100)

//  set bit 0 and 2
s[0] = true
s[2] = true

(lldb) po s
BitSet (width=100, value=101)

//  bitwise operators
let conjunction = s1 & s2
let disjunction = s1 | s2
let negation = ~s1

构建一个 MinHash 并插入一些元素

var a = MinHash<FNV1AHashing>(hashCount: 64)
a.insert("a".utf8)
a.insert("b".utf8)
a.insert("c".utf8)

var b = MinHash<FNV1AHashing>(hashCount: 64)
b.insert("a".utf8)
b.insert("b".utf8)

比较两个 MinHash 结构的相似性

(lldb) po a.jaccard(b)
0.734375

形成两个 MinHash 之间的并集

let c = a.union(b)

(lldb) po a.jaccard(c)
1.0

var ll = HyperLogLog<FNV1AHashing>()
ll.insert("abc".utf8)
ll.insert("def".utf8)
ll.insert("abc".utf8)

(lldb) po ll.cardinality()
2.007853430022625

使用特定大小和哈希函数数量初始化一个 BloomFilter

var f = BloomFilter<FNV1AHashing>(bitWidth: 128, hashCount: 16)

使用预期的项目数量和误报概率初始化一个 BloomFilter

var f = BloomFilter<FNV1AHashing>(expectedCardinality: 10, probabilityOfFalsePositives: 0.001)

插入一些元素

f.insert("abc".utf8)
f.insert("def".utf8)

测试包含性

(lldb) po f.contains("gh".utf8)
false