Код гольф: объединение нескольких отсортированных списков в один отсортированный список

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

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))))) 

edit : Повторное посещение через некоторое время: это можно сделать в одну строку:

(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 3

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, [])) ( Встроенный )
• Решение Дестана , которое отсортировано по-другому ( Повторная реализация )

РЕДАКТИРОВАТЬ 2: (JFS)

Метки рисунка:

• merge_26 - heapq.merge() из Python 2.6 stdlib
• merge_alabaster - вышеуказанный код (обозначен Merge на рисунке выше)
• sort_builtin - L = sum(lists,[]); L.sort()
• Решение Дистана - это 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 4

Рубин: 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

* повторно 1002 *

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

Это в основном обобщает объединение двух списков.

Answer 7

Я просто оставлю это здесь ...

Язык: C, Количество символов: 265

L[99][99];N;n[99];m[99];i;I;b=0;main(char t){while(scanf("%d%c",L[i]+I,&t)+1){++
I;if(t==10){n[i++]=I;I=0;}}if(I)n[i++] = I;N=i;while(b+1){b=-1;for(i=0;i<N;++i){
I=m[i];if(I-n[i])if(b<0||L[i][I]<L[b][m[b]])b=i;}if(b<0)break;printf("%d ",L[b][
m[b]]);++m[b];}puts("");}

принимает входные данные, такие как:

1 4 7
2 5 8
3 6 9
(EOF)

Answer 8

(все остальные решения - O (N) (для предоставленного ввода))

Если мы позволим N быть числом элементов в выводе и k количеством входных списков, то вы не сможете сделать это быстрее, чем O (N log k) - предположим, что каждый список был только одним элементом, у вас будет сортировка на основе сравнения быстрее, чем O (N log N).

Те, на кого я смотрел, больше похожи на O (N * k).

Вы можете довольно легко перейти к O (N log k) времени: просто поместите списки в кучу. Это один из способов эффективной сортировки ввода-вывода (можно также обобщить быструю сортировку и кучу / сортировку).

[без кода, просто комментарий]

Answer 9

Хотя у меня не хватило терпения попробовать это, мой коллега показал мне, как можно сделать это, используя клавишу 0 символов - Whie Space

Answer 10

F #: 116 символов :

let p l=
    let f a b=List.filter(a b) in
    let rec s=function[]->[]|x::y->s(f(>)x y)@[x]@s(f(<=)x y) in
    [for a in l->>a]|>s

Примечание: этот код заставляет F # выдавать много предупреждений, но это работает:)

Вот аннотированная версия с пробелами и значимыми идентификаторами (примечание: код выше не использует синтаксис #light, код ниже использует):

let golf l=
    // filters my list with a specified filter operator
    // uses built-in F# function
    // ('a -> 'b -> bool) -> 'a -> ('b list -> 'b list)
    let filter a b = List.filter(a b)

    // quicksort algorithm
    // ('a list -> 'a list)
    let rec qsort =function
        | []->[]
        | x :: y -> qsort ( filter (>) x y) @ [x] @ qsort ( filter (<=) x y)

    // flattens list
    [for a in l ->> a ] |> qsort