pagerank
PageRank算法的实现目标一 迭代法实现题目迭代法实现大规模PageRank,网页数量不低于10000
思路首先创建一个txt文件,里面储存各个点之间的关系,然后通过python语言读取,将其转化为矩阵,并通过公式将其转化为相应矩阵,然后进行迭代,直至误差小于 0.00000001结束。
原理
源代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859import numpy as npif __name__ == '__main__': file = open('input2.txt', 'r') edges_in = [] edges_out = [] while True: lines = file.readline().strip('\n') if not lines: ...
bloom
Bloom过滤器算法的实现题目采用Bloom过滤器设计一个邮件地址过滤器。要求:存储1000000个垃圾邮件地址,检测错误率小于0.00001,如果采用k=8个映射函数,则Bloom过滤器的最小长度是多少?
思路创建一个rubbish.txt文件储存垃圾邮件地址,垃圾邮件地址由程序自动生成,然后生成一个input.txt文件用于储存输入的邮箱地址,过滤后邮箱地址由output.txt储存。
使用python的bitarray来进行位操作,更加方便,主要是使用的空间少,如何使用numpy.array需要34GiB,电脑无法分配如此巨量的空间。然后使用开源的8种哈希函数进行散列,然后取最后N位,N为位的个数,进行下标设置1操作。
原理布隆过滤器的核心就是哈希函数,可以将其看作是对 bitmap 的拓展,通过将添加的元素经过 k 个哈希函数映射到一个很长的 bit 向量中的 k 个位置,并将它们置为 1。检索时,通过判断这个位置是否都为 1 就能大概知道集合中是否存在查询的元素。具体规则是:
如果这些位置中有任何一个位置为 0,那么被检索的元素一定不在
如果这些位置都是 1,那么被检索的 ...