algorithm - code - recursive merge sort

Code golf: combina múltiples listas ordenadas en una sola lista ordenada

Question

Implemente un algoritmo para fusionar una cantidad arbitraria de listas ordenadas en una lista ordenada. El objetivo es crear el programa de trabajo más pequeño, en el idioma que desee.

Por ejemplo:

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)

Nota : las soluciones que concatenan las listas de entrada y luego usan una función de ordenamiento proporcionada por el idioma no concuerdan con el espíritu del golf y no serán aceptadas:

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

¡Aparte de todo lo demás, tu algoritmo debería ser (pero no necesariamente) mucho más rápido!

Indique claramente el idioma, las deficiencias y el recuento de caracteres. Solo incluya personajes significativos en el recuento, pero no dude en agregar espacios en blanco al código con fines artísticos o de legibilidad.

Para mantener las cosas ordenadas, sugiera mejoras en los comentarios o edite las respuestas cuando corresponda, en lugar de crear una nueva respuesta para cada "revisión".

EDITAR : si volviera a enviar esta pregunta, ampliaría la regla "ordenar sin idioma" para que sea "no concatenar todas las listas y luego ordenar el resultado". Las entradas existentes que concatenan-luego-ordenar son en realidad muy interesantes y compactas, por lo que no introduciré retroactivamente una regla que rompan, pero pueden trabajar con las especificaciones más restrictivas en las nuevas presentaciones.

Inspirado por la combinación de dos listas ordenadas en Python

Answer 1

Aunque no he tenido la paciencia para probar esto, un colega mío me mostró una manera de hacerlo con la tecla 0 - Whie Space

Answer 2

Sólo dejaré esto aquí...

Idioma: C, Número de caracteres: 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("");}

Toma entrada como tal:

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

Answer 3

reenviado

Python - 74 caracteres (contando espacios en blanco y líneas nuevas)

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

i se ingresa como lista de listas

Uso:

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

Answer 4

Haskell: 127 caracteres (sin sangría y nuevas líneas)

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

Básicamente, se generaliza la fusión de dos listas.

Answer 5

Ruby: 100 caracteres (1 espacio en blanco significativo, 4 líneas nuevas importantes)

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

Versión humana:

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

Esto solo puede ser reemplazado por numbers.flatten.sort

Puntos de referencia:

 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

Produce:

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

Entonces mi algoritmo funciona horriblemente, ¡oye!

Answer 6

(todas las demás soluciones son O (N) (para la entrada proporcionada))

Si permitimos que N sea el número de elementos en la salida yk el número de listas de entrada, entonces no puede hacer más rápido que O (N log k) - supongamos que cada lista era solo un elemento, y usted tener una clasificación basada en la comparación más rápida que la O (N log N).

Los que he visto se ven más como si fueran O (N * k).

Puede llegar fácilmente al tiempo O (N log k): simplemente ponga las listas en un montón. Esta es una de las maneras de hacer una clasificación eficiente de E / S (también puede generalizar quicksort y heaps / heapsort).

[sin código, solo comentario]

Answer 7

Rubí:

41 caracteres significativos, 3 caracteres de espacio en blanco significativos en el cuerpo del método de combinación.

arrs es una matriz de matrices

def merge_sort(arrs)
o = Array.new
arrs.each do |a|
o = o | a
end
o.sort!
end

Para probar en irb:

arrs = [ [ 90, 4, -2 ], [ 5, 6, -100 ], [ 5, 7, 2 ] ]
merge_sort(arrs)

Devuelve: [-100, -2, 2, 4, 5, 6, 7, 90]

Editar: usó el idioma provisto merge / sort porque probablemente está respaldado por código C y cumple con el requisito ''más rápido''. Pensaré en la solución sin más tarde (es el fin de semana aquí y estoy de vacaciones).

Answer 8

VB generalmente no es el idioma de elección para el golf de código, pero aquí va de todos modos.

La puesta en marcha -

Dim m1 As List(Of Integer) = New List(Of Integer)
Dim m2 As List(Of Integer) = New List(Of Integer)
Dim m3 As List(Of Integer) = New List(Of Integer)
Dim m4 As List(Of Integer) = New List(Of Integer)
m1.Add(1)
m1.Add(2)
m1.Add(3)
m2.Add(4)
m2.Add(5)
m2.Add(6)
m3.Add(7)
m3.Add(8)
m3.Add(9)
Dim m5 As List(Of List(Of Integer)) = New List(Of List(Of Integer))
m5.Add(m1)
m5.Add(m2)
m5.Add(m3)

Un intento en VB.NET (sin ordenar)

 While m5.Count > 0
Dim idx As Integer = 0
Dim min As Integer = Integer.MaxValue
For k As Integer = 0 To m5.Count - 1
If m5(k)(0) < min Then min = m5(k)(0) : idx = k
Next
m4.Add(min) : m5(idx).RemoveAt(0)
If m5(idx).Count = 0 Then m5.RemoveAt(idx)
End While

