Code golf:将多个排序列表组合到一个排序列表中

Question

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

例如:

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中组合两个排序列表

Answer 1

OCaml有42个字符:

let f=List.fold_left(List.merge compare)[]

我想我应该得到额外的42分信用额度？

Answer 2

Python:113个字符

def m(c,l):
    try:
        c += [l[min((m[0], i) for i,m in enumerate(l) if m)[1]].pop(0)]
        return m(c,l)
    except:
        return c

# called as:
>>> m([], [[1,4], [2,6], [3,5]])
[1, 2, 3, 4, 5, 6]

编辑:在一些地方看到有关性能的讨论,我会提到我认为这是非常有效的实现,特别是随着列表的增长.我在10个排序随机数列表上运行了三种算法:

• 我的解决方案(合并)
• sorted(sum(lists, []))(内置)
• Deestan的解决方案以不同的方式排序(重新实现)

编辑 2:(JFS)

图的标签:

• merge_26- heapq.merge()来自Python 2.6 stdlib
• merge_alabaster- 上面的代码(Merge在上图中标出)
• sort_builtin - L = sum(lists,[]); L.sort()
• Deestan的解决方案是O(N**2),因此它被排除在比较之外(所有其他解决方案都是O(N)(对于提供的输入))

输入数据是[f(N) for _ in range(10)],其中f():

max_ = 2**31-1
def f(N):
    L = random.sample(xrange(max_), n)
    L.sort()
    return L
f.__name__ = "sorted_random_%d" % max_

注:merge_alabaster()不适用于工作N > 100因RuntimeError: "maximum recursion depth exceeded".

要获取生成此图的Python脚本,请键入:

$ git clone git://gist.github.com/51074.git

结论:对于相当大的列表,内置排序显示接近线性行为,并且它是最快的.

Answer 3

Common Lisp已经具有merge语言标准中的一般序列的功能,但它仅适用于两个序列.对于按升序排序的多个数字列表,可以在以下函数中使用(97个基本字符).

(defun m (&rest s)
  (if (not (cdr s))
      (car s)
      (apply #'m
             (cons (merge 'list (car s) (cadr s) #'<)
                   (cddr s))))) 

编辑:一段时间后重新访问:这可以在一行中完成:

(defun multi-merge (&rest lists)
  (reduce (lambda (a b) (merge 'list a b #'<)) lists))

这有79个基本字符,有意义的名字,减少到一个字母,它出现在61:

(defun m(&rest l)(reduce(lambda(a b)(merge 'list a b #'<))l))

Answer 4

Ruby:100个字符(1个重要的空格,4个重要的换行符)

def m(i)
  a=[]
  i.each{|s|s.each{|n|a.insert((a.index(a.select{|j|j>n}.last)||-1)+1,n)}}
  a.reverse
end

人类版本:

def sorted_join(numbers)
  sorted_numbers=[]

  numbers.each do |sub_numbers|
    sub_numbers.each do |number|
      bigger_than_me = sorted_numbers.select { |i| i > number }
      if bigger_than_me.last
        pos = sorted_numbers.index(bigger_than_me.last) + 1
      else
        pos = 0
      end

      sorted_numbers.insert(pos, number)
    end
  end

  sorted_numbers.reverse
end

这一切都可以替换为 numbers.flatten.sort

基准:

 a = [[1, 4, 7], [2, 4, 8], [3, 6, 9]]
 n = 50000
 Benchmark.bm do |b|
   b.report { n.times { m(a) } }
   b.report { n.times { a.flatten.sort } }
 end

生产:

      user     system      total        real
 2.940000   0.380000   3.320000 (  7.573263)
 0.380000   0.000000   0.380000 (  0.892291)

所以我的算法表现得非常糟糕,是的!

Answer 5

重新提交

Python - 74个字符(计算空格和换行符)

def m(i):
 y=[];x=sum(i,[])
 while x:n=min(x);y+=[n];x.remove(n)
 return y

i 作为列表列表输入

用法:

>>> m([[1,5],[6,3]])
[1, 3, 5, 6]

Answer 6

Haskell:127个字符(没有缩进和换行)

m l|all null l=[]
   |True=x:(m$a++(xs:b))
 where
   n=filter(not.null)l
   (_,min)=minimum$zip(map head n)[0..]
   (a,((x:xs):b))=splitAt min n

它基本上概括了两个列表的合并.