相关疑难解决方法(0)

我有一堆排序的对象列表和一个比较函数

class Obj :
    def __init__(p) :
        self.points = p
def cmp(a, b) :
    return a.points < b.points

a = [Obj(1), Obj(3), Obj(8), ...]
b = [Obj(1), Obj(2), Obj(3), ...]
c = [Obj(100), Obj(300), Obj(800), ...]

result = magic(a, b, c)
assert result == [Obj(1), Obj(1), Obj(2), Obj(3), Obj(3), Obj(8), ...]

是什么magic样子的？我目前的实施是

def magic(*args) :
    r = []
    for a in args : r += a
    return sorted(r, cmp)

但这是非常低效的.更好的答案？

实现一种算法,将任意数量的排序列表合并为一个排序列表.目标是用您喜欢的任何语言创建最小的工作程序.

例如:

input:  ((1, 4, 7), (2, 5, 8), (3, 6, 9))
output: (1, 2, 3, 4, 5, 6, 7, 8, 9)

input:  ((1, 10), (), (2, 5, 6, 7))
output: (1, 2, 5, 6, 7, 10)

注意:连接输入列表然后使用语言提供的排序功能的解决方案不符合高尔夫的精神,并且不会被接受:

sorted(sum(lists,[])) # cheating: out of bounds!

除了其他任何东西,你的算法应该(但不一定)快得多!

清楚地说明语言,任何缺点和字符数.只在计数中包含有意义的字符,但可以随意为代码添加空格以用于艺术/可读性目的.

为了保持整洁,建议改进评论或在适当的时候编辑答案,而不是为每个"修订"创建新的答案.

编辑:如果我再次提交这个问题,我会扩展"无语言提供排序"规则为"不连接所有列表然后排序结果".连接然后排序的现有条目实际上非常有趣和紧凑,因此我不会回溯地引入它们中断的规则,而是可以自由地在新提交中使用更严格的规范.

灵感来自于在Python中组合两个排序列表

我的一个朋友通过了我最近得到的一个面试问题,我对解决方案的态度不太满意.问题如下:

• 你有两个清单.
• 每个列表将包含长度为2的列表,其表示范围(即,[3,5]表示范围从3到5,包括3和5).
• 您需要返回集合之间所有范围的交集.如果我给你[1,5]和[0,2],结果将是[1,2].
• 在每个列表中,范围将始终增加并且从不重叠(即,[[0,2],[5,10] ...]永远不会[[0,2],[2,5] ......] )

一般而言,在列表的排序或重叠方面没有"陷阱".

例:

a = [[0, 2], [5, 10], [13, 23], [24, 25]]
b = [[1, 5], [8, 12], [15, 18], [20, 24]]

预期产量: [[1, 2], [5, 5], [8, 10], [15, 18], [20, 24]]

我的懒惰解决方案涉及将范围列表扩展为整数列表,然后执行集合交集,如下所示:

def get_intersection(x, y):
    x_spread = [item for sublist in [list(range(l[0],l[1]+1)) for l in x] for item in sublist]
    y_spread = [item for sublist in [list(range(l[0],l[1]+1)) for l in y] for item in sublist]
    flat_intersect_list = list(set(x_spread).intersection(y_spread))
...

但我想有一个既可读也有效的解决方案. …

在尝试回答什么是从Python中的多个列表组成集合的首选方法时,我做了一些性能分析,并得出了一个有些令人惊讶的结论.

运用

python -m timeit -s '
import itertools
import random
n=1000000
random.seed(0)
A = [random.randrange(1<<30) for _ in xrange(n)]
B = [random.randrange(1<<30) for _ in xrange(n)]
C = [random.randrange(1<<30) for _ in xrange(n)]'

为了安装,我计时了以下片段:

> $TIMEIT 'set(A+B+C)'
10 loops, best of 3: 872 msec per loop

> $TIMEIT 's = set(A); s.update(B); s.update(C)'
10 loops, best of 3: 930 msec per loop

> $TIMEIT 's = set(itertools.chain(A,B,C))'
10 loops, best of 3: 941 msec per loop

令我惊讶的 …

来自Google的Python类:

E. Given two lists sorted in increasing order, create and return a merged
list of all the elements in sorted order. You may modify the passed in lists.
Ideally, the solution should work in "linear" time, making a single
pass of both lists.

这是我的解决方案:

def linear_merge(list1, list2):
  merged_list = []
  i = 0
  j = 0

  while True:
    if i == len(list1):
        return merged_list + list2[j:]
    if j == len(list2):
        return merged_list + list1[i:]

    if list1[i] <= list2[j]:
        merged_list.append(list1[i]) …

我有几个排序列表,我想将它们一起添加到一个大的排序列表中.最有效的方法是什么？

这是我要做的,但效率太低:

big_list=[]
for slist in sorted_lists: # sorted_lists is a generator, so lists have to be added one by one
    big_list.extend(slist)
big_list.sort()

以下是sorted_lists的示例:

sorted_lists的大小= 200

sorted_lists的第一个元素的大小= 1668

sorted_lists=[
['000008.htm_181_0040_0009', '000008.htm_181_0040_0037', '000008.htm_201_0041_0031', '000008.htm_213_0029_0004', '000008.htm_263_0015_0011', '000018.htm_116_0071_0002', '000018.htm_147_0046_0002', '000018.htm_153_0038_0015', '000018.htm_160_0060_0001', '000018.htm_205_0016_0002', '000031.htm_4_0003_0001', '000032.htm_4_0003_0001', '000065.htm_5_0013_0005', '000065.htm_8_0008_0006', '000065.htm_14_0038_0036', '000065.htm_127_0016_0006', '000065.htm_168_0111_0056', '000072.htm_97_0016_0012', '000072.htm_175_0028_0020', '000072.htm_188_0035_0004'….],
['000018.htm_68_0039_0030', '000018.htm_173_0038_0029', '000018.htm_179_0042_0040', '000018.htm_180_0054_0021', '000018.htm_180_0054_0031', '000018.htm_182_0025_0023', '000018.htm_191_0041_0010', '000065.htm_5_0013_0007', '000072.htm_11_0008_0002', '000072.htm_14_0015_0002', '000072.htm_75_0040_0021', '000079.htm_11_0005_0000', '000079.htm_14_0006_0000', '000079.htm_16_0054_0006', '000079.htm_61_0018_0012', '000079.htm_154_0027_0011', '000086.htm_8_0003_0000', '000086.htm_9_0030_0005', '000086.htm_11_0038_0004', '000086.htm_34_0031_0024'….],
['000001.htm_13_0037_0004', '000008.htm_48_0025_0006', '000008.htm_68_0025_0008', '000008.htm_73_0024_0014', '000008.htm_122_0034_0026', '000008.htm_124_0016_0005', '000008.htm_144_0046_0030', '000059.htm_99_0022_0012', '000065.htm_69_0045_0017', '000065.htm_383_0026_0020', '000072.htm_164_0030_0002', …