高效地合并和重新排序已排序的列表

Question

这不是经典的“合并两个排序”列表问题，这在线性时间内是相当微不足道的。

我想做的是合并两个（key，value）对的列表，它们已经按value排序，其中两个列表中都有具有相同key的对象：这些对象应该合并（添加）它们的value，这可能会改变它们的排序顺序。我主要感兴趣的是如何使用已经排序的列表中的信息高效地执行排序，因为排序是该算法中最慢的部分。

让我们举一个具体的例子。想象一个学生对象的List：

class Student {
  final String name;
  final int score;
  ...
}

作为输入给出两个列表

例如，

List 1:
{"bob", 20}
{"john", 15}
{"mark", 14}

List 2:
{"bill", 11}
{"mark", 9}
{"john", 1}

Result:
{"mark", 23}
{"bob", 20}
{"john", 16}
{"bill", 11}

合并本身（识别出现在两个列表中的学生）可以使用任何O（1）查找/插入结构（例如HashMap）在预期的O（1）时间内完成。我最感兴趣的是排序步骤（尽管我不排除同时进行合并和排序的解决方案）。

但问题是，我如何有效地重新排序这样的列表？现有列表的排序明确地限制了元素在合并列表中的最终位置。例如，如果一个学生在第一个列表中的位置是i，在第二个列表中的位置是j，那么他必须通过一个简单的参数出现在合并列表中的第一个ij学生中，该参数分析可能具有更高分数的学生的最大数量。然而，目前尚不清楚这些信息是否有助于对列表进行排序。

你可以假设在很多情况下，在一个列表中得分高的学生在另一个列表中得分高。当情况并非如此时，该算法应该可以工作，但除了列表已经排序这一事实之外，它还为您提供了一些关于分布的可能有用的额外信息。

这种类型的操作似乎在任何类型的分布式查询排序实现中都很常见。例如，想象一个针对分布式系统的“select state，count（*）group by state”类型的查询问题（计算每个状态中的记录数）——自然地，您会从每个节点得到一个（state，count）对象的排序列表，然后您会希望在REDUCT操作期间合并并重新排序这些对象。放弃分布式节点上已经完成的所有工作似乎很愚蠢。

我感兴趣的是要合并和重新排序的列表很小的情况：通常大约256个条目。分数的范围各不相同，在某些情况下从0到100，在另一些情况下从0到10000000。当然，考虑到元素的数量很小，即使使用简单的算法，每个操作在绝对时间上也会很快，但总计执行了数十亿次。

事实上，下面的一个答案已经证明，通常情况下，对于增加列表大小（即，取n作为组合列表大小）来说，你不能比简单排序做得更好，但实际上我更感兴趣的是，对于固定大小的列表，要做很多次，并且具有良好的经验性能。




Answer 1

（不考虑先合并然后重新排序）我的第一个尝试是声明已排序的输入列表（半静态）优先级队列，并分两个阶段进行。为了避免术语“合并”中的歧义，我将调用创建/更改对象来表示“公共对象”组合/组合的值；为了减少混乱，我将表示优先级队列PQ。

• 识别出现在两个/多个“输入队列”中的对象
  （在这里以次要兴趣的方式）
  • 合并（可能使任一列表中的位置无效），
  • 把它们放在另一个（动态）PQ中（如有必要）
  • 从（输入）队列中删除/无效，它们将不再存在。

  这应该在线性时间内以n个对象的数量工作，对于c个“公共”对象，加上O（c log c），其中组合的对象将取代任何组合的对象而失去顺序。（…假设（识别和）组合一个（公共）对象（见问题中关于预期O（1）的注释）的预期时间不变，
  那么，恐怕这并不能正确地解决主要问题：

  有没有办法利用最后一个键，使其成为至少一个有序序列和“其他值”的（线性、单调）
  组合
  （有很多常见条目——全方位思考。）

  如果组合单调地降低优先级（在示例中，添加（正）分数值会增加优先级），则在合并PQ时不要合并阶段并组合对象，这可能会减少内存和所需的时间。
  否则，选择一个PQ来获取对象（优先级降低），以潜在地与其他对象组合。
  “最坏的情况”似乎是组合对象的优先级没有相关性：恐怕答案通常是
  没有。（有关显式参数，请参阅user2570465的答案）
  （正如BeeOnRope所指出的，选择的（序列）对象在组合中占主导地位（不利的选择）实际上可能会变成一个好情况，如果可以检测和利用的话。）
  话说回来，即使没有（正）相关性（假设在问题中），（线性、单调）组合也可以预期会扭曲密钥的分布：be

