python-3.x - recursive - mergesort c++ ejemplo

Mergestort Python

Question

No pude encontrar ningún código de mergesort Python 3.3 en funcionamiento, así que hice 1 yo mismo. ¿Hay alguna forma de acelerarlo? Clasifica 20000 números en aproximadamente 0.3-0.5 segundos

def msort(x):
result = []
if len(x) < 2:
return x
mid = int(len(x)/2)
y = msort(x[:mid])
z = msort(x[mid:])
while (len(y) > 0) or (len(z) > 0):
if len(y) > 0 and len(z) > 0:
if y[0] > z[0]:
result.append(z[0])
z.pop(0)
else:
result.append(y[0])
y.pop(0)
elif len(z) > 0:
for i in z:
result.append(i)
z.pop(0)
else:
for i in y:
result.append(i)
y.pop(0)
return result

Answer 1

Aquí está la implementación de CLRS :

def merge(arr, p, q, r):
n1 = q - p + 1
n2 = r - q
right, left = [], []
for i in range(n1):
left.append(arr[p + i])
for j in range(n2):
right.append(arr[q + j + 1])
left.append(float(''inf''))
right.append(float(''inf''))
i = j = 0
for k in range(p, r + 1):
if left[i] <= right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
def merge_sort(arr, p, r):
if p < r:
q = (p + r) // 2
merge_sort(arr, p, q)
merge_sort(arr, q + 1, r)
merge(arr, p, q, r)
if __name__ == ''__main__'':
test = [5, 2, 4, 7, 1, 3, 2, 6]
merge_sort(test, 0, len(test) - 1)
print test

Resultado:

[1, 2, 2, 3, 4, 5, 6, 7]

Answer 2

Bucles como este probablemente se puedan acelerar:

for i in z:
result.append(i)
z.pop(0)

En cambio, simplemente haz esto:

result.extend(z)

Tenga en cuenta que no es necesario limpiar el contenido de z porque de todos modos no lo usará.

Answer 3

Como ya se dijo, l.pop(0) es una operación O (len (l)) y debe evitarse, la función msort anterior es O (n ** 2). Si la eficiencia es importante, la indexación es mejor, pero también ha costado. El for x in l es más rápido pero no fácil de implementar para mergesort: iter se puede usar en su lugar aquí. Finalmente, verificar i < len(l) se realiza dos veces porque se volvió a probar al acceder al elemento: el mecanismo de excepción (try except) es mejor y proporciona una última mejora del 30%.

def msort(l):
if len(l)>1:
t=len(l)//2
it1=iter(msort(l[:t]));x1=next(it1)
it2=iter(msort(l[t:]));x2=next(it2)
l=[]
try:
while True:
if x1<=x2: l.append(x1);x1=next(it1)
else : l.append(x2);x2=next(it2)
except:
if x1<=x2: l.append(x2);l.extend(it2)
else: l.append(x1);l.extend(it1)
return l

Answer 4

La primera mejora sería simplificar los tres casos en el ciclo principal: en lugar de iterar mientras que parte de la secuencia tiene elementos, itere mientras ambas secuencias tienen elementos. Al salir del ciclo, uno de ellos estará vacío, no sabemos cuál, pero no nos importa: los añadimos al final del resultado.

def msort2(x):
if len(x) < 2:
return x
result = [] # moved!
mid = int(len(x) / 2)
y = msort2(x[:mid])
z = msort2(x[mid:])
while (len(y) > 0) and (len(z) > 0):
if y[0] > z[0]:
result.append(z[0])
z.pop(0)
else:
result.append(y[0])
y.pop(0)
result += y
result += z
return result

La segunda optimización es evitar hacer ping a los elementos. Por el contrario, tiene dos índices:

