algorithm - code - recursive merge sort
Code golf: combina múltiples listas ordenadas en una sola lista ordenada (26)
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
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
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)
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]
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.
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!
(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]
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).
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()
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 });
}
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
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 $ _.
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
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.
OCaml en 42 caracteres:
let f=List.fold_left(List.merge compare)[]
Creo que debería obtener crédito extra por 42 exactamente?
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.
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))
Guiones del sistema GNU (supongo que es una trampa, pero también es bueno saberlo).
sort -m file1 file2 file3 ...
Implementación en C a través de listas enlazadas.
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));
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
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
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}))
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
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
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 ).
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 (etiquetadoMergeen 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.