Bee*_*ope 12 java sorting algorithm merge time-complexity
这不是经典的"合并两个排序"列表问题,这在线性时间中相当微不足道.
我要做的是合并两个(key, value)已经排序的对列表value,其中key两个列表中都有相同的对象:这些对象应该value合并(添加),这可能会改变它们的排序顺序.我主要关注的是如何使用已排序列表中的信息有效地执行排序,因为排序是此算法中最慢的部分.
我们举一个具体的例子.试想一个List的Student对象:
class Student {
final String name;
final int score;
...
}
鉴于作为输入二List<Student>排序score,我想创建新的合并学生列表,其中Student.name出现在两个列表中的任何学生(标识为)出现在最终列表中一次,其得分等于两个列表中他们的得分总和.原始列表应保持不变.
例如,
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)查找/插入结构在预期的O(1)时间内完成HashMap.我最感兴趣的是排序步骤(尽管我不排除同时进行合并和排序的解决方案).
但问题是,我如何有效地重新排序这样的列表呢？现有列表的排序明显地对合并列表中元素的最终位置施加了一些约束.例如,如果学生i在第一个列表和j第二个列表中处于位置,则他必须i + j通过分析可能具有较高分数的最大学生数量的简单参数出现在合并列表中的第一批学生中.然而,目前还不清楚这些信息是否对列表排序有用.
您可以假设,在许多情况下,在一个列表中获得高分的学生在另一个列表中获得高分.该算法应该在不是这种情况时起作用,但除了列表已经排序之外,它还为您提供了一些可能有用的分发信息.
看起来这种类型的操作对于任何类型的分布式查询+排序实现都是常见的.例如,想象一下针对分布式系统的"选择状态,计数(*)分组状态"类型的查询问题(计算每个状态中的记录数) - 自然你会得到一个排序列表(状态,计数) )对象从每个节点返回,然后您想要在reduce操作期间合并和重新排序它们.抛弃已经在分布式节点上完成的所有工作似乎很愚蠢.
我对要合并和重新排序的列表很小的情况感兴趣:通常大约256个条目.分数范围在一些情况下从0到100变化,在其他情况下变化到大约0到10,000,000.当然,考虑到元素数量很少,即使使用天真的算法,每个操作在绝对时间内也会很快 - 但执行数十亿次,它会增加.
实际上,下面的答案之一已经证明,一般来说,你不能比增加列表大小的简单排序(即将n作为组合列表大小)做得更好- 但我实际上更感兴趣多次这样做,对于固定大小的列表,具有良好的经验性能.
听起来你需要使用自适应排序算法.
"排序算法如果利用其输入中的现有顺序,则属于自适应排序族.它受益于输入序列中的预先排序 - 或者对于各种无序度量定义的有限量的无序 - 并且排序更快.排序通常通过修改现有的排序算法来执行." - 上面链接的维基百科文章.
例子包括插入排序和Timsort; 请参阅上面的文章了解更多.请注意,在Java 8中,Arrays.sort(Object[])库方法使用修改后的Timsort.
我不知道任何已发布的算法可以处理您的示例的特定要求,但这里有一个想法:
在两个输入列表L1和L2上执行经典合并:
对临时列表A进行排序
合并列表A和B.
假如说:
那么整体复杂度是O(M + N + RlogR).如果R相对于M + N较小,那么这应该是一种改进.
在您的示例中,输入列表中元素之间存在匹配的每种情况都可能会按顺序移动元素.如果它移动元素,它将移动到稍后的顺序(并且从不更早).因此,另一个想法是在原始2列表和优先级队列之间进行三向合并.获得匹配后,合并计数并将结果添加到优先级队列.
复杂性与前一个类似,但是您可以避免额外的传递来合并列表.并且A RlogR变为RlogA优先级队列的平均大小.
请记住,我特别感兴趣的是R大约等于max(M,N),并且M == N.
(你没有在你的问题中说明这一点!事实上,R对于min(M,N)没有任何意义!)
在这种情况下,可能只使用优先级队列作为增量分拣机.抛出所有合并的记录和所有无法合并到队列中的记录,并在他们的密钥/分数低于两个列表的当前头部时拉出我们的记录.假设M和N是列表长度,并且A是平均优先级队列大小,则复杂度是max(M,N)*log A).这是否是对简单重新排序的改进将取决于平均值A是否显着(以大O值表示)小于最大值(M,N).这将取决于输入......和合并功能.
数字(N)变化,但通常为256到1,000.也许多达10,000.
对于那个典型大小的列表,你的复杂性分析没有帮助.但是,如果你的优化变得毫无意义,那么你就会陷入困境......除非你在很多次,或者在紧张的"时间预算"中进行操作.
这一切都非常近似,我的数学充其量只是"粗略".
正确的调查将需要数百小时来研究,编码,测试,基准测试,分析各种替代方案......我们可能仍然得到它取决于输入数据集大小和分布的答案.
（先合并然后重新排序，）我的第一个尝试是声明排序的输入列表（半静态）优先级队列并分两个阶段进行。为了避免术语合并中的歧义，我将调用创建/更改对象来表示“公共对象”的值组合/组合；为了减少混乱，我将表示优先队列PQ。
这应该在n个对象的线性时间内工作，对于c 个“公共”对象加上O(c log c)，其中组合的对象将在组合的任何对象的位置上乱序。（......给定（识别和）组合一个（一组公共）对象的预期恒定时间（请参阅问题中有关预期O（1）的评论））
然后，恐怕这不能正确解决主要问题观点：
有没有办法利用最终键成为至少一个有序序列和“其他值”的（线性、单调）
组合？
（有很多常见的条目 - 考虑所有。）
如果组合单调地降低优先级（在示例中，添加（正）分数值会增加优先级），则在合并 PQ 时不要使用组合阶段并组合对象，这可能会减少内存和所需的时间。
否则，选择一个PQ 从中获取对象（优先级递减），以潜在地与其他对象组合。
“最坏的情况”似乎是显示没有相关性的组合对象的优先级：恐怕答案
通常是，没有。（请参阅user2570465 的明确参数的答案）
（正如BeeOnRope 指出的那样，如果可以检测和利用，选择的（序列）对象在组合中占主导地位（不利选择）实际上可能会变成一个很好的情况。）
然后，（线性，单调）组合可以预期会扭曲密钥的分布即使没有（正）相关（在问题中假设）：一定要使用（动态）PQ 实现，其中按顺序插入是最好的情况而不是最坏的情况：
首先，在数组中取一个隐式堆（元素的子元素）在索引i 处是2i和2i+1（或2i+1 & 2i+2 “不浪费元素 0”，而是更多的索引操作）：
只需将项目（分布倾向于降低优先级）附加到末尾：与父级
的预期交换次数低于 1（在没有倾斜的情况下几乎为 1）。
看起来你想要像合并排序那样进行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 = 1 + 0(即x_1 = x_1 + 0).然后,如果x_{i-1} -> x_i是增加,我从Dec中的值减去1并计算Inc中的必要值以求和x_i.如果x_{i-1} -> x_i是减少,那么我在Inc中将我的值加1,并在Dec中计算必要的值以求和x_i.我们将此算法应用于下表中的序列:
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)
然后你基本上完成了一个初始序列的argsort(按索引排序)x_i.因此,如果您比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.
我们有三个限制:
Inc[j] + Dec[j] = x_j for all j = 1..i-1正如他们的名字所暗示的那样,Dec将严格减少,Inc将严格增加.我们将保持不变性x_i = Dec[i] + Inc[i] for i = 1..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-1},我们知道Dec_{i-1} + Inc_{i-1} = x_{i-1}.我们也可以这么说(Dec_{i-1} - 1) + (Inc_{i+1} + 1) = x_{i-1}.
既然如此x_{i} > x_{i-1},我们必须拥有x_{i} >= x_{i-1} + 1.因此,x_{i} >= (Dec_{i-1} - 1) + (Inc_{i+1} + 1).因此,如果我们只将Dec递减1,我们将被迫向Inc添加至少1,因此Inc仍然严格增加.
回想一下,在这种情况下,我们选择将Inc增加1.我们得到了x_{i} <= x_{i-1},我们知道Dec_{i-1} + Inc_{i-1} = x_{i-1}.我们也可以这样说,(Dec_{i-1} - 1) + (Inc_{i+1} + 1) = x_{i-1}因为x_{i} <= x_{i-1}必须如此(Dec_{i-1} - 1) + (Inc_{i+1} + 1) <= x_{i}.因此,如果我们将1添加到Inc,我们确信必须从12月减去至少1.
你的问题不能比O(nlog(n))更快地完成.你最好只是组合成一个HashMap,然后在O(nlog(n))中对它的元素进行排序,因为找不到更快的解决方案是不可能的.
但是,如果您发现减少问题或有疑问,请随意发表评论.我很确定这是正确的.当然,如果我错误地认为排序不比O(nlog(n))快,那么整个证据就会崩溃,但最后我检查过,有人已经证明O(nlog(n))是排序最快的复杂性.评论,如果您更喜欢正式减少.对我来说现在已经很晚了,我跳过了一些"正式化",但是当我有机会时我可以编辑它们.
如果您编写用于创建缩减的算法,您可能会更好地理解.
另外:如果你想要对排序绑定的O(nlog(n))进行解释,请参阅这篇文章.排序算法的"Ω(n log n)屏障"有哪些规则？
维护一张地图，该地图映射了实际学生信息所特有的内容。
Map<String, Student> scores = new HashMap<>();
迭代所有列表并将它们放入分数映射中
for (Student s : list1) {
if (scores.containsKey(s.name)) {
scores.put(s.name, s.score + scores.get(s.name));
} else {
scores.put(s.name, s.score);
}
}
使用 Java 8 流对 EntrySet 进行排序
scores.entrySet()
.stream()
.sorted((s1, s2) -> (s2.getValue().score - s1.getValue().score)
.map(s1 -> s1.getValue())
.collect(Collectos.toList());
这还是O(N Log N)
您无法使用标准合并算法对其进行排序，因为列表包含位置不相同的名称。标准合并算法不会对同一元素处理两次。找到重复项并添加学生分数后，您需要重新排序。您打破了合并排序的前提条件，即两个列表始终按其值排序。