6

我需要编写一个程序来计算两个用户在同一组中的次数。用户由用户名给出，组由 id 给出。例如，使用输入（存储在文本文件中）：

john 32
john 21
jim 21
jim 32
bob 32

我想要结果：

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

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

我已经编写了 5 个不同的程序来执行此操作，但没有一个能够减少数据量：它作为 PostgreSQL 查询太慢了。在 Java 工作内存中的 Map 中运行太耗内存（第一个堆空间，优化后我得到了罕见的“超出 GC 开销限制”）。从 Java 连续写入数据库太慢（即使使用批处理查询进行了优化）。越来越绝望，我尝试了一些更奇特的事情，比如将所有对写入数组，然后对它们进行排序 (O(n log (n)))，然后计算它们 peu à peu。但它仍然是太多的数据存储在内存中。

关于这样做的算法的任何想法？还是不可能？

4

3 回答 3

7

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 现在已经过时了。特别是 PostgreSQL 9.2 专注于大数据。对于这样的工作，您可以期待更好的表现。没有人应该运行 8.4.0
    。仅出于安全原因，您也错过了许多错误修复。当前的版本是 8.4.17。我引用链接的网站：

我们始终建议所有用户针对正在使用的主要版本运行最新的可用次要版本。

  • 为用户使用integeras 代理键，因此您只在usr_grp. 使表和索引更小，处理速度更快。如果 n:m table ( usr_grp) 的基数比 table 大得多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;


    CREATE INDEX usr_grp_gu_idx ON usr_grp(grp_id, usr_id);

测试用例

我获取了@OldCurmudgeon为他的测试用例报告的数字，并在 PostgreSQL 中创建了一个可比较的测试用例。

-> SQLfiddle演示。

在这个公共测试数据库中~ 250 毫秒。
结果未排序（否ORDER BY），因为尚未指定。
相比2.5 分钟，报告如下。系数 600。

于 2013-04-05T10:01:59.170 回答
2

让你的文件系统来做这件事怎么样。

对于每个条目 - 打开一个以组 ID 命名的文件并附加新用户的名称。您最终将得到每组一个文件。

你现在有 - 例如：

Group-21.txt
 jim
 john

Group-32.txt
 bob
 jim
 john

现在遍历所有文件，在其中生成每个用户名对（我将对名称进行排序并对其执行标准组合过程）。对于每一对，将“1”附加到具有特定名称的文件中。

你现在有 - 例如：

User-jim-john.txt
 11

User-bob-jim.txt
 1

User-bob-john.txt
 1

您现在在文件中拥有文件名和计数对（一元，所以您真正需要的只是文件大小（以字节为单位））。

尽管第 1 阶段必须在第 2 阶段开始之前完成，但几乎所有这些都可以并行完成。为了提高速度 - 添加内核 - 购买更快的磁盘。没有内存限制，只有磁盘。

补充：我刚刚使用一个线程对此算法进行了一些模拟测试

1800 个群组、300 个用户和 15000 个会员都是随机生成的，耗时约 2.5 分钟。900 个群组、150 个用户和 7500 个会员资格用时 54 秒。

于 2013-04-05T10:33:47.710 回答
1

无论解决方案如何，复杂性取决于生成的对数，而不一定取决于组或人的数量。对于不同的组大小：

  • 一个有 10 个成员的组产生 C(10,2) = 45 对
  • 一个有 100 个成员的组产生 C(100,2) = 4950 对
  • 1000人的团体，499500对...
  • 拥有10000名成员，单组将产生近5000万双！因此，单个组可以超过其余计算的全部成本。

所以我的第一个建议是在数据集中剔除非常大的组。如果您不能省略大型组，并且发现它不适合内存或者使用单个线程需要很长时间才能通过它，您可以使用Map-Reduce自动并行化计算，如下所示。如果您从组成员身份开始，例如：

32 -> john, jim, bob
21 -> john, jim

您可以使用 map 步骤生成所有对：

john-jim -> 32, john-bob -> 32, jim-bob -> 32
john-jim -> 21

这些将按名称对为您汇总。然后在 reduce 中，只计算每个键的出现次数。这假设您有足够的磁盘来存储所有对。

于 2013-04-05T10:41:22.630 回答