排序对要更连续

我有一套配对项目：[(a0,b0),(a1,b1),(a2,b2),...(aN,bN)]。这些对形成一组运行。例如，可能是b4=a1和b1=a6，因此4,1,6是运行。所有的a s，和所有的b s，都是独一无二的，所以运行永远不会含糊不清。请注意，一些运行将是长度1.排序对要更连续

我想排列这样的运行是连续的。在排列组中，对于任何j，应该是aj=b(j+1)或aj不等于任何b的情况。我不在乎排列的任何其他方面，并且运行可以以相对于彼此的任何顺序出现。

例如：设定[(5,2),(0,3),(1,0),(7,4),(6,5),(3,8)]包含运行4,0（(6,5)和(5,2)）2,1,5（(1,0)，(0,3)，和(3,8)），和3。所以有效的排列是[(6,5),(5,2),(1,0),(0,3),(3,8),(7,4)]。

显然有一个简单的O(n log n)时间和空间O(n)溶液：

排序b阵列对。
对于每一对的a，在阵列上执行二进制搜索以匹配b。记录与b不匹配的所有a;这些将是运行的开始。
对a对数组进行排序。
对于每个运行起始点a，首先通过二进制搜索匹配a的对，然后在a之间通过二进制搜索该对b等，直到运行结束。

渐近地说，这可能和我们不用散列一样好。然而从实际的角度来看，我并不完全开心。它涉及两种不同的类型和二进制搜索。这是相当麻烦的。这段代码处于一个极端的内部循环中（是的，我已经进行了剖析），并将对整个系统的性能产生重大影响。

还有什么其他的方法值得思考吗？

来源

2014-11-24 Sneftel

值的密度/紧凑程度如何，即通过使用数组索引元组会浪费多少空间？ – 2014-11-24 15:47:33

@ Zim-ZamO'Pootertoot根本不紧凑。这些项目是128位或256位，但N一般不会大于30. – Sneftel 2014-11-24 15:54:06

对于30个项目，O（n^2）算法是眨眼 – 2014-11-25 18:45:11

我们至少可以取消二进制搜索。使用指向链接列表节点的指针（本例中的字母）装饰每对，然后按第二个数字排序并分别按第一个数字排序。

[(5,2,a),(0,3,b),(1,0,c),(7,4,d),(6,5,e),(3,8,f)] # unsorted 
[(1,0,c),(5,2,a),(0,3,b),(7,4,d),(6,5,e),(3,8,f)] # second number 
[(0,3,b),(1,0,c),(3,8,f),(5,2,a),(6,5,e),(7,4,d)] # first number

现在做一个修改后的排序合并。

(1,0,c) (0,3,b): case =; set c->next = b 
(5,2,a) (1,0,c): case >; c is a list head 
(5,2,a) (3,8,f): case < 
(0,3,b) (3,8,f): case =; set b->next = f 
(7,4,d) (5,2,a): case < 
(6,5,e) (5,2,a): case =; set e->next = a 
(3,8,f) (6,5,e): case >; e is a list head 
(3,8,f) (7,4,d): case >; d is a list head

链表结构看起来像

c->b->f 
d 
e->a,

，我们可以一起主食。

来源

2014-11-24 16:13:29

啊，非常优雅。 – Sneftel 2014-11-25 10:09:44

你能否澄清你如何将每一对分类到每个案例？它似乎是比较第一个B和第二个A？ '0 = 0，2> 1，2 <3，3 = 3，4 <5, 5=5, 8> 6，8> 7'我不得不想一会儿说服自己适用于所有套餐。 – 2014-11-25 18:51:34

@MooingDuck是的，它是比较排序键。 – 2014-11-25 18:53:22

可以提高平均运行时间不使用哈希表使用太多额外的空间：每个元组添加到使用b为重点的哈希表，然后通过每个元组进行迭代，并看看它a匹配的b有已在表格中编入索引。除了索引b在预期的线性时间内运行（而不是最差情况下的n log n）之外，这与您的算法几乎完全相同，并且二分查找被替换为已查询的恒定时间查找。

我假设你不使用散列的原因是散列函数可能是昂贵的，散列冲突会损害性能。另一种方法是使用类似于radix tree而不是哈希表，这将提供更一致的结果。考虑到你有很大的密钥并且不是很多，你可以使用大的基数（例如32位）来保持常数因子很小。

来源

2014-11-24 16:07:57

如果索引取自有限集合，则有O(N)解决方案。

使用所有对，使用Ai作为索引填充数组，并存储相应的Bi。

然后扫描数组，然后按照运行。

为了确保您访问每个链一次并找到运行的开始，您将添加两个标志，告诉1）该条目是否是一对的结尾，以及2）该条目已经被是否消耗。

在给定的情况下，该阵列填充有

0:*3 
1: 0 
2:*- 
3:*8 
4:*- 
5:*2 
6: 5 
7: 4 
8:*-

星号表示该项目不能开始运行。

找到以下试验：1-0-3-8,6-5-2，7-4。

如果索引范围太大而不允许数组，那么散列表是一个很好的选择。

来源

2014-11-25 18:32:08

排序对要更连续

回答

相关问题