Python-сообщество

Конечный оптимизированный вариант функций merge и mergesort:

def merge(a,b):
    a, b = iter(a), iter(b)
    try:
        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 b
    except: yield from a
    
def mergesort(lst):
    l = len(lst)
    if l == 2:
        ll, rr = lst
        return lst if ll < rr else (rr, ll)
    l //= 2
    return tuple(merge(mergesort(lst[:l]), mergesort(lst[l:]))) if l else lst

Isem
Если вызвать mergesort2, то у меня получается

Isem
Конечный оптимизированный вариант функций merge и mergesort:

#!/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
 
def prepare3():
 
    def merge(a,b):
        a, b = iter(a), iter(b)
        try:
            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 b
        except: yield from a
 
    def mergesort(lst):
        l = len(lst)
        if l == 2:
            ll, rr = lst
            return lst if ll < rr else (rr, ll)
        l //= 2
        return tuple(merge(mergesort(lst[:l]), mergesort(lst[l:]))) if l else lst
 
    return mergesort
 
mergesort1 = prepare1()
mergesort2 = prepare2()
mergesort3 = prepare3()
 
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 f3():
    list(mergesort3([]))
    list(mergesort3([3, 2, 1]))
    list(mergesort3([4, 3, 2, 1]))
    list(mergesort3([4, 3, 2, 1, 4, 3, 2, 1]))
    list(mergesort3(lst))
 
def main():
    t1 = timeit.Timer('f1()', 'from __main__ import f1')
    t2 = timeit.Timer('f2()', 'from __main__ import f2')
    t3 = timeit.Timer('f3()', 'from __main__ import f3')
     
    for t in t1, t2, t3:
        print(t.repeat(3, 10))
 
if __name__ == '__main__':
    main()

[guest@localhost py]$ ./mergecmp.py 
[12.741739178999978, 12.674231455999916, 13.210156642000015]
[9.427098683000054, 9.385439743000006, 9.390970238000023]
[6.9163552539999955, 7.000873819999924, 6.991111120000028]
[guest@localhost py]$

>>> sorted('abcd')
['a', 'b', 'c', 'd']
>>>

Отредактировано py.user.next (Авг. 28, 2015 10:42:13)

py.user.next
Получилось преимущество в два раза, не более. :)

py.user.next
(хотя почему в кортеж? типа он быстрее списка? а почему на входе подаётся список, а на выходе кортеж? а если список пустой, то возвращается список? надо уж как-то точнее что ли)

py.user.next
Вопрос: почему встроенная sorted() возвращает список а не кортеж?

Isem
Обект кортежа создается раз и навсегда одним куском памяти, которая хранит как сам объект кортежа, так и список объектов, которые он содержит.

>>> a, b, c = [1], [2], [3]
>>> 
>>> t = a, b, c
>>> t
([1], [2], [3])
>>> a.append(1)
>>> t
([1, 1], [2], [3])
>>>

Isem
Встроенная sorted возвращает список по той простой причине, что ее оптимизированная сишная реализация органически требует динамический массив, а значит и нет никакой надобности делать его еще потом тьюплом. Зачем лишний раз заниматься реаллокацией данных в памяти?

Отредактировано py.user.next (Авг. 28, 2015 12:57:24)

py.user.next
Кортеж - это такой же массив указателей, как и список:

py.user.next
Просто список медленнее работает, потому что в нём есть дополнительные методы для изменения.

py.user.next
Она (sorted) возвращает список, потому что проводит перестановки элементов.

py.user.next
Как точно такие же перестановки исключаются при mergesort? Какое преимущество даёт tuple?

>>> a = (1,2,3,4)
>>> id(a) == id(a[:2])
False
>>> 

Отредактировано Isem (Авг. 28, 2015 13:48:00)

Интересно было бы написать inplace mergesort. В таком случае скорость ее работы увеличится на порядок.
И тогда она, конечно, будет работать со списком.

Isem
находится в памяти - отдельно (в этом случае его размер можно динамически менять) или в той же структуре тьюпла

Isem
Список работает не медленне, просто не вызывайте методы, которых нет в тьюпле - методы, изменяющие список.

[guest@localhost ~]$ python3 -mtimeit -n 10000 -s "obj = [1, 2, 3]" "obj[::-1]"
10000 loops, best of 3: 0.237 usec per loop
[guest@localhost ~]$ python3 -mtimeit -n 10000 -s "obj = (1, 2, 3)" "obj[::-1]"
10000 loops, best of 3: 0.16 usec per loop
[guest@localhost ~]$