Otro intento de VB.NET (con un ordenamiento permitido )

Private Function Comp(ByVal l1 As List(Of Integer), ByVal l2 As List(Of Integer)) As Integer
Return l1(0).CompareTo(l2(0))
End Function
.
.
.
While m5.Count > 0
m5.Sort(AddressOf Comp)
m4.Add(m5(0)(0)) : m5(0).RemoveAt(0)
If m5(0).Count = 0 Then m5.RemoveAt(0)
End While

El programa completo -

 Dim rand As New Random
Dim m1 As List(Of Integer) = New List(Of Integer)
Dim m2 As List(Of Integer) = New List(Of Integer)
Dim m3 As List(Of Integer) = New List(Of Integer)
Dim m4 As List(Of Integer) = New List(Of Integer)
Dim m5 As List(Of List(Of Integer)) = New List(Of List(Of Integer))
m5.Add(m1)
m5.Add(m2)
m5.Add(m3)
For Each d As List(Of Integer) In m5
For i As Integer = 0 To 100000
d.Add(rand.Next())
Next
d.Sort()
Next
Dim sw As New Stopwatch
sw.Start()
While m5.Count > 0
Dim idx As Integer = 0
Dim min As Integer = Integer.MaxValue
For k As Integer = 0 To m5.Count - 1
If m5(k)(0) < min Then min = m5(k)(0) : idx = k
Next
m4.Add(min) : m5(idx).RemoveAt(0)
If m5(idx).Count = 0 Then m5.RemoveAt(idx)
End While
sw.Stop()
''Dim sw As New Stopwatch
''sw.Start()
''While m5.Count > 0
'' m5.Sort(AddressOf Comp)
'' m4.Add(m5(0)(0)) : m5(0).RemoveAt(0)
'' If m5(0).Count = 0 Then m5.RemoveAt(0)
''End While
''sw.Stop()
Console.WriteLine(sw.Elapsed)
Console.ReadLine()

Answer 9

DO#

static void f(params int[][] b)
{
var l = new List<int>();
foreach(var a in b)l.AddRange(a);
l.OrderBy(i=>i).ToList().ForEach(Console.WriteLine);
}
static void Main()
{
f(new int[] { 1, 4, 7 },
new int[] { 2, 5, 8 },
new int[] { 3, 6, 9 });
}

Answer 10

VB

La puesta en marcha:

Sub Main()
f(New Int32() {1, 4, 7}, _
New Int32() {2, 5, 8}, _
New Int32() {3, 6, 9})
End Sub

La salida:

Sub f(ByVal ParamArray b As Int32()())
Dim l = New List(Of Int32)
For Each a In b
l.AddRange(a)
Next
For Each a In l.OrderBy(Function(i) i)
Console.WriteLine(a)
Next
End Sub

Answer 11

Perl: 22 caracteres, incluidos dos espacios en blanco significativos.

sub a{sort map{@$_}@_}

Solo construcciones aquí. ¿Ver? ;)

Llamar así:

my @sorted = a([1, 2, 3], [5, 6, 89], [13, -1, 3]);
print "@sorted" # prints -1, 1, 1, 2, 3, 3, 5, 6, 89

Honestamente, negar las características del lenguaje (nota: no bibliotecas ...) parece una especie de contra-punto. El código más corto para implementar en un idioma debe incluir características de compilación / lenguaje. Por supuesto, si importa un módulo, debe contar ese código con su solución.

Editar: eliminó {} innecesarios alrededor de $ _.

Answer 12

F #: 116 caracteres :

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

Nota: este código hace que F # arroje muchas advertencias, pero funciona :)

Aquí está la versión anotada con espacios en blanco e identificadores significativos (nota: el código anterior no usa la sintaxis #light, el código a continuación sí lo hace):

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

Answer 13

Aunque podría romper las reglas. Aquí hay una entrada agradable y corta de c ++ :

13 personajes

l1.merge(l2); // Removes the elements from the argument list, inserts
// them into the target list, and orders the new, combined
// set of elements in ascending order or in some other
// specified order.

Answer 14

OCaml en 42 caracteres:

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

Creo que debería obtener crédito extra por 42 exactamente?

Answer 15

Python, 181 caracteres

from heapq import *
def m(l):
r=[]
h=[]
for x in l:
if x:
heappush(h, (x[0], x[1:]))
while h:
e,f=heappop(h)
r.append(e)
if f:
heappush(h, (f.pop(0),f))
return r

Esto se ejecuta en O (NlgM) tiempo, donde N es el número total de elementos y M es el número de listas.

Answer 16

Common Lisp ya tiene una función de merge para secuencias generales en el estándar de lenguaje, pero solo funciona en dos secuencias. Para múltiples listas de números ordenados de forma ascendente, se puede usar en la siguiente función (97 caracteres esenciales).

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

editar : volver a visitar después de un tiempo: esto se puede hacer en una línea:

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

Esto tiene 79 personajes esenciales con nombres significativos, reduciéndolos a una sola letra, sale a 61:

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

Answer 17

Guiones del sistema GNU (supongo que es una trampa, pero también es bueno saberlo).

sort -m file1 file2 file3 ...

Answer 18

Implementación en C a través de listas enlazadas.

http://datastructuresandalgorithmsolutions.blogspot.com/2010/02/chapter-2-basic-abstract-data-types_7147.html

Answer 19

Javascript

function merge(a) {
var r=[], p;
while(a.length>0) {
for (var i=0,j=0; i<a.length && p!=a[j][0]; i++)
if (a[i][0]<a[j][0])
j = i;
r.push(p = a[j].shift());
if (!a[j].length)
a.splice(j, 1);
}
return r;
}

Prueba:

var arr = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]​;
alert(merge(arr));