Answer 2

看起来你想要一个O（n）合并，就像他们对合并排序所做的那样。我想我可能有一些坏消息要告诉你。我将（希望）证明对于广义问题，你不可能做得比O（nlog（n））更好：（因此，您应该使用其他人提供的任何最优O（nlog（n））解决方案）。首先，我将从直觉开始解释为什么会这样，然后我将写一个非正式的证明。

这个想法是把列表排序的问题转化为你的问题，并表明如果你能比O（nlog（n））更快地解决问题，那么我可以比O（nlog（n））更快地排序任何列表，我们知道这是错误的。我们将只使用整数来保持简单。

假设有一些奇怪的序列需要排序：X=1,3,2，-10,5,4,7,25。现在我将构建两个列表Dec和Inc。我从1=10（即x_1=x_1 0）开始。然后，如果x_{i-1}-

idx   x     Dec    Inc      
----------------------
 1 |  1  =  1   +  0
 2 |  3  =  0   +  3
 3 |  2  =  -2  +  4
 4 | -10 =  -15 +  5
 5 |  5  =  -16 +  21
 6 |  4  =  -18 +  22
 7 |  7  =  -19 +  23
 8 |  25 =  -20 +  45

请注意，我可以在O（n）中从排序转换为您的问题-注意：在O（n）时间内反向Inc以获得两个递减序列。然后我们可以输入您的问题

A = {(1, 1), (2, 0), (3, -2), (4, -15), (5, -16), (6, -18), (7, -19), (8, -20)}
B = {(8, 45), (7, 23), (6, 22), (5, 21), (4, 5), (3, 4), (2, 3), (1, 0)}

现在，如果你可以根据A和B的值之和（有序对中的第二个元素）将它们组合成排序顺序，得到如下结果：