Isem
А также больше фрагментирует память.

Isem
Список создается потому, что для работы алгоритма сортировки требуется массив указателей, размер которого заранее неизвестен (ведь в функцию sorted можно передать любой итератор, размер которого неизвестен, пока мы по нему не пробежим), поэтому выгоднее создать список с динамическим массивом.

Isem
А так как приходится создавать много-много массивов, то выгоднее всего в таком случае создавать tuple.

Isem
Операция взятия среза создает новый объект:

Isem
На входе в merge можно подавать что угодно, лишь бы это был итератор (список, кортеж, словарь, генератор, множество).

Отредактировано py.user.next (Авг. 28, 2015 14:30:25)

py.user.next
Это ты смотрел или предполагаешь?

py.user.next
$ python3 -mtimeit -n 10000 -s "obj = “ ”obj"
10000 loops, best of 3: 0.237 usec per loop
$ python3 -mtimeit -n 10000 -s “obj = (1, 2, 3)” "obj"
10000 loops, best of 3: 0.16 usec per loop
$

py.user.next
Это откуда инфа такая?

py.user.next
Чем же мешает кортеж в таком случае? Уж не тем ли, что в нём переставлять элементы невозможно?

py.user.next
Так оно у тебя не создаётся, только конечный массив преобразуется в tuple, а так - там генераторы. А те генераторы, которые в промежутках преобразуются в tuple, делают это напрасно.

py.user.next
У меня там срезы, чтобы можно было списки эти менять и на исходный массив это не влияло. У тебя же там срезы - непонятно, зачем. По идее, надо сделать копию списка (итерабла) и сортировать её на месте (inplace), раз уж там генераторы.

[1,2,3,4][:]

py.user.next
Но подаются-то туда срезы, которые с генератора не сделаешь (нецелесообразно). Генератор предназначен для использования без знания его длины, тогда как правый срез должен узнавать его длину.

Отредактировано Isem (Авг. 28, 2015 19:53:58)

Isem
Я это знаю, так как использую С-структуры питона непосредственно в С/С++ проектах

Isem
Здесь я вижу создание двух списков (первый пример) и двух тьюплов (второй пример). Как уже сказал, создание списка - это медленнее, чем создание тьюпла.

Isem
Это называется memory managment in C/C++. Список в течение времени жизни много раз отводит и освобождает память (при старте - два раза), тьюпл - только один раз и только при его создании.

Isem
Дело не в перестановке элементов в кортеже, а в изменении его размера (количества элементов).

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

Isem
Поставь на вход тьюпл и все прекрасно сработает

Isem
Для inplace mergesort функция merge тоже должна быть inplace

Isem
Срезы не являются самостоятельными объектами, поэтому их нельзя куда-то подать.

>>> [1, 2, 3, 4][slice(1, 3)]
[2, 3]
>>>

Отредактировано py.user.next (Авг. 29, 2015 13:36:06)

py.user.next
И откуда следует, что объекты списка и кортежа хранятся по-разному?

py.user.next
Насколько помню (лень смотреть) они там хранятся в виде прицепленного к структуре массива.

py.user.next
Операция-то одна и та же - взятие среза.

py.user.next
C и C++, это разные языки, а склеивают их обычно те, кто C не знает (теоретизировал после C++ в стиле “гиме зе мер бите… а, ну это я знаю”).

py.user.next
Если подаётся кортеж, для сортировки его элементов нужно их переставлять, а так как порядок элементов кортежа можно определить один раз, то делается список, чтобы там можно было обмены совершать по мере сортировки

py.user.next
Как-то у тебя странно: ты хотел использовать итераторы, но так как они криво пошли, ты переключился на кортежи. Но ведь кортежи жрут память, и практически то же количество, что и списки.

py.user.next
У меня там списки не просто так, а для возможности выполнения pop(). И по ним ещё и условие проверяется, пуст/не пуст.

py.user.next
В общем, у тебя какая-то комбинация получилась запутанная. С одной строны ты хотел применить итераторы, но оказалось, что там надо копировать части. И в итоге ты их использовал хотя бы где-то. А если всё делать на итераторах, то оно как-то не получается ;)
А всё почему? Потому что в итераторе ты не можешь менять порядок элементов.

py.user.next
slice(1, 3)

Отредактировано Isem (Авг. 29, 2015 19:50:00)