我有许多巨大的未排序的List包含(user,amountspend)元组。每个列表对应一天。现在我想将所有列表合并为一个列表，其中包含给定用户的累积值。我有两种方法：
-
方法1：对各个列表进行排序，然后迭代使用合并排序。
-
方法2：以用户为键形成一个HashMap，然后遍历列表并更新密钥的值（如果存在）或添加具有值的新密钥。
如果存在m列表并且每个列表可能具有不同长度的(k1,k2,...,km)
问题：
哪个是有效的解决方案
哪个解决方案可以在多个线程中运行
或者有更好的解决方案吗？
示例：
第1天：（user1100），（user2200）
第2天：（user2,10）、（user1100）、（user3,10）
合并后的列表：（user1200）、（user2210）、（user3,10）
1 的总体方法和复杂性
我想：
- 客户端数量很大但有限=N
- 持续增长的天数=M
- 也许每一天，我们都有每一个客户（或者几乎是这样）
完成工作的最低复杂性：
-
处理每个数据，因此M.N操作。由于你不想保留总和的元素，你只需要做：部分和+新值，所以，一切都需要M.N x有限时间（我想你没有几十亿美元）
-
您必须在N个客户端上协定数据（对于每个数据，您必须在每个客户端上查找、求和、存储…）。对我来说，最短的时间是对客户端至少排序一次（或任何索引它们的方法），所以用最好的算法和最好的实现（也存在更快的方法，但需要非常大的空间）。
所以，你至少需要O（N log N）+O（M.N）。
两种可能的解决方案：
您的方法1浪费时间：因为您对每个列表进行排序（使用相同的数据）。你需要M.O（N log N）+O（M.N）。您只需要一个排序（之后才能求和）。
您的方法2是最短的方法
3如何并行
你（至少）有两种方法来分割你的数据：与天数或与客户。因为你想在客户身上求和，所以使用第二。
您的流程易于扩展
然后你可以使用一个简单的散列函数（客户端的第一个或最后一个字符，或者一些非常简单的东西）=>每个线程（或进程，或机器）接收每个数据，并且只为其客户端保留数据。
你可以这样拆分每个作业（处理、求和、检索…）。
如果需要几乎相同的总时间：
使用k过程，您将拥有k.O（N/k log N/k）+k*Ox（M.N）+k.O（M.N/k）
当你通过拆分N/k获胜时，你会通过选择（牛，我想很快）来回报。
然后你可以在许多机器上分配你的工作，这些机器将是独立的
希望能有所帮助。
HashMap方法更好，因为它是O（N）。这两种解决方案都可以在多个线程中运行，但需要进行不同的修改以支持并发性。
排序和合并解决方案的复杂性为O（mn log n）+O（n log m），其中m是假设每个列表的大小为n的列表数量。
为了计算基于哈希的解决方案的复杂性，让我们假设有k个用户。将k个元素插入到HashMap（Java）或map（C++）中的操作取O（k log k）。在最佳情况下，更改mn-k值的值取（mn-k）O（1），在最坏情况下，取（mn-k）0（logk）。总体复杂度为O（mn log k）。因此，哈希似乎比这两者更好，特别是当k远小于mn时。