
介绍一下海量数据的处理方法
适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集
基本原理及要点:
对 于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明存在,很明显这 个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter,用一个counter数组代替位数组,就可以支持删除了。
还有一个比较重要的问题,如 何根据输入元素个数n,确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况 下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应 该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
举个例子我们假设错误率为0.01,则此时m应大概是n的13倍。这样k大概是8个。
注意这里m与n的单位不同,m是bit为单位,而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。
扩展:
Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter,从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。
问题实例:给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?
根 据这个问题我们来计算下内存的占用,4G=2^32大概是40亿*8大概是340亿,n=50亿,如果按出错率0.01算需要的大概是650亿个bit。 现在可用的是340亿,相差并不多,这样可能会使出错率上升些。另外如果这些urlip是一一对应的,就可以转换成ip,则大大简单了。
2.Hashing
适用范围:快速查找,删除的基本数据结构,通常需要总数据量可以放入内存
基本原理及要点:
hash函数选择,针对字符串,整数,排列,具体相应的hash方法。
碰撞处理,一种是open hashing,也称为拉链法;另一种就是closed hashing,也称开地址法,opened addressing。
扩展:
d-left hashing中的d是多个的意思,我们先简化这个问题,看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半,分别叫做T1和T2,给T1和T2分别配备一个哈希函数,h1和h2。在存储一个新的key时,同 时用两个哈希函数进行计算,得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置,哪一个 位置已经存储的(有碰撞的)key比较多,然后将新key存储在负载少的位置。如果两边一样多,比如两个位置都为空或者都存储了一个key,就把新key 存储在左边的T1子表中,2-left也由此而来。在查找一个key时,必须进行两次hash,同时查找两个位置。
问题实例:
1).海量日志数据,提取出某日访问百度次数最多的那个IP。
数据分析咨询请扫描二维码
若不方便扫码,搜微信号:CDAshujufenxi
在 “神经网络与卡尔曼滤波融合” 的理论基础上,Python 凭借其丰富的科学计算库(NumPy、FilterPy)、深度学习框架(PyTorch、T ...
2025-10-23在工业控制、自动驾驶、机器人导航、气象预测等领域,“状态估计” 是核心任务 —— 即从含噪声的观测数据中,精准推断系统的真 ...
2025-10-23在数据分析全流程中,“数据清洗” 恰似烹饪前的食材处理:若食材(数据)腐烂变质、混杂异物(脏数据),即便拥有精湛的烹饪技 ...
2025-10-23在人工智能领域,“大模型” 已成为近年来的热点标签:从参数超 1750 亿的 GPT-3,到万亿级参数的 PaLM,再到多模态大模型 GPT-4 ...
2025-10-22在 MySQL 数据库的日常运维与开发中,“更新数据是否会影响读数据” 是一个高频疑问。这个问题的答案并非简单的 “是” 或 “否 ...
2025-10-22在企业数据分析中,“数据孤岛” 是制约分析深度的核心瓶颈 —— 用户数据散落在注册系统、APP 日志、客服记录中,订单数据分散 ...
2025-10-22在神经网络设计中,“隐藏层个数” 是决定模型能力的关键参数 —— 太少会导致 “欠拟合”(模型无法捕捉复杂数据规律,如用单隐 ...
2025-10-21在特征工程流程中,“单变量筛选” 是承上启下的关键步骤 —— 它通过分析单个特征与目标变量的关联强度,剔除无意义、冗余的特 ...
2025-10-21在数据分析全流程中,“数据读取” 常被误解为 “简单的文件打开”—— 双击 Excel、执行基础 SQL 查询即可完成。但对 CDA(Cert ...
2025-10-21在实际业务数据分析中,我们遇到的大多数数据并非理想的正态分布 —— 电商平台的用户消费金额(少数用户单次消费上万元,多数集 ...
2025-10-20在数字化交互中,用户的每一次操作 —— 从电商平台的 “浏览商品→加入购物车→查看评价→放弃下单”,到内容 APP 的 “点击短 ...
2025-10-20在数据分析的全流程中,“数据采集” 是最基础也最关键的环节 —— 如同烹饪前需备好新鲜食材,若采集的数据不完整、不准确或不 ...
2025-10-20在数据成为新时代“石油”的今天,几乎每个职场人都在焦虑: “为什么别人能用数据驱动决策、升职加薪,而我面对Excel表格却无从 ...
2025-10-18数据清洗是 “数据价值挖掘的前置关卡”—— 其核心目标是 “去除噪声、修正错误、规范格式”,但前提是不破坏数据的真实业务含 ...
2025-10-17在数据汇总分析中,透视表凭借灵活的字段重组能力成为核心工具,但原始透视表仅能呈现数值结果,缺乏对数据背景、异常原因或业务 ...
2025-10-17在企业管理中,“凭经验定策略” 的传统模式正逐渐失效 —— 金融机构靠 “研究员主观判断” 选股可能错失收益,电商靠 “运营拍 ...
2025-10-17在数据库日常操作中,INSERT INTO SELECT是实现 “批量数据迁移” 的核心 SQL 语句 —— 它能直接将一个表(或查询结果集)的数 ...
2025-10-16在机器学习建模中,“参数” 是决定模型效果的关键变量 —— 无论是线性回归的系数、随机森林的树深度,还是神经网络的权重,这 ...
2025-10-16在数字化浪潮中,“数据” 已从 “辅助决策的工具” 升级为 “驱动业务的核心资产”—— 电商平台靠用户行为数据优化推荐算法, ...
2025-10-16在大模型从实验室走向生产环境的过程中,“稳定性” 是决定其能否实用的关键 —— 一个在单轮测试中表现优异的模型,若在高并发 ...
2025-10-15