DjangoBB LoFi version

Полная версия: в результате выполнения кода создаются лишние списки, вложенные в друг друга

Начало » Центр помощи » в результате выполнения кода создаются лишние списки, вложенные в друг друга

1 2 3

iawrow

Авг. 26, 2015 23:22:51

здравствуйте,

пишу merge sort algorithm по статье из википедии сортировка слиянием. ту часть, где в статье внизу написано на псевдокоде.

мой код:

m = [4, 3, 5, 1, 6, 9 , 7 , 8]
def mergesort (m):
    left = []
    right = []
    result = []
    if len(m) <= 1:
        return m
    else:
        middle = len(m) / 2
        for i in range(0, middle):
            left.append(m[i])
        for i in range(middle, len(m)):
            right.append(m[i])
        left = mergesort(left)      
        right = mergesort(right)        
        result = merge(left, right)        
        return result
    
def merge(left, right):
    result = []
    while len(left) > 0 and len(right) > 0:
        if left[0] <= right[0]:
            result.append(left[0])
            left.pop(0)
        else:         
            result.append(right[0])
            right.pop(0)
    if len(left) > 0:
        result.append(left)
    if len(right) > 0:
        result.append(right)
    return result
b = mergesort(m)
print b

результат:

[1, 3, 6, 7, [4], [8], [[5]], [[[9]]]]

собственно, половина исходного массива почему то возвращается с многократно вложенными списками. интересно почему.

py.user.next

Авг. 27, 2015 02:01:44

Как-то писал mergesort():

"""Merge sort."""
 
def merge(left, right):
    """Merge two lists in ascending order."""
    lst = []
    while left and right:
        if left[0] < right[0]:
            lst.append(left.pop(0))
        else:
            lst.append(right.pop(0))
    if left:
        lst.extend(left)
    if right:
        lst.extend(right)
    return lst
 
def mergesort(lst):
    """Sort the list by merging O(n * log n)."""
    length = len(lst)
    if length >= 2:
        mid = int(length / 2)
        lst = merge(mergesort(lst[:mid]), mergesort(lst[mid:]))
    return lst

iawrow

Авг. 27, 2015 12:16:32

!!! все исправилось, когда я заменил в merge, в последних условиях, append на extend. спасибо

Isem

Авг. 27, 2015 21:27:12

Сложно придумать более неэффективную операцию, чем удаление первого элемента списка в цикле:

py.user.next
for … :
list.pop(0)

Такой merge для списков из 100 000 элементов работает примерно в 30 и более раз быстрее, к тому же не разрушает исходные списки:

def merge(a,b):
    a, b = iter(a), iter(b)
    def gen(a, b):
        vb = next(b)
        while 1:
            va = next(a)
            if va > vb: va, vb, a, b = vb, va, b, a
            yield va
    yield from gen(a, b)
    yield from a
    yield from b

py.user.next

Авг. 28, 2015 02:21:46

Isem
Такой merge для списков из 100 000 элементов работает примерно в 30 и более раз быстрее, к тому же не разрушает исходные списки:

Ты бы хоть проверил сначала.

>>> def merge(a,b):
...     a, b = iter(a), iter(b)
...     def gen(a, b):
...         vb = next(b)
...         while 1:
...             va = next(a)
...             if va > vb: va, vb, a, b = vb, va, b, a
...             yield va
...     yield from gen(a, b)
...     yield from a
...     yield from b
... 
>>> def mergesort(lst):
...     """Sort the list by merging O(n * log n)."""
...     length = len(lst)
...     if length >= 2:
...         mid = int(length / 2)
...         lst = merge(mergesort(lst[:mid]), mergesort(lst[mid:]))
...     return lst
... 
>>> mergesort([])
[]
>>> list(mergesort([3, 2, 1]))
[1]
>>> list(mergesort([4, 3, 2, 1]))
[1]
>>>

Там не только генератор возвращается на выходе (хотя нужен список), так вообще не только не сортирует, но даже неотсортированные элементы не возвращает.

Isem

Авг. 28, 2015 06:08:45

py.user.next
Там не только генератор возвращается на выходе (хотя нужен список)

