今天一个统计任务,需要从一个巨大的列表(几亿条)
中找出属于另一个小点的列表的记录,小表有3千多条。
使用bloomfilter 算法简化,bloomfilter 的介绍在谷歌中文blog上有一篇。 简单的说就是用一个位串做筛子,用一组hash
函数作映射。 先用小表创建这个位串过滤器,形象的说就是在纸带上打孔。 全都打好后,用这个筛子来过滤大表,大表中的元素经过hash函数,如果能全
部通过纸带上的孔,就算通过,否则就过滤掉。
bloomfilter 的一个特点是:过滤有误差,误差通过过滤函数以及位串的长度两个变量可以计算出来。
Haskell hackage 上有一个 bloomfilter 的库,很易用。
安装: cabal install bloomfilter
http://hackage.haskell.org/package/bloomfilter
Data.BloomFilter
* Data.BloomFilter.Easy
* Data.BloomFilter.Hash
使用的时候, 先通过 suggestSizing 函数获得推荐的 hash函数个数以及位串长度:
suggestSizing Source
:: Int expected maximum capacity
-> Double desired false positive rate (0 < e < 1)
-> (Int, Int)
然后创建一个过滤器:
fromListB Source
::
=> a -> [Hash] family of hash functions to use
-> Int number of bits in filter
-> [a] values to populate with
-> Bloom a
例如: filt = fromListB (cheapHashes 3) 1024 ["foo", "bar", "quux"]
使用过滤器过滤值:
elemB :: a -> Bloom a -> Bool
分享到:
相关推荐
haskell中文入门资料,代码齐全,入门简单
HaskellR, 在Haskell中,R的全部威力 HaskellR项目 网站:https://tweag.github.io/HaskellR邮件列表:GoogleHaskellR项目提供了一种使用Haskell或者 R 代码高效地处理数据的环境。 HaskellR允许Ha
haskell中文教程
英文 haskell 的必读书 Haskell是一种纯函数式编程语言,它的命名源自美国数学家Haskell Brooks Curry,他在数学逻辑方面上的工作使得函数式编程...本语言的特式是利用很简单的叙述就可以完成链表、矩阵等数据结构。
HyperHaskell 强烈的推荐的Haskell图形化解释器
这是Haskell编程的上一页,我们正在处理中,将那里的所有书籍都转换为新页面。 请每天检查此页面!!!
这种浓缩的代码和语法参考以一种组织良好的格式呈现了基本的haskell语法,可以用作快速而方便的参考,包括云计算和数据分析的应用程序。本书介绍了haskell的功能编程特性,以及强大的静态类型、懒惰的评估、广泛的...
Haskell-Data-Analysis-Cookbook, Haskell数据分析 cookbook的附带源代码 Haskell-Data-Analysis-Cookbook这是 Haskell数据分析 cookbook的附带源代码。最新的源代码可以在GitHub上获得: ...
haskell语言教材 Haskell(发音为 /ˈhæskəl/)是一种纯函数式编程语言,它的命名源自美国数学家哈斯凯尔·加里,他在数学逻辑方面上的工作使得函数式编程语言有了广泛的基础。Haskell语言是1990年在编程语言...
在内部,数据存储在未装箱向量的集合中,底层存储和类型信息从最终用户那里抽象出来,目的是创建一个 DataFrame,它可以使用任意 CSV 文件,并让库处理列对齐和缺失值,而无需额外的方向。 安装 $ cabal configure ...
language-c-inline, 在Haskell中,内联C & Objective C 内内嵌C & objective-c这个库使用模板Haskell和 language-c-quote,用于C 类似语言的引用库,用于在Haskell中提供内联C 和 objective-c 。 在编译Haskell程序...
stack官方网站: ...首先: 在终端下键入下面这条命令: ... 出现以下情况: 在终端下输入命令: sudo apt install curl ...stack new my-project ...stack build //作用:在此目录/配置中生成包 stack exec my-project-exe
Haskell的课程PPT
Haskell数据结构在Haskell中练习数据结构
Yi 是用 Haskell 开发的文本编辑器,其目的是提供一个灵活、强大的编辑器核心脚本。
我们上函数编程HASKELL课时候的讲义 很有用的讲解了函数编程 和HASKELL的使用方法 很不错的
Atom-ide-haskell.zip,用于Atom编辑器的Haskell IDE插件伊德哈斯克尔,atom是一个用web技术构建的开源文本编辑器。
Haskell 2010 Language Report, Haskell2010的官方报告
最近出的书,使用Haskell 2010,并且讲解中使用的是现代的工具链(如stack),并是用构建工具stack来新建、编译和运行书中的全部示例代码工程。
irc-core, 在 Freenode #haskell IRC中,Haskell IRC库和控制台客户机加入了我们 GLIRC - 高级控制台IRC客户端glirc 核心 连接 Wiki文档 建筑glirc使用最新版本的软件包,请确保软件包的数据库是只读的: $ cabal ...