java – 使用大数据计算公共组成员资格的算法

发布时间：2020-12-14 05:36:45 所属栏目：Java 来源：网络整理

导读：我需要编写一个程序来计算两个用户在同一组中的次数.用户按用户名和组ID分配. 例如,使用输入(存储在文本文件中)： john 32john 21jim 21jim 32bob 32 我想要结果： john-jim 2 john-bob 1jim-bob 1 这听起来微不足道.但问题是：我有1,800万组和30万用户.还有

我需要编写一个程序来计算两个用户在同一组中的次数.用户按用户名和组ID分配.
例如,使用输入(存储在文本文件中)：

john 32
john 21
jim 21
jim 32
bob 32

我想要结果：

john-jim 2 
john-bob 1
jim-bob 1

这听起来微不足道.但问题是：我有1,800万组和30万用户.还有很多会员资格(我预计每个用户平均至少50个,可能更多).这意味着大量的数据和处理.

我写了5个不同的程序,没有一个能够减少数据量：它像PostgreSQL查询一样慢.耗尽内存消耗在Java工作内存中的Map中运行(第一个堆空间,在优化之后我得到了罕见的“超出GC开销限制”).从Java连续写入数据库太慢(即使使用批处理查询进行优化).越来越绝望,我尝试了一些更奇特的东西,比如把所有的对都写成一个数组,然后对它们进行排序(O(n log(n)))然后将它们计算为peuàpeu.但仍有太多数据需要存储在内存中.

有关算法的任何想法吗？还是不可能？

解决方法

RDBMS专门用于排序等操作.在数据库外部执行此操作几乎不会在性能上接近.用SQL做吧！

这将完成工作(简化更新)：

SELECT t1.usr || '-' || t2.usr,count(*) AS ct
FROM   usr_grp t1
JOIN   usr_grp t2 USING (grp_id) 
WHERE  t2.usr > t1.usr   -- prevent dupes and get sorted pair
GROUP  BY t1.usr,t2.usr;

正如您所说,根据您拥有的重叠次数,这可能会产生大量的行.所以这永远不会快.

提出一个问题：产生数百万行没有人可以处理的目的是什么？你确定,这个操作从一开始就有意义吗？

为了让它更快,你可以..

>升级！ PostgreSQL 8.4 is rather outdated by now.特别是,PostgreSQL 9.2专注于大数据.对于像这样的工作,你可以期待更好的性能.
没有人应该运行8.4.0.仅出于安全原因,您也错过了很多错误修复.目前的释放点是8.4.17.我引用链接的网站：

We always recommend that all users run the latest available minor
release for whatever major version is in use.

>使用整数作为用户的代理键,因此只在usr_grp中处理整数.使表和索引更小并且处理更快.如果n：m表(usr_grp)具有比表usr更大的基数,那么它应该更快,即使它意味着额外的连接.

SELECT u1.usr  || '-' || u2.usr,count(*) AS ct
FROM   usr_grp t1
JOIN   usr_grp t2 USING (grp_id) 
JOIN   usr u1 ON t1.usr_id = u1.usr_id
JOIN   usr u2 ON t2.usr_id = u2.usr_id
WHERE  t2.usr_id > t1.usr_id
GROUP  BY u1.usr_id,u2.usr_id;

>创建一个多列索引(如果还没有).
grp_id必须先来. Why does this matter?

CREATE INDEX usr_grp_gu_idx ON usr_grp(grp_id,usr_id);

>将大量RAM放入机器并增加work_mem和shared_buffers的设置.

测试用例

我将数字@OldCurmudgeon reported作为他的测试用例,并在PostgreSQL中创建了一个类似的测试用例.

-> SQLfiddle demo.

在这个公共测试数据库中约250毫秒.
结果没有排序(没有ORDER BY),因为尚未指定.
与2.5分钟相比,reported below.因素600.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!