例如,使用输入(存储在文本文件中)：
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.但仍有太多数据需要存储在内存中.
有关算法的任何想法吗？还是不可能？
解决方法
这将完成工作(简化更新)：
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.