def msort3(x):
result = []
if len(x) < 2:
return x
mid = int(len(x) / 2)
y = msort3(x[:mid])
z = msort3(x[mid:])
i = 0
j = 0
while i < len(y) and j < len(z):
if y[i] > z[j]:
result.append(z[j])
j += 1
else:
result.append(y[i])
i += 1
result += y[i:]
result += z[j:]
return result

Una mejora final consiste en utilizar un algoritmo no recursivo para ordenar secuencias cortas. En este caso, uso la función sorted incorporada y la uso cuando el tamaño de la entrada es menor a 20:

def msort4(x):
result = []
if len(x) < 20:
return sorted(x)
mid = int(len(x) / 2)
y = msort4(x[:mid])
z = msort4(x[mid:])
i = 0
j = 0
while i < len(y) and j < len(z):
if y[i] > z[j]:
result.append(z[j])
j += 1
else:
result.append(y[i])
i += 1
result += y[i:]
result += z[j:]
return result

Mis mediciones para ordenar una lista aleatoria de 100000 enteros son 2,46 segundos para la versión original, 2,33 para msort2, 0,60 para msort3 y 0,40 para msort4. Como referencia, ordenando toda la lista con tomas sorted 0.03 segundos.

Answer 5

Prueba esta versión recursiva

def mergeList(l1,l2):
l3=[]
Tlen=len(l1)+len(l2)
inf= float("inf")
for i in range(Tlen):
print "l1= ",l1[0]," l2= ",l2[0]
if l1[0]<=l2[0]:
l3.append(l1[0])
del l1[0]
l1.append(inf)
else:
l3.append(l2[0])
del l2[0]
l2.append(inf)
return l3
def main():
l1=[2,10,7,6,8]
print mergeSort(breaklist(l1))
def breaklist(rawlist):
newlist=[]
for atom in rawlist:
print atom
list_atom=[atom]
newlist.append(list_atom)
return newlist
def mergeSort(inputList):
listlen=len(inputList)
if listlen ==1:
return inputList
else:
newlist=[]
if listlen % 2==0:
for i in range(listlen/2):
newlist.append(mergeList(inputList[2*i],inputList[2*i+1]))
else:
for i in range((listlen+1)/2):
if 2*i+1<listlen:
newlist.append(mergeList(inputList[2*i],inputList[2*i+1]))
else:
newlist.append(inputList[2*i])
return mergeSort(newlist)
if __name__ == ''__main__'':
main()

Answer 6

Puede inicializar la lista de resultados completa en la llamada de nivel superior a mergesort:

result = [0]*len(x) # replace 0 with a suitable default element if necessary.
# or just copy x (result = x[:])

Luego, para las llamadas recursivas, puede usar una función auxiliar a la que pase no sublistas, sino índices en x . Y las llamadas de nivel inferior leen sus valores de x escriben en el result directamente.

De esa forma puede evitar todo lo que aparezca y append , lo que debería mejorar el rendimiento.

Answer 7

Si cambias tu código así, estará funcionando.

def merge_sort(arr):
if len(arr) < 2:
return arr[:]
middle_of_arr = len(arr) / 2
left = arr[0:middle_of_arr]
right = arr[middle_of_arr:]
left_side = merge_sort(left)
right_side = merge_sort(right)
return merge(left_side, right_side)
def merge(left_side, right_side):
result = []
while len(left_side) > 0 or len(right_side) > 0:
if len(left_side) > 0 and len(right_side) > 0:
if left_side[0] <= right_side[0]:
result.append(left_side.pop(0))
else:
result.append(right_side.pop(0))
elif len(left_side) > 0:
result.append(left_side.pop(0))
elif len(right_side) > 0:
result.append(right_side.pop(0))
return result
arr = [6, 5, 4, 3, 2, 1]
# print merge_sort(arr)
# [1, 2, 3, 4, 5, 6]

Answer 8

Toma mi implementación

def merge_sort(sequence):
if len(sequence) < 2:
return sequence
m = len(sequence) / 2
return merge(merge_sort(sequence[:m]), merge_sort(sequence[m:]))
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
print merge_sort([5, 2, 6, 8, 5, 8, 1])

