网站建设网站建,网站开发项目经验怎么写,wordpress 管理登录,重庆网站建设重庆最加科技十一#xff0c;百亿数据中找中位数 桶/计数排序思想 根据数据的特征#xff0c;比如数据落在某个固定范围内#xff0c;可以使用桶排序或计数排序的思想。通过统计每个桶内元素的数量#xff0c;我们可以确定中位数所在的桶#xff0c;然后在该桶内使用更精确的方法计算中…十一百亿数据中找中位数 桶/计数排序思想 根据数据的特征比如数据落在某个固定范围内可以使用桶排序或计数排序的思想。通过统计每个桶内元素的数量我们可以确定中位数所在的桶然后在该桶内使用更精确的方法计算中位数。 外部排序 如果数据无法一次性装入内存则可以使用外部排序。这个过程包括将数据分割成多个块每个块单独排序并存储在外部存储器如硬盘上再将这些有序的块合并来找出整体的中位数。 1. 分割数据
将原始数据集分割成多个小块称为“runs”或“chunks”。每个小块的大小应当适合放入内存中进行排序。2. 排序小块
读取每个小块至内存使用内部排序算法如快速排序、堆排序等对其进行排序。3. 存储排序后的小块
将排序后的小块写回到外部存储硬盘等上。这样硬盘上就有了多个有序的数据块。4. 归并排序
使用N路归并排序算法将所有有序的小块合并成一个完整有序的数据集。这个步骤通常涉及以下操作创建一个优先队列最小堆初始化时将每个有序块的第一个元素加入。
不断从优先队列堆中取出最小元素并将该元素所在块的下一个元素加入队列。
将取出的最小元素写入到最终的输出文件中。
重复以上过程直到所有块中的元素都被处理。
5. 输出最终结果
最终所有数据块中的元素都按顺序写入到最终输出文件中完成总体的排序任务。外部排序的效率很大程度上取决于磁盘IO的速度以及归并阶段处理有序块的效率。在现代操作系统中通常会使用缓冲区来减少磁盘IO次数提高外部排序的速度。MapReduce估算中位数 将数字按范围数位大小分到不同的桶中 每个分位桶排序计算得到一个局部中位数 以中间两个桶的局部中位数为基础来估算全局中位数
十二海量数据求TopK问题
海量日志数据提取出某日访问百度次数最多的那个IP如果想一次性把所有IP数据装进内存处理则内存容量明显不够故针对数据太大内存受限的情况可以把大文件转化成取模映射小文件从而大而化小逐个处理。换言之先映射而后统计最后排序。
具体分为以下3个步骤 1.分而治之/hash映射 首先把这一天访问百度日志的所有IP提取出来然后逐个写入到一个大文件中接着采用映射的方法比如%1000把整个大文件映射为1000个小文件。 2.hash_map统计 当大文件转化成了小文件那么我们便可以采用hash_map(ip, value)来分别对1000个小文件中的IP进行频率统计再找出每个小文件中出现频率最大的IP。 3.堆/快速排序 统计出1000个频率最大的IP后依据各自频率的大小进行排序(可采取堆排序)找出那个频率最大的IP即为所求。 注Hash取模是一种等价映射不会存在同一个元素分散到不同小文件中去的情况即这里采用的是%1000算法那么同一个IP在hash后只可能落在同一个文件中不可能被分散的。 同样的有一个1G大小的一个文件里面每一行是一个词词的大小不超过16字节内存限制大小是1M。返回频数最高的100个词
解法 1.分而治之/hash映射 顺序读取文件对于每个词x取hash(x)%5000然后把该值存到5000个小文件记为x0,x1,…x4999中。这样每个文件大概是200k左右。当然如果其中有的小文件超过了1M大小还可以按照类似的方法继续往下分直到分解得到的小文件的大小都不超过1M。 2.hash_map统计 对每个小文件采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。 3.堆/归并排序 取出出现频率最大的100个词可以用含100个结点的最小堆后再把100个词及相应的频率存入文件这样又得到了5000个文件。最后就是把这5000个文件进行归并类似于归并排序的过程了。 参考https://www.cnblogs.com/xingyunblog/articles/9078808.html
十三、如何设计一个比较两篇文章相似度的算法
局部敏感哈希Locality-Sensitive HashingLSH是一种用于快速相似性搜索的算法技术。该技术主要用于高维空间中的数据其目标是为相似的对象生成相同或相近的哈希值而对于不相似的对象则生成不同的哈希值。通过这种方式LSH能够在大规模数据集中高效地执行近邻搜索任务。
特点
局部敏感性如果两个数据点相似那么它们被哈希到相同桶中的概率会很高。
可调性LSH家族通常有参数可以调整以控制相似度与哈希碰撞概率之间的平衡。simhash作为locality sensitive hash局部敏感哈希的一种 其主要思想是降维将高维的特征向量映射成低维的特征向量通过两个向量的Hamming Distance来确定文章是否重复或者高度近似。 其中Hamming Distance又称汉明距离在信息论中两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。如此通过比较多个文档的simHash值的海明距离可以获取它们的相似度。
simhash算法分为5个步骤分词、hash、加权、合并、降维具体过程如下所述
分词 给定一段语句进行分词得到有效的特征向量然后为每一个特征向量设置1-5等5个级别的权重如果是给定一个文本那么特征向量可以是文本中的词其权重可以是这个词出现的次数。例如给定一段语句“CSDN博客结构之法算法之道的作者July”分词后为“CSDN 博客 结构 之 法 算法 之 道 的 作者 July”然后为每个特征向量赋予权值CSDN(4) 博客(5) 结构(3) 之(1) 法(2) 算法(3) 之(1) 道(2) 的(1) 作者(5) July(5)其中括号里的数字代表这个单词在整条语句中的重要程度数字越大代表越重要。 hash 通过hash函数计算各个特征向量的hash值hash值为二进制数01组成的n-bit签名。比如“CSDN”的hash值Hash(CSDN)为100101“博客”的hash值Hash(博客)为“101011”。就这样字符串就变成了一系列数字。 加权 在hash值的基础上给所有特征向量进行加权即W Hash * weight且遇到1则hash值和权值正相乘遇到0则hash值和权值负相乘。例如给“CSDN”的hash值“100101”加权得到W(CSDN) 100101_4 4 -4 -4 4 -4 4给“博客”的hash值“101011”加权得到W(博客)101011_5 5 -5 5 -5 5 5其余特征向量类似此般操作。 合并 将上述各个特征向量的加权结果累加变成只有一个序列串。拿前两个特征向量举例例如“CSDN”的“4 -4 -4 4 -4 4”和“博客”的“5 -5 5 -5 5 5”进行累加得到“45 -4±5 -45 4±5 -45 45”得到“9 -9 1 -1 1”。 降维 对于n-bit签名的累加结果如果大于0则置1否则置0从而得到该语句的simhash值最后我们便可以根据不同语句simhash的海明距离来判断它们的相似度。例如把上面计算出来的“9 -9 1 -1 1 9”降维某位大于0记为1小于0记为0得到的01串为“1 0 1 0 1 1”从而形成它们的simhash签名。
