← Сtrl

bismigalis · Окт. 31, 2013 13:55:27

если в моей ============== 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

bismigalis · Окт. 31, 2013 15:12:27

так там была наверное какая-то оптимизация

если на вход подаю range(1,10**6*2,4) + range(2,10**6*2, 4)
то вижу удвоение у py.user.next
EDIT: это не удвоение, это так показывает что в out'е накопилось

Line #    Mem usage    Increment   Line Contents
================================================
     3     39.9 MiB      0.0 MiB   @profile 
     4                             def convert_any_order(lst):
     5     39.9 MiB      0.0 MiB       fmt = '{}:{}'
     6     43.7 MiB      3.8 MiB       lst.sort()
     7     43.7 MiB      0.0 MiB       out = []
     8     43.7 MiB      0.0 MiB       prev, inrange, first = lst[0], False, 0
     9     83.1 MiB     39.4 MiB       for x in lst[1:]:
    10     83.1 MiB      0.0 MiB           if prev + 1 != x:
    11     83.1 MiB      0.0 MiB               if inrange:
    12     83.1 MiB      0.0 MiB                   inrange = False
    13     83.1 MiB      0.0 MiB                   out.append(fmt.format(first, prev))
    14                                         else:
    15                                             out.append(str(prev))
    16     83.1 MiB      0.0 MiB           elif not inrange:
    17     83.1 MiB      0.0 MiB               inrange, first = True, prev
    18     83.1 MiB      0.0 MiB           prev = x
    19     75.5 MiB     -7.6 MiB       if inrange:
    20     75.5 MiB      0.0 MiB           out.append(fmt.format(first, prev))
    21                                 else:
    22                                     out.append(str(prev))
    23     75.5 MiB      0.0 MiB       return out

у меня по прежнему всё плохо

Line #    Mem usage    Increment   Line Contents
================================================
     4     39.9 MiB      0.0 MiB   @profile
     5                             def f(lst):
     6     43.7 MiB      3.8 MiB       lst.sort()
     7     43.7 MiB      0.0 MiB       res = []
     8     43.7 MiB      0.0 MiB       tmp = []
     9    110.7 MiB     67.0 MiB       for item, nextitem in izip(lst, lst[1:]+[None]):
    10    110.7 MiB      0.0 MiB           tmp.append(item)
    11    110.7 MiB      0.0 MiB           if nextitem is None or nextitem - item != 1:
    12    110.7 MiB      0.0 MiB               if len(tmp) > 1:
    13    110.7 MiB      0.0 MiB                   res.append(tmp)
    14                                         else:
    15                                             res.extend(tmp)
    16    110.7 MiB      0.0 MiB               tmp = []
    17                             
    18    103.0 MiB     -7.6 MiB       out = []
    19    137.9 MiB     34.8 MiB       for item in res:
    20    137.9 MiB      0.0 MiB           if isinstance(item, list):
    21    137.9 MiB      0.0 MiB               out.append("{}:{}".format(item[0], item[-1]))
    22                                     else:
    23                                         out.append(str(item))
    24    145.4 MiB      7.6 MiB       print ', '.join(out)

Отредактировано bismigalis (Окт. 31, 2013 20:24:26)

py.user.next · Окт. 31, 2013 22:30:55

bismigalis

    10    110.7 MiB      0.0 MiB           tmp.append(item)

странно, что он не показывает рост списка tmp, именно про него я и говорил: когда у тебя миллиард элементов в списке lst, то при накоплении в tmp будет добавляться ещё такой же миллиард

bismigalis

     9    110.7 MiB     67.0 MiB       for item, nextitem in izip(lst, lst[1:]+[None]):

возможно, в этой строке эта инфа о tmp

Отредактировано py.user.next (Окт. 31, 2013 22:33:31)

bismigalis · Ноя. 2, 2013 11:57:24

да, я тоже не правильно понял, и сделал неправильные выводы

то что напротив for аккумулирует то что внутри цикла

bismigalis · Ноя. 2, 2013 15:22:18

py.user.next
когда у тебя миллиард элементов в списке lst, то при накоплении в tmp будет добавляться ещё такой же миллиард

это в худшем случае, если весь список одна последовательность, как в первом случае, когда на вход подаю range(10**6),
плюс у меня еще накапливается промежуточный результат в res, короче я понял свою ошибку

у тебя оптимально получается, но 7.6MiB теряется на слайс, можно без слайса обойтись, я щас разобрался что к чему

Line #    Mem usage    Increment   Line Contents
================================================
     3      8.8 MiB      0.0 MiB   @profile
     4                             def main():
     5     39.9 MiB     31.0 MiB       lst = range(10**6)
     6     47.5 MiB      7.6 MiB       slc = lst[:]

список из миллиона интов занимает 31MiB, слайс возвращает список, в питоне список это массив указателей, то есть копируется массив указателей, а не значения.

py.user.next · Ноя. 2, 2013 19:22:44