Answer 9

Un poco tarde en la fiesta, pero pensé que pondría mi sombrero en el ring ya que mi solución parece funcionar más rápido que OP (en mi máquina, de todos modos):

# [Python 3]
def merge_sort(arr):
if len(arr) < 2:
return arr
half = len(arr) // 2
left = merge_sort(arr[:half])
right = merge_sort(arr[half:])
out = []
li = ri = 0 # index of next element from left, right halves
while True:
if li >= len(left): # left half is exhausted
out.extend(right[ri:])
break
if ri >= len(right): # right half is exhausted
out.extend(left[li:])
break
if left[li] < right[ri]:
out.append(left[li])
li += 1
else:
out.append(right[ri])
ri += 1
return out

Esto no tiene ningún pop() lento, y una vez que se agota una de las medias matrices, inmediatamente extiende la otra a la matriz de salida en lugar de comenzar un nuevo ciclo.

Sé que depende de la máquina, pero para 100.000 elementos aleatorios (por encima de merge_sort() frente a Python incorporado sorted() ):

merge sort: 1.03605 seconds
Python sort: 0.045 seconds
Ratio merge / Python sort: 23.0229

Answer 10

Una más larga que cuenta inversiones y se adhiere a la interfaz sorted . Es trivial modificar esto para convertirlo en un método de un objeto que se ordena en su lugar.

import operator
class MergeSorted:
def __init__(self):
self.inversions = 0
def __call__(self, l, key=None, reverse=False):
self.inversions = 0
if key is None:
self.key = lambda x: x
else:
self.key = key
if reverse:
self.compare = operator.gt
else:
self.compare = operator.lt
dest = list(l)
working = [0] * len(l)
self.inversions = self._merge_sort(dest, working, 0, len(dest))
return dest
def _merge_sort(self, dest, working, low, high):
if low < high - 1:
mid = (low + high) // 2
x = self._merge_sort(dest, working, low, mid)
y = self._merge_sort(dest, working, mid, high)
z = self._merge(dest, working, low, mid, high)
return (x + y + z)
else:
return 0
def _merge(self, dest, working, low, mid, high):
i = 0
j = 0
inversions = 0
while (low + i < mid) and (mid + j < high):
if self.compare(self.key(dest[low + i]), self.key(dest[mid + j])):
working[low + i + j] = dest[low + i]
i += 1
else:
working[low + i + j] = dest[mid + j]
inversions += (mid - (low + i))
j += 1
while low + i < mid:
working[low + i + j] = dest[low + i]
i += 1
while mid + j < high:
working[low + i + j] = dest[mid + j]
j += 1
for k in range(low, high):
dest[k] = working[k]
return inversions
msorted = MergeSorted()

Usos

>>> l = [5, 2, 3, 1, 4]
>>> s = msorted(l)
>>> s
[1, 2, 3, 4, 5]
>>> msorted.inversions
6
>>> l = [''e'', ''b'', ''c'', ''a'', ''d'']
>>> d = {''a'': 10,
... ''b'': 4,
... ''c'': 2,
... ''d'': 5,
... ''e'': 9}
>>> key = lambda x: d[x]
>>> s = msorted(l, key=key)
>>> s
[''c'', ''b'', ''d'', ''e'', ''a'']
>>> msorted.inversions
5
>>> l = [5, 2, 3, 1, 4]
>>> s = msorted(l, reverse=True)
>>> s
[5, 4, 3, 2, 1]
>>> msorted.inversions
4
>>> l = [''e'', ''b'', ''c'', ''a'', ''d'']
>>> d = {''a'': 10,
... ''b'': 4,
... ''c'': 2,
... ''d'': 5,
... ''e'': 9}
>>> key = lambda x: d[x]
>>> s = msorted(l, key=key, reverse=True)
>>> s
[''a'', ''e'', ''d'', ''b'', ''c'']
>>> msorted.inversions
5

Answer 11

aquí hay otra solución

class MergeSort(object):
def _merge(self,left, right):
nl = len(left)
nr = len(right)
result = [0]*(nl+nr)
i=0
j=0
for k in range(len(result)):
if nl>i and nr>j:
if left[i] <= right[j]:
result[k]=left[i]
i+=1
else:
result[k]=right[j]
j+=1
elif nl==i:
result[k] = right[j]
j+=1
else: #nr>j:
result[k] = left[i]
i+=1
return result
def sort(self,arr):
n = len(arr)
if n<=1:
return arr
left = self.sort(arr[:n/2])
right = self.sort(arr[n/2:] )
return self._merge(left, right)
def main():
import random
a= range(100000)
random.shuffle(a)
mr_clss = MergeSort()
result = mr_clss.sort(a)
#print result
if __name__ == ''__main__'':
main()

y aquí está el tiempo de ejecución para la lista con 100000 elementos:

real 0m1.073s
user 0m1.053s
sys 0m0.017s

Answer 12

Código del curso MIT. (con el cooperador genérico)

import operator
def merge(left, right, compare):
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if compare(left[i], right[j]):
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
while i < len(left):
result.append(left[i])
i += 1
while j < len(right):
result.append(right[j])
j += 1
return result
def mergeSort(L, compare=operator.lt):
if len(L) < 2:
return L[:]
else:
middle = int(len(L) / 2)
left = mergeSort(L[:middle], compare)
right = mergeSort(L[middle:], compare)
return merge(left, right, compare)

Answer 13

 def merge(a,low,mid,high):
l=a[low:mid+1]
r=a[mid+1:high+1]
#print(l,r)
k=0;i=0;j=0;
c=[0 for i in range(low,high+1)]
while(i<len(l) and j<len(r)):
if(l[i]<=r[j]):
c[k]=(l[i])
k+=1
i+=1
else:
c[k]=(r[j])
j+=1
k+=1
while(i<len(l)):
c[k]=(l[i])
k+=1
i+=1
while(j<len(r)):
c[k]=(r[j])
k+=1
j+=1
#print(c)
a[low:high+1]=c
def mergesort(a,low,high):
if(high>low):
mid=(low+high)//2
mergesort(a,low,mid)
mergesort(a,mid+1,high)
merge(a,low,mid,high)
a=[12,8,3,2,9,0]
mergesort(a,0,len(a)-1)
print(a)

Answer 14

def merge(l1, l2, out=[]):
if l1==[]: return out+l2
if l2==[]: return out+l1
if l1[0]<l2[0]: return merge(l1[1:], l2, out+l1[0:1])
return merge(l1, l2[1:], out+l2[0:1])
def merge_sort(l): return (lambda h: l if h<1 else merge(merge_sort(l[:h]), merge_sort(l[h:])))(len(l)/2)
print(merge_sort([1,4,6,3,2,5,78,4,2,1,4,6,8]))

Answer 15

def merge(x):
if len(x) == 1:
return x
else:
mid = int(len(x) / 2)
l = merge(x[:mid])
r = merge(x[mid:])
i = j = 0
result = []
while i < len(l) and j < len(r):
if l[i] < r[j]:
result.append(l[i])
i += 1
else:
result.append(r[j])
j += 1
result += l[i:]
result += r[j:]
return result

Answer 16

def mergeSort(alist):
print("Splitting ",alist)
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i=0
j=0
k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1
while i < len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1
while j < len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",alist)
alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

Answer 17

def merge_sort(x):
if len(x) < 2:return x
result,mid = [],int(len(x)/2)
y = merge_sort(x[:mid])
z = merge_sort(x[mid:])
while (len(y) > 0) and (len(z) > 0):
if y[0] > z[0]:result.append(z.pop(0))
else:result.append(y.pop(0))
result.extend(y+z)
return result