Answer 20

BASH en aproximadamente 250 caracteres esenciales

BASH no es realmente bueno en la manipulación de listas, de todos modos, este es el trabajo.

# This merges two lists together
m(){
[[ -z $1 ]] && echo $2 && return;
[[ -z $2 ]] && echo $1 && return;
A=($1); B=($2);
if (( ${A[0]} > ${B[0]} ));then
echo -n ${B[0]}/ ;
unset B[0];
else
echo -n ${A[0]}/ ;
unset A[0];
fi;
m "${A[*]}" "${B[*]}";
}
# This merges multiple lists
M(){
A=$1;
shift;
for x in $@; do
A=`m "$A" "$x"`
done
echo $A
}
$ M ''1 4 7'' ''2 5 8'' ''3 6 9''
1 2 3 4 5 6 7 8 9

Answer 21

VB.NET (2008) 185 caracteres

Lista de aceptaciones (de lista (de byte))

Function s(i)
s=New List(Of Byte)
Dim m,c
Dim N=Nothing
Do
m=N
For Each l In i:
If l.Count AndAlso(l(0)<m Or m=N)Then m=l(0):c=l
Next
If m<>N Then s.Add(m):c.Remove(m)
Loop Until m=N
End Function

Answer 22

F #, 32 caracteres

let f x=List.sort(List.concat x)

Y sin usar una función incorporada para el concat (57 caracteres):

let f x=List.sort(Seq.toList(seq{for l in x do yield!l}))

Answer 23

Python, 107 caracteres:

def f(l):
n=[]
for t in l:
for i in t: n+=[t]
s=[]
while n: s.+=[min(n)]; n.remove(min(n))
return s

Answer 24

Haskell like (158, pero se pudieron eliminar más de 24 espacios):

mm = foldl1 m where
m [] b = b
m a [] = a
m (a:as) (b:bs)
| a <= b = a : m as (b:bs)
| true = b : m (a:as) bs

Answer 25

No creo que puedas obtener mucho mejor que la respuesta de @Sykora , aquí , para Python.

Modificado para manejar tus entradas:

import heapq
def m(i):
return list(heapq.merge(*i))
print m(((1, 4, 7), (2, 5, 8), (3, 6, 9)))

Para la función real, 59 caracteres o el 52 en versión reducida:

import heapq
def m(i): return list(heapq.merge(*i))

Esto también tiene el beneficio de usar una implementación verdadera y probada incorporada en Python

Editar: eliminó los puntos y comas (gracias @Douglas ).

Answer 26

Python: 113 caracteres

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]

EDITAR: al ver que se habla de rendimiento en algunos lugares, mencionaré que creo que esta es una implementación bastante eficiente, especialmente a medida que crecen las listas. Ejecuté tres algoritmos en 10 listas de números aleatorios ordenados:

• mi solución ( Merge )
• sorted(sum(lists, [])) ( incorporado )
• La solución de Deestan que ordenó de una manera diferente ( Reimplementar )

EDICION 2: (JFS)

Las etiquetas de la figura:

• merge_26 - heapq.merge() desde Python 2.6 stdlib
• merge_alabaster : el código anterior (etiquetado Merge en la figura anterior)
• sort_builtin - L = sum(lists,[]); L.sort() L = sum(lists,[]); L.sort()
• La solución de Deestan es O (N ** 2) por lo que se excluye de la comparación (todas las demás soluciones son O (N) (para la entrada proporcionada))

Los datos de entrada son [f(N) for _ in range(10)] , donde f() es:

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

NOTA: merge_alabaster() no funciona para N > 100 debido a RuntimeError: "maximum recursion depth exceeded" .

Para obtener los scripts de Python que generaron esta figura , escriba:

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

Conclusión: para listas razonablemente grandes, el tipo incorporado muestra un comportamiento lineal cercano y es el más rápido.