C = {(8, 25), (7, 7), (5, 5), (6, 4), (2, 3), (3, 2), (1, 1), (4, -10)

然后，您基本上已经完成了初始序列x_i的Arg排序（按索引排序）。因此，如果您解决问题的速度比O（nlog（n））快，那么我可以通过首先解决您的问题，然后将解决方案转换为我的列表排序问题来比O（nlog（n））更快地排序。特别是，我将使用复杂性O（n）O（解决问题的复杂性）进行排序

让你的两个键值列表

A = [(ka_i, va_i) | i = 1..n]
B = [(kb_i, vb_i) | i = 1..m] 

按值的降序排序。您无法找到组合列表

C = [(ka_i, va_i + va_j) | ka_i = kb_j]

在快于O（nlog（n））的时间内。

这个证明所做的唯一假设是，你不能比O（nlog（n））时间更快地排序一个列表，这个证明将继续提供一个从排序任意列表到你的问题的O（n）时间的减少。

本质上，我们将展示，如果我们比O（nlog（n））更快地解决问题，那么我们也可以比O（nlog（n））更快地对任意列表进行排序。我们已经知道，不可能比nlog（n）更快地对列表进行排序，所以您想要的解决方案也一定是不可能的。

为了简单起见，我们将对整数列表进行排序。让S=x_1，x_2。。。，x_n可以是任何整数序列。现在我们将构建两个列表，Dec和Inc。

我们有三个限制：

1. 公司正在严格增加
2. Dec正在严格减少
3. 在算法的迭代i中，Inc[j]Dec[j]=x_j表示所有j=1。。i-1

顾名思义，Dec将严格减少，Inc将严格增加。对于i=1，我们将保持x_i=Dec[i]Inc[i]的不变量。。n

以下是减少：

# (Assume 1-indexed lists)
1. Initialize Inc = [x_1] and Dec = [0]
2. For i = 2..n:
    a. if x[i] > x[i-1] then
          Dec.append(Dec[i-1] - 1)
          Inc.append(x_i - Dec[i])
       else   # We must have x[i] <= x[i-1]
          Inc.append(Inc[i-1] + 1)
          Dec.append(x_i - Inc[i])

3. Create list A and B:
    A = [(i, Dec[i]) | i = 1..n]
    B = [(i, Inc[i]) | i = 1..n]
4. B = reverse(B) # Reverse B because B was in increasing order and we
                  # need both lists to be in decreasing order
5. A and B are inputs to your algorithm.
  If your algorithm can combine A and B into sorted order,
  then we have also sorted S (via argsort on the keys).

你可能还渴望得到一个证据，证明我选择将Inc增加1或将Dec减少1的特别方法是有效的。这里有一个非正式的“证明”（你可以用归纳法将其形式化）：

回想一下，在这种情况下，我们选择将Dec减少1。我们被赋予x_{i}

因为x_{i}

回想一下，在这种情况下，我们选择将Inc增加1。我们得到了x_{i}

你的问题不能比O（nlog（n））更快完成。最好是合并成一个HashMap，然后用O（nlog（n））对其元素进行排序，因为不可能找到更快的解决方案。

不过，如果你发现降价有问题或有疑问，请随时发表评论。我很确定这是正确的。当然，如果我错误地认为排序不比O（nlog（n））快，那么整个证明就不成立了，但最后我检查了一下，有人已经证明O（nlog（n））是排序最快的复杂度。如果您喜欢正式降价，请发表评论。现在对我来说已经很晚了，我跳过了一些“形式化”，但我可以在有机会的时候编辑它们。

如果您对创建缩减的算法进行编码，您可能会获得更好的理解。

另外：如果您想解释排序时绑定的O（nlog（n）），请参阅这篇文章排序算法的“Ω（n log n）屏障”的规则是什么？

Answer 3

听起来您需要使用自适应排序算法。

“如果一个排序算法利用了其输入中的现有顺序，它就属于自适应排序家族。它受益于输入序列中的预排序——或者对于各种无序度的定义，有有限的无序度——并且排序更快。自适应排序通常通过修改现有排序算法来执行。”-上面链接了维基百科的文章。

示例包括插入排序和Timsort；更多信息请参见上面的文章。注意，在Java8中，数组。sort（Object[]）library方法使用修改后的Timsort。

我不知道有任何已发布的算法可以处理您的示例的特定要求，但这里有一个想法：

>

对两个输入列表L1和L2执行经典合并：

• 当您合并一对对象并更改决定排序的键时，将合并的对象放入临时列表A中。
• 否则将对象放入临时列表B...这将保持有序。

对临时列表A进行排序。

合并列表A和B。

假设：

• 原始列表的长度为L1

那么总体复杂度是O（mn RlogR）。如果R相对于mn很小，那么这应该是一个改进。

在您的示例中，输入列表中元素之间存在匹配的每种情况都可能会按顺序移动元素。如果它移动元素，它将按顺序移动到后面（而不是更早）。所以另一个想法是在原始2个列表和优先级队列之间进行三方合并。当您获得匹配项时，您将合并计数并将结果添加到优先级队列中。

其复杂性与前一个类似，但可以避免额外的过程来合并列表。而且RlogR变成RlogA，其中A是优先级队列的平均大小。

请记住，我特别感兴趣的是R大约等于max（m，N），并且m==N的情况。

（你在问题中没有说明这一点！事实上，R是没有任何意义的。）

在这种情况下，可以将优先级队列用作增量分类器。抛出所有合并的记录和无法合并到队列中的所有记录，如果记录的密钥/分数小于两个列表的当前头，则拉取我们的记录。假设M和N是列表长度，A是平均优先级队列大小，那么复杂性是max（M，N）*loga）。这是否是对简单重新排序的改进，将取决于平均值A是否显著（以大O为单位）小于最大值（M，N）。这将取决于输入。。。以及合并功能。

数字（N）各不相同，但256到1000是典型的。也许多达10,000。

对于这种典型规模的列表，您的复杂度分析将毫无帮助。但同时，你正处于一个优化变得毫无意义的阶段。。。除非你做了很多次手术，或者时间紧。

这些都是非常近似的，我的数学充其量只是“粗略的”。

一项适当的调查需要数百小时来研究、编码、测试、基准测试、分析各种备选方案。。。我们可能仍然会得到答案，这取决于输入数据集的大小和分布。