锐客网

  1. 首页 > 睿知 > it技术 > >

php不适合处理大数据 php yield 处理大数据( 六 )

IT技术partition


9.trie树
适用范围：数据量大，重复多，但是数据种类小可以放入内存
基本原理及要点：实现方式 ， 节点孩子的表示方式
扩展：压缩实现 。
问题实例：
1).有10个文件，每个文件1G ，  每个文件的每一行都存放的是用户的query，每个文件的query都可能重复 。要你按照query的频度排序。
2).1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串 。请问怎么设计和实现？
3).寻找热门查询：查询串的重复度比较高 ， 虽然总数是1千万，但如果除去重复后，不超过3百万个，每个不超过255字节 。
10.分布式处理 mapreduce
适用范围：数据量大，但是数据种类小可以放入内存
基本原理及要点：将数据交给不同的机器去处理 ， 数据划分，结果归约 。
扩展：
问题实例：
1).The canonical example application of MapReduce is a process to count the appearances of
each different word in a set of documents:
void map(String name, String document):
// name: document name
// document: document contents
for each word w in document:
EmitIntermediate(w, 1);
void reduce(String word, Iterator partialCounts):
// key: a word
// values: a list of aggregated partial counts
int result = 0;
for each v in partialCounts:
result += ParseInt(v);
Emit(result);
Here, each document is split in words, and each word is counted initially with a "1" value by
the Map function, using the word as the result key. The framework puts together all the pairs
with the same key and feeds them to the same call to Reduce, thus this function just needs to
sum all of its input values to find the total appearances of that word.
2).海量数据分布在100台电脑中 ， 想个办法高效统计出这批数据的TOP10 。
3).一共有N个机器，每个机器上有N个数 。每个机器最多存O(N)个数并对它们操作 。如何找到N^2个数的中数(median)？
经典问题分析
上千万or亿数据（有重复），统计其中出现次数最多的前N个数据,分两种情况：可一次读入内存，不可一次读入 。
可用思路：trie树+堆，数据库索引，划分子集分别统计，hash，分布式计算，近似统计，外排序
所谓的是否能一次读入内存，实际上应该指去除重复后的数据量 。如果去重后数据可以放入内存，我们可以为数据建立字典 ， 比如通过 map，hashmap，trie，然后直接进行统计即可 。当然在更新每条数据的出现次数的时候，我们可以利用一个堆来维护出现次数最多的前N个数据，当然这样导致维护次数增加 ， 不如完全统计后在求前N大效率高 。
如果数据无法放入内存 。一方面我们可以考虑上面的字典方法能否被改进以适应这种情形，可以做的改变就是将字典存放到硬盘上，而不是内存，这可以参考数据库的存储方法 。
当然还有更好的方法，就是可以采用分布式计算，基本上就是map-reduce过程，首先可以根据数据值或者把数据hash(md5)后的值，将数据按照范围划分到不同的机子 ， 最好可以让数据划分后可以一次读入内存，这样不同的机子负责处理各种的数值范围 ， 实际上就是map 。得到结果后 ， 各个机子只需拿出各自的出现次数最多的前N个数据，然后汇总，选出所有的数据中出现次数最多的前N个数据，这实际上就是reduce过程 。
实际上可能想直接将数据均分到不同的机子上进行处理，这样是无法得到正确的解的 。因为一个数据可能被均分到不同的机子上，而另一个则可能完全聚集到一个机子上 ， 同时还可能存在具有相同数目的数据 。比如我们要找出现次数最多的前100个，我们将1000万的数据分布到10台机器上，找到每台出现次数最多的前 100个，归并之后这样不能保证找到真正的第100个，因为比如出现次数最多的第100个可能有1万个，但是它被分到了10台机子，这样在每台上只有1千个 ， 假设这些机子排名在1000个之前的那些都是单独分布在一台机子上的，比如有1001个，这样本来具有1万个的这个就会被淘汰 ， 即使我们让每台机子选出出现次数最多的1000个再归并，仍然会出错 ， 因为可能存在大量个数为1001个的发生聚集 。因此不能将数据随便均分到不同机子上，而是要根据hash 后的值将它们映射到不同的机子上处理，让不同的机器处理一个数值范围 。

推荐阅读


上一篇：关于wordpress圆角卡片式主题的信息

下一篇：为什么总不显示路由器名，路由不显示wifi