В этом все и дело, что возвращается генератор, а не список (а почему, кстати, именно список, а не тьюпл, например?).

Модифицированный merge:

def merge(a,b):
    a, b = iter(a), iter(b)
    def gen(a, b):
        vb = next(b)
        try:
            while 1:
                va = next(a)
                if va > vb: va, vb, a, b = vb, va, b, a
                yield va
        except: yield vb
    yield from gen(a, b)
    yield from a
    yield from b

Ну и пресловутый mergsort:

def mergesort(lst):
    mid = len(lst) // 2
    return merge(mergesort(lst[:mid]), mergesort(lst[mid:])) if mid else lst

>>> print(*mergesort([3, 2, 1]))
1 2 3
>>> tuple(mergesort([3, 2, 1, 9, -3]))
(-3, 1, 2, 3, 9)
>>>

py.user.next

Авг. 28, 2015 06:59:44

#!/usr/bin/env python3
 
import timeit
 
def prepare1():
 
    def merge(left, right):
        """Merge two lists in ascending order."""
        lst = []
        while left and right:
            if left[0] < right[0]:
                lst.append(left.pop(0))
            else:
                lst.append(right.pop(0))
        if left:
            lst.extend(left)
        if right:
            lst.extend(right)
        return lst
 
    def mergesort(lst):
        """Sort the list by merging O(n * log n)."""
        length = len(lst)
        if length >= 2:
            mid = int(length / 2)
            lst = merge(mergesort(lst[:mid]), mergesort(lst[mid:]))
        return lst
 
    return mergesort
 
def prepare2():
 
    def merge(a,b):
        a, b = iter(a), iter(b)
        def gen(a, b):
            vb = next(b)
            try:
                while 1:
                    va = next(a)
                    if va > vb: va, vb, a, b = vb, va, b, a
                    yield va
            except: yield vb
        yield from gen(a, b)
        yield from a
        yield from b
 
    def mergesort(lst):
        mid = len(lst) // 2
        return merge(mergesort(lst[:mid]), mergesort(lst[mid:])) if mid else lst
 
    return mergesort
 
mergesort1 = prepare1()
mergesort2 = prepare2()
 
def f1():
    mergesort1([])
    mergesort1([3, 2, 1])
    mergesort1([4, 3, 2, 1])
    mergesort1([4, 3, 2, 1, 4, 3, 2, 1])
 
def f2():
    list(mergesort2([]))
    list(mergesort2([3, 2, 1]))
    list(mergesort2([4, 3, 2, 1]))
    list(mergesort2([4, 3, 2, 1, 4, 3, 2, 1]))
    
def main():
    t1 = timeit.Timer('f1()', 'from __main__ import f1')
    t2 = timeit.Timer('f2()', 'from __main__ import f2')
 
    for t in t1, t2:
        print(t.repeat(3, 10000))
 
if __name__ == '__main__':
    main()

[guest@localhost py]$ ./mergecmp.py 
[0.48058103199946345, 0.47939332600071793, 0.47897031599859474]
[0.6807953729985456, 0.6841518840010394, 0.6824002640023537]
[guest@localhost py]$

Мой быстрее :) Да, и с tuple для генераторов - тоже.

Isem

Авг. 28, 2015 07:36:31

Возьмем побольше элементов для сортировки, чтобы понять асимптотическую сложность алгоритмов:

import timeit
import random
 
def prepare1():
 
    def merge(left, right):
        """Merge two lists in ascending order."""
        lst = []
        while left and right:
            if left[0] < right[0]:
                lst.append(left.pop(0))
            else:
                lst.append(right.pop(0))
        if left:
            lst.extend(left)
        if right:
            lst.extend(right)
        return lst
 
    def mergesort(lst):
        """Sort the list by merging O(n * log n)."""
        length = len(lst)
        if length >= 2:
            mid = int(length / 2)
            lst = merge(mergesort(lst[:mid]), mergesort(lst[mid:]))
        return lst
 
    return mergesort
 
