- 浏览: 197698 次
- 性别:
- 来自: 北京
-
文章分类
最新评论
-
only_java:
博主,你好。感谢这篇你的这篇文章,我的问题是跟你一样,也是在跑 ...
JVM Crash分析 -
shuofenglxy:
1 确保程序运行时没有更新程序需要的相关jar包。2 确保程序 ...
JVM Crash分析 -
renduly:
# A fatal error has been detect ...
JVM Crash分析 -
shuofenglxy:
renduly 写道博主好。这两天我在公司程序也出现了类似的问 ...
JVM Crash分析 -
renduly:
博主好。这两天我在公司程序也出现了类似的问题。博主能否说的详细 ...
JVM Crash分析
原文来自:http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html
BloomFilter——大规模数据处理利器
Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。
一 . 实例
为了说明Bloom Filter存在的重要意义,举一个实例:
假设要你写一个网络蜘蛛(web crawler)。由于网络间的链接错综复杂,蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”,就需要知道蜘蛛已经访问过那些URL。给一个URL,怎样知道蜘蛛是否已经访问过呢?稍微想想,就会有如下几种方案:
1. 将访问过的URL保存到数据库。
2. 用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。
3. URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。
4. Bit-Map方法。建立一个BitSet,将每个URL经过一个哈希函数映射到某一位。
方法1~3都是将访问过的URL完整保存,方法4则只标记URL的一个映射位。
以上方法在数据量较小的情况下都能完美解决问题,但是当数据量变得非常庞大时问题就来了。
方法1的缺点:数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了?
方法2的缺点:太消耗内存。随着URL的增多,占用的内存会越来越多。就算只有1亿个URL,每个URL只算50个字符,就需要5GB内存。
方法3:由于字符串经过MD5处理后的信息摘要长度只有128Bit,SHA-1处理后也只有160Bit,因此方法3比方法2节省了好几倍的内存。
方法4消耗内存是相对较少的,但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash表冲突的各种解决方法么?若要降低冲突发生的概率到1%,就要将BitSet的长度设置为URL个数的100倍。
实质上上面的算法都忽略了一个重要的隐含条件:允许小概率的出错,不一定要100%准确!也就是说少量url实际上没有没网络蜘蛛访问,而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。
二 . Bloom Filter 的算法
废话说到这里,下面引入本篇的主角——Bloom Filter。其实上面方法4的思想已经很接近Bloom Filter了。方法四的致命缺点是冲突概率高,为了降低冲突的概念,Bloom Filter使用了多个哈希函数,而不是一个。
Bloom Filter算法如下:
创建一个m位BitSet,先将所有位初始化为0,然后选择k个不同的哈希函数。第i个哈希函数对字符串str哈希的结果记为h(i,str),且h(i,str)的范围是0到m-1 。
(1) 加入字符串过程
下面是每个字符串处理的过程,首先是将字符串str“记录”到BitSet中的过程:
对于字符串str,分别计算h(1,str),h(2,str)…… h(k,str)。然后将BitSet的第h(1,str)、h(2,str)…… h(k,str)位设为1。
图1.Bloom Filter加入字符串过程
很简单吧?这样就将字符串str映射到BitSet中的k个二进制位了。
(2) 检查字符串是否存在的过程
下面是检查字符串str是否被BitSet记录过的过程:
对于字符串str,分别计算h(1,str),h(2,str)…… h(k,str)。然后检查BitSet的第h(1,str)、h(2,str)…… h(k,str)位是否为1,若其中任何一位不为1则可以判定str一定没有被记录过。若全部位都是1,则“认为”字符串str存在。
若一个字符串对应的Bit不全为1,则可以肯定该字符串一定没有被Bloom Filter记录过。(这是显然的,因为字符串被记录过,其对应的二进制位肯定全部被设为1了)
但是若一个字符串对应的Bit全为1,实际上是不能100%的肯定该字符串被Bloom Filter记录过的。(因为有可能该字符串的所有位都刚好是被其他字符串所对应)这种将该字符串划分错的情况,称为false positive 。
(3) 删除字符串过程
字符串加入了就被不能删除了,因为删除会影响到其他字符串。实在需要删除字符串的可以使用Counting bloomfilter(CBF),这是一种基本Bloom Filter的变体,CBF将基本Bloom Filter每一个Bit改为一个计数器,这样就可以实现删除字符串的功能了。
Bloom Filter跟单哈希函数Bit-Map不同之处在于:Bloom Filter使用了k个哈希函数,每个字符串跟k个bit对应。从而降低了冲突的概率。
三 . Bloom Filter 参数选择
(1) 哈希函数选择
哈希函数的选择对性能的影响应该是很大的,一个好的哈希函数要能近似等概率的将字符串映射到各个Bit。选择k个不同的哈希函数比较麻烦,一种简单的方法是选择一个哈希函数,然后送入k个不同的参数。
(2)Bit 数组大小选择
哈希函数个数k、位数组大小m、加入的字符串数量n的关系可以参考参考文献1 。该文献证明了对于给定的m、n,当 k = ln(2)* m/n 时出错的概率是最小的。
同时该文献还给出特定的k,m,n的出错概率。例如:根据参考文献1,哈希函数个数k取10,位数组大小m设为字符串个数n的20倍时,false positive发生的概率是0.0000889 ,这个概率基本能满足网络爬虫的需求了。
四 . Bloom Filter 实现代码
下面给出一个简单的Bloom Filter的Java实现代码:
import java.util.BitSet; public class BloomFilter { /* BitSet初始分配2^24个bit */ private static final int DEFAULT_SIZE = 1 << 25; /* 不同哈希函数的种子,一般应取质数 */ private static final int[] seeds = new int[] { 5, 7, 11, 13, 31, 37, 61 }; private BitSet bits = new BitSet(DEFAULT_SIZE); /* 哈希函数对象 */ private SimpleHash[] func = new SimpleHash[seeds.length]; public BloomFilter() { for (int i = 0; i < seeds.length; i++) { func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]); } } // 将字符串标记到bits中 public void add(String value) { for (SimpleHash f : func) { bits.set(f.hash(value), true); } } //判断字符串是否已经被bits标记 public boolean contains(String value) { if (value == null) { return false; } boolean ret = true; for (SimpleHash f : func) { ret = ret && bits.get(f.hash(value)); } return ret; } /* 哈希函数类 */ public static class SimpleHash { private int cap; private int seed; public SimpleHash(int cap, int seed) { this.cap = cap; this.seed = seed; } //hash函数,采用简单的加权和hash public int hash(String value) { int result = 0; int len = value.length(); for (int i = 0; i < len; i++) { result = seed * result + value.charAt(i); } return (cap - 1) & result; } } }
参考文献:
[1]Pei Cao. Bloom Filters - the math.
http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
[2]Wikipedia. Bloom filter.
http://en.wikipedia.org/wiki/Bloom_filter
发表评论
-
数组查值
2011-09-27 16:42 833问题描述:{4,5,7,8,1,2} 找值为K的元素。 两种 ... -
全排列 递归式
2011-09-27 15:18 887简单的整理一下全排列思路。全部遍历,打印前筛选条件。全部遍历则 ... -
简单的四则运算计算器
2011-09-27 11:27 894这是一个简单的四则运算计算器,不支持括号,没有做乘法的越 ... -
ZZ并查集
2011-02-22 15:40 907原文出处:http://blog.si ... -
矩阵链乘法算法讲解
2011-02-15 15:57 4395矩阵链乘是一个计算 ... -
把二元查找树转变成排序的双向链表
2011-02-14 19:59 2026分析:二叉树中序遍历即可得到一个有序的结果,只要按照中序遍历的 ... -
A Simple Ordered Hashtable
2011-02-11 15:26 984原文来自: http://wuhua.iteye.com/bl ... -
递归总结二 汉诺塔问题
2011-02-07 19:38 1156汉诺塔是貌似递归入门的引导题目,把这个过程写下来,mark一下 ... -
递归总结一 全排列问题
2011-02-07 18:48 1596全排列问题:这是描述 ... -
几种常见的排序算法
2011-02-05 13:19 1185这里是以前写的算法总结了。照搬过来而已。 package S ... -
二叉树和红黑树的java实现
2011-02-05 13:11 1638二叉查找树代码大致如下: 二叉树节点类: pa ... -
LIS 最长递增子序列算法总结
2011-02-05 12:53 1515这里包含了三种求得递增子序列的算法。 是以前写的代码,这里就 ... -
求1的个数问题
2011-01-25 16:14 1192又是一年笔试时,很多学弟们开始笔试了。今天学弟问求一个int数 ... -
消除递归典型应用2------N阶台阶问题
2011-01-25 16:12 1394问题描述:一个人可以一步走1或2或3级台阶,问到N级台阶共有多 ... -
左右手法则的典型应用---字符串逆序
2011-01-25 16:10 1189问题:输入 I am a boy 输出boy a am I ... -
一个正整数拆分为连续的几个整数之和
2011-01-25 16:08 2608import java.util.Scanner; pu ... -
斐波那契序列的基本实现
2011-01-25 16:07 1690今天实在没事干,刚好别人问了我下斐波那契面试怎么回答。就 ... -
矩阵型数据 顺时针打印
2011-01-25 15:28 1422输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。 ...
相关推荐
在日常的开发和使用中,我们经常需要借助各种小工具来提高工作效率,例如快速启动常用的应用程序、管理文件等。一个简单但功能强大的集成工具箱可以帮助用户快速访问、启动并管理程序。今天,我们将以Python为基础,结合Tkinter和Win32API,开发一个类似Windows快捷方式的工具箱应用,能够让你轻松集成各种常用程序并一键启动
django自建博客app
《基于YOLOv8的智慧校园实验室高压灭菌锅安全联锁系统》(包含源码、可视化界面、完整数据集、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计
用于hifi测序数据的基因组组装程序
Microsoft Access 2010 数据库引擎可再发行程序包AccessDatabaseEngine-X64解压后的文件AceRedist
从大模型、智能体到复杂AI应用系统的构建——以产业大脑为例
自然语言处理之TF-IDF算法与TextRank算法的缠绵_textrank,tf-idf和两者的组合-CSDN博客.html
内容概要:2023版《科学智能 (AI4S)全球发展观察与展望》阐述了AI for Science(AI4S)在全球范围内的最新进展及其对科学和工业的深远影响。文章首先回顾了AI4S在过去一年中的快速发展,特别是在药物研发、材料科学、地质学、污染治理等多个领域的应用实例。AI4S通过结合深度学习、机器学习和其他AI技术,加速了从基础研究到实际应用的转化过程。例如,在药物研发中,AI4S帮助科学家克服了“反摩尔定律”的挑战,提高了新药研发的成功率;在材料科学中,AI4S实现了复杂材料的高效模拟,如人造钻石、石墨烯、碳纳米管等;在地质学中,AI4S通过模拟地球内部结构和物理过程,为地震学研究提供了新视角。此外,文章还探讨了大语言模型(LLMs)与科学方法的结合,指出LLMs不仅能辅助科学研究,还能生成新的科学假设并进行逻辑推理。 适合人群:具备一定科研背景或对AI技术感兴趣的科研人员、工程师、政策制定者及高校师生。
这个数据集包含了日常步数统计、睡眠时长、活跃分钟数以及消耗的卡路里,是个人健康与健身追踪的一部分。 该数据集非常适合用于以下实践: 数据清洗:现实世界中的数据往往包含缺失值、异常值或不一致之处。例如,某些天的步数可能缺失,或者存在不切实际的数值(如10,000小时的睡眠或负数的卡路里消耗)。通过处理这些问题,可以学习如何清理和准备数据进行分析。 探索性分析(发现日常习惯中的模式):可以通过分析找出日常生活中的模式和趋势,比如一周中哪一天人们通常走得最多,或是睡眠时间与活跃程度之间的关系等。 构建可视化图表(步数趋势、睡眠与活动对比图):将数据转换成易于理解的图形形式,有助于更直观地看出数据的趋势和关联。例如,绘制步数随时间变化的趋势图,或是比较睡眠时间和活动量之间的关系图。 数据叙事(将个人风格的追踪转化为可操作的见解):通过讲述故事的方式,把从数据中得到的洞察变成具体的行动建议。例如,根据某人特定时间段内的活动水平和睡眠质量,提供改善健康状况的具体建议。
框架结构天城商业办公楼5200平米(建筑图 结构图 计算书 开题报告 任务书 文献翻.zip
柴油机连杆加工工艺及夹具设计.zip
读书网首页的HTML信息
文字渐变颜色代码生成器:让文字绽放多彩魅力,演示:在信息交流日益丰富的今天,个性化的文字展示成为吸引目光的关键。这款文字渐变颜色代码生成器,便是为满足这一需求而生的绿色软件,无需安装,便捷实用。 它的操作极为简便。用户只需在软件界面中输入想要转换的文字内容,接着从丰富的色彩选项里挑选心仪的起始颜色与结束颜色,随后轻轻按下 “转换按钮”,神奇的事情就此发生 —— 适用于论坛、网页、QQ 空间等多种平台,以及自定义格式的渐变颜色代码便会即刻生成。不仅如此,生成的代码还能自动复制到剪切板,极大地节省了用户手动复制的时间。当你在论坛回帖、更新网页内容或是装扮 QQ 空间时,只需轻松粘贴代码,原本单调的文字瞬间就能拥有绚丽的渐变色彩,瞬间脱颖而出,为你的表达增添独特魅力,让文字不再平凡,轻松成为视觉焦点。 一款可以轻松把一段文字生成渐变颜色代码的绿色软件,当你在软件中输入完要转换的文字后,只需要挑选自己喜欢的起始颜色、结束颜色后,按一下―转换按钮即可生成相应的论坛/网页/QQ空间以及自定义格式代码,并且代码可以自动复制到剪切板中,回帖时直接粘贴代码即可不错得文字代码生成器,让你得文字更加漂亮.
1.【锂电池剩余寿命预测】Transformer锂电池剩余寿命预测(Matlab完整源码和数据) 2.数据集:NASA数据集,已经处理好,B0005电池训练、B0006测试; 3.环境准备:Matlab2023b,可读性强; 4.模型描述:Transformer在各种各样的问题上表现非常出色,现在被广泛使用。 5.领域描述:近年来,随着锂离子电池的能量密度、功率密度逐渐提升,其安全性能与剩余使用寿命预测变得愈发重要。本代码实现了Transformer在该领域的应用。 6.作者介绍:机器学习之心,博客专家认证,机器学习领域创作者,2023博客之星TOP50,主做机器学习和深度学习时序、回归、分类、聚类和降维等程序设计和案例分析,文章底部有博主联系方式。从事Matlab、Python算法仿真工作8年,更多仿真源码、数据集定制私信。
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
Android项目原生java语言课程设计,包含LW+ppt
配套文章:https://blog.csdn.net/gust2013/article/details/146909670?spm=1001.2014.3001.5502
《基于YOLOv8的智慧社区儿童游乐设施安全监测系统》(包含源码、可视化界面、完整数据集、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计