performance - 聚合点的算法

Question

我有一张桌子

• 第 1 行 = (V1, K1, 5);
• 第2行=（V2，K2，7）；
• 第2行=（V1，K1，3）；

我需要聚合 AggregateRating 表中的点，以便该表包含

• 第 1 行 = (V1, K1, 8);
• 第2行=（V2，K2，7）；

我在 Rating 表中循环一次，并使用 [key = (Col1,Col2), value = Points] 创建一个地图，如果密钥存在，我添加点，否则创建一个新的地图条目。评级表可以包含近 100 多个条目，因此我想避免多次通过。

这是最有效的方法吗？

Answer 1

这取决于您用于存储地图的数据结构。如果您使用哈希映射，那么存储和读取它的复杂性将保持不变（O(1)）。然后，您使用一个查询进行一次传递，并且对数组中的每个条目最多插入一次。这意味着您的算法的整体复杂性将是O(n).

但是，仅输入是O(n)，这意味着您无法做得更好。

请记住，如果您选择不同的地图实现，例如树形地图，复杂性将会改变，您将无法获得最有效的解决方案。