bismigalis
у тебя оптимально получается, но 7.6MiB теряется на слайс, можно без слайса обойтись

#!/usr/bin/env python3
 
# приводит список целых к списку диапазонов
# [3, 1, 2, 5] -> ['1:3', '5']
 
# f: OM(Z) -> OM(seq S)
# F: OM(Z) -> (f, Z, Q, Z)
#
# F: om -> (f(om), p, q, n)
#
# F(dt) = (dt, неопр, нет, 0)
# G = | (f(om),          x, нет, 0), если p = неопр
#     | (f(om) * p,      x, нет, 0), если p + 1 != x и не q
#     | (f(om) * (n, p), x, нет, 0), если (p + 1 != x или last(x)) и q
#     | (f(om),          x, да,  p), если p + 1 = x и не q
#     | (f(om),          x, да,  n), если p + 1 = x
 
class NotAListError(TypeError):
    pass
 
def convert_any_order(lst):
    """Convert integers in any order to single and range strings."""
    if type(lst) != list:
        raise NotAListError('the argument should be a list')
    fmt = '{}:{}'
    lst.sort()
    out = []
    prev, inrange, first = None, False, 0
    for x in lst:
        if prev is None:
            pass
        elif prev + 1 != x:
            if inrange:
                inrange = False
                out.append(fmt.format(first, prev))
            else:
                out.append(str(prev))
        elif not inrange:
            inrange, first = True, prev
        prev = x
    if inrange:
        out.append(fmt.format(first, prev))
    elif prev is not None:
        out.append(str(prev))
    return out

это без среза, но оно медленнее немного

[guest@localhost timecmp]$ ./timecmp.py 
[0.6980301569997209, 0.6972508899998502, 0.6992985159999989]
[0.7046079839997219, 0.7039838179998696, 0.6905217889998312]
[0.7073219859998972, 0.7085624579999603, 0.706647607999912]
[guest@localhost timecmp]$

1) со срезом
2) со срезом через itertools
3) без среза

Отредактировано py.user.next (Ноя. 2, 2013 21:53:22)

bismigalis · Ноя. 2, 2013 20:19:55

лучше так

    it = iter(lst)
    prev, inrange, first = next(it), False, 0
    for x in it:

py.user.next · Ноя. 2, 2013 22:10:22

bismigalis
лучше так

лучше, но позапутаннее выходит как по описанию, так и по коду (обработка пустого списка выносится)
я бы оставил свой последний вариант потому, что он не сильно медленнее (одна лишняя проверка на каждом шаге)

[guest@localhost timecmp]$ ./timecmp.py 
[0.6925457369998185, 0.6927445239998633, 0.6931966669999383]
[0.6925680670010479, 0.6935572090005735, 0.6948275009999634]
[0.703800751000017, 0.7037471780004125, 0.7026632309989509]
[0.6951408549994085, 0.693388210998819, 0.6947514619987487]
[guest@localhost timecmp]$

1) со срезом
2) со срезом через itertools
3) без среза
4) через iter()

Отредактировано py.user.next (Ноя. 2, 2013 22:17:13)

bismigalis · Ноя. 2, 2013 23:10:24

py.user.next
со срезом

на мильярде элементов срез займет 8Гб, так что не вариант

bismigalis · Ноя. 4, 2013 09:56:10

def intervals(lst):
    lst.sort()
    lst.append(None)
    NOTSEQ, SEQ = 0, 1
    prev_state = NOTSEQ
    itr = iter(lst)
    item = next(itr)
    for nextitem in itr:
        state = SEQ if (nextitem is not None and nextitem - item == 1) else NOTSEQ
        if state == SEQ:
            if prev_state == NOTSEQ:
                seq_start = item
        elif state == NOTSEQ:
            if prev_state == SEQ:
                yield str(seq_start) + ':' + str(item)
            elif prev_state == NOTSEQ:
                yield str(item)
        prev_state, item = state, nextitem

Отредактировано bismigalis (Ноя. 4, 2013 10:05:28)

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

Уведомления

#1 Окт. 31, 2013 13:55:27

сокращение последовательности в строке, re

#2 Окт. 31, 2013 15:12:27

сокращение последовательности в строке, re

#3 Окт. 31, 2013 22:30:55

сокращение последовательности в строке, re

#4 Ноя. 2, 2013 11:57:24

сокращение последовательности в строке, re

#5 Ноя. 2, 2013 15:22:18

сокращение последовательности в строке, re

#6 Ноя. 2, 2013 19:22:44

сокращение последовательности в строке, re

#7 Ноя. 2, 2013 20:19:55

сокращение последовательности в строке, re

#8 Ноя. 2, 2013 22:10:22

сокращение последовательности в строке, re

#9 Ноя. 2, 2013 23:10:24

сокращение последовательности в строке, re

#10 Ноя. 4, 2013 09:56:10

сокращение последовательности в строке, re

Board footer