def prepare2():
 
    def merge(a,b):
        a, b = iter(a), iter(b)
        def gen(a, b):
            vb = next(b)
            try:
                while 1:
                    va = next(a)
                    if va > vb: va, vb, a, b = vb, va, b, a
                    yield va
            except: yield vb
        yield from gen(a, b)
        yield from a
        yield from b
 
    def mergesort(lst):
        mid = len(lst) // 2
        return merge(mergesort(lst[:mid]), mergesort(lst[mid:])) if mid else lst
 
    return mergesort
 
mergesort1 = prepare1()
mergesort2 = prepare2()
 
lst = list(range(400000))
random.shuffle(lst)
def f1():
    mergesort1(lst)
 
def f2():
    list(mergesort2(lst))
    
def main():
    t1 = timeit.Timer('f1()', 'from __main__ import f1')
    t2 = timeit.Timer('f2()', 'from __main__ import f2')
 
    for t in t1, t2:
        print(t.repeat(1, 1))
 
if __name__ == '__main__':
    main()

Результат:
53.83247528142226
8.517664874189144

При такой модификации (обертка в tuple)

def mergesort(lst):
        mid = len(lst) // 2
        return tuple(merge(mergesort(lst[:mid]), mergesort(lst[mid:]))) if mid else lst

время работы уменьшается до 6 секунд
Естественно, при этом преобразование в список не требуется: list(mergesort2(lst)) -> mergesort2(lst)

py.user.next

Авг. 28, 2015 07:57:39

#!/usr/bin/env python3
 
import timeit
 
def prepare1():
 
    def merge(left, right):
        """Merge two lists in ascending order."""
        lst = []
        while left and right:
            if left[0] < right[0]:
                lst.append(left.pop(0))
            else:
                lst.append(right.pop(0))
        if left:
            lst.extend(left)
        if right:
            lst.extend(right)
        return lst
 
    def mergesort(lst):
        """Sort the list by merging O(n * log n)."""
        length = len(lst)
        if length >= 2:
            mid = int(length / 2)
            lst = merge(mergesort(lst[:mid]), mergesort(lst[mid:]))
        return lst
 
    return mergesort
 
def prepare2():
 
    def merge(a,b):
        a, b = iter(a), iter(b)
        def gen(a, b):
            vb = next(b)
            try:
                while 1:
                    va = next(a)
                    if va > vb: va, vb, a, b = vb, va, b, a
                    yield va
            except: yield vb
        yield from gen(a, b)
        yield from a
        yield from b
 
    def mergesort(lst):
        mid = len(lst) // 2
        return merge(mergesort(lst[:mid]), mergesort(lst[mid:])) if mid else lst
 
    return mergesort
 
mergesort1 = prepare1()
mergesort2 = prepare2()
 
lst = list(range(100000))[::-1]
 
def f1():
    mergesort1([])
    mergesort1([3, 2, 1])
    mergesort1([4, 3, 2, 1])
    mergesort1([4, 3, 2, 1, 4, 3, 2, 1])
    mergesort1(lst)
 
def f2():
    list(mergesort2([]))
    list(mergesort2([3, 2, 1]))
    list(mergesort2([4, 3, 2, 1]))
    list(mergesort2([4, 3, 2, 1, 4, 3, 2, 1]))
    list(mergesort2(lst))
 
def main():
    t1 = timeit.Timer('f1()', 'from __main__ import f1')
    t2 = timeit.Timer('f2()', 'from __main__ import f2')
 
    for t in t1, t2:
        print(t.repeat(3, 10))
 
if __name__ == '__main__':
    main()

[guest@localhost py]$ ./mergecmp.py 
[12.73703371800002, 12.702942302999986, 12.771910132000016]
[9.36449182199999, 9.416434981000009, 9.488683936999962]
[guest@localhost py]$

Взял 100000 в обратном порядке и количество замеров уменьшил с 10000 до 10.

Add
Исправил mergesort1 на mergesort2.

Isem

Авг. 28, 2015 08:06:53

py.user.next
list(mergesort2())
list(mergesort1(lst))

Если вызвать mergesort2, то у меня получается
для 1: 24.475478611249645, 24.644684209573377, 24.50444498213283
для 2: 7.947475635309004, 7.956832071685923, 7.988833309466557