当前位置: 首页 > >

按看电影次数的最多的前n个用户问题,极限性能解答

发布时间:

有一个5000万的用户文件,一个2亿记录的用户看电影记录,列出前1000/1000万个看电影次数最多的用户。


本答案比更通用更有扩展性的答案麻烦很多倍,但是性能应该也能强个几倍。
分析:
用户有50M个(显然不重复,我们关心用户名或UUID,总之是个超过int32的数据类型),
记录有200M个(每行记录我们只关心是哪个用户),
任务的最后一个步奏是不断的得出某个用户的总观影次数,配合最小堆,即可求出前x个用户的id。


首先为了性能,必须把用户映射为int,但这样基本会有冲突。
首先我们需要1个 哈希表MapA 来记录无冲突{用户hash, 用户名的文件偏移量},1个 双向映射表MapB用来记录发生了冲突的 {hash, 用户名} (双向映射表可实现为两个单向map)
** 定义“唯一int”: 用户名的唯一标识,类型为int**
让hash无冲突(或者第一个占用了那个hash值的)的用户名,唯一int = hash=31位int整数,
让hash有冲突的用户名(除去第一个占用了hash值的),唯一int = 负的总冲突次数序号(-1, -2, …)
稍后我们在遍历观影记录时,先在MapB中查询,如果没有得到负数序号,那么就取其31位hash作为唯一id,否则以负数序号作为唯一id。


**我们需要得到一个hash值-用户名的表,为了节省空间,用户名用字符串在文件偏移量表示 **
由于50M个用户映射映射到31位(2G)的数值空间中,显然较为稀疏,所以冲突的用户数量会很少,所以两个Map占用内存较少,可以常驻内存。


用户文件的每17M条分为一组
遍历这些组
----对于第i组:


遍历第i组,每个hash(name),如果是第一次出现,那么存储到MapA,否则(也就是在MapA中能找到此hash)那么存储到MapB中。假设MapA每项需要40字节,此时MapA占用内存17M×40字节=680MB随后将MapA序列化并排序,写为文件Ai (A1, A2, A3 …),每个Ai文件小于 8字节*17M = 136MB。清空MapA,但保留双向MapB

现在我们得到了50M/17M=3个Ai文件,其中存储了局部的int不冲突的用户,但是他们在全局可能会int冲突,下面就要解决冲突
先申请200M×4字节=800MB的内存映射文件备用,其作为一个数组H记录每次观影的唯一int,其数据存储于硬盘或内存中,手动维持其在内存中实际存在100MB。这个文件在随后的使用时,表现为区域的连续读取,不会出现跨区域的随机读取,因此性能很好。


对各自内部有序的Ai进行多路归并:如果int2int1,那么把A2的那一行处理到MapB,如果int3int2或int1,那么把A3的那一行处理到MapB;如果没有相等,那么把{最小int,偏移量}追加到数组D……
每写满数组D的一部分(17M条=136MB),将Di重构为MapDi


只要有MapDi 配合MapB,我们就有了一种能力:对于某条观影记录可以根据hash(name),如果不介于MapDi的最小值和最大值之间,那么暂时标记为0x80000000等下一轮另一组MapD再处理这条观影记录,否则可以唯一地确定name的全局唯一int。所以根据MapDi和MapB,尽力过滤观影记录文件到H数组中去。
经过几轮就能把观影记录文件完全翻译为虚拟内存中的H数组,其中每条是一个用户的全局唯一int
清空除MapB以外其他内存,将内存映射文件中的H数组完全载入内存,使用1G内存2G文件找出现最多次QQ号算法中的算法,配合最小堆得到目标前x个用户的唯一id,将这些唯一id用MapB检查后,或从Ai文件中,即可逆查出用户名。

由于写文件时只二进制输出了int,所以写硬盘体积最小,因此性能是挺好的。


另外复杂度低的方法是根据hash(name)把用户文件和观影文件各自分成多个文件(必须输出用户名全名,因此此步骤硬盘读写量很大),然后分组处理,各组自然降低了数据量,后面的可以简单使用hashmap装载组内全部数据处理,并获得组内的topK个用户名,再合并多个组再次得出topK。由于各组粗放地使用内存,因此组数量远大于3,可能是100,进行100组topK的合并,如果K极大,那么还有进一步优化方案,就是各组先评估组内的数值分布,一个组的数值分布,例子如{第100个用户看了1000场,第200个用户看了200场,第300个用户看了5场……}, 然后所有组的数值分布重叠在一起,把较少数值的组直接丢弃,分析出topK可能在哪些组的各多少topXi中,然后组合进行topK算法,求出答案。



友情链接: