DjangoBB LoFi version

Начало » Python для новичков » кодирование текста

1 2

vic57

Дек. 9, 2017 04:09:10

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

ну а как надо через итераторы? я не вижу физического смысла вычислять ф-цию от пустой строки.

py.user.next

Дек. 9, 2017 04:23:29

vic57
ну а как надо через итераторы?

Это я твою функцию поправил минимально

  
>>> def f(s):
...     it = iter(s)
...     prev = next(it, None)
...     count = 1
...     out = ''
...     while prev:
...         try:
...             curr = next(it)
...             if prev == curr: count += 1
...             else:
...                 out += prev + str(count)
...                 count = 1
...             prev = curr
...         except StopIteration:
...             out += prev + str(count)
...             break
...     return out
... 
>>> f('')
''
>>> f('a')
'a1'
>>> f('ab')
'a1b1'
>>> f('aabb')
'a2b2'
>>>

То есть она хотя бы возвращает всё правильно алгоритмически. То есть юнит-тесты она бы прошла. Но по скорости, понятности, стильности она, конечно, должна быть полностью переделана.

vic57
я не вижу физического смысла вычислять ф-цию от пустой строки.

Ты можешь не обрабатывать None, поданный в функцию, но пустая строка входит во множество всех строк. Когда эта функция будет использоваться в какой-нибудь программе, туда запросто может пустая строка попасть. И ещё, функция, обрабатывающая любые строки, ценнее функции, обрабатывающей лишь часть строк. Ценнее потому, что эта функция подходит для решения большего числа задач. То есть у неё более высокий коэффициент реюза. Мы её можем использовать не в 50 проектах, а в 100 проектах. Чем больше у тебя таких функций с высоким реюзом, тем быстрее ты будешь делать новые проекты. Это как салат из полуфабрикатов готовить: можно выращивать овощи, пропалывать, собирать их там, чистить и нарезать; а можно купить уже нарезанные овощи и просто смешать их с майонезом. За одно и то же время у тебя разный результат получается. То же самое с функциями: ты можешь в каждом проекте писать их заново, а можешь в одном проекте их написать, а потом в сотню других проектов их просто скопировать.

vic57

Дек. 9, 2017 04:29:29

ну не проще на входе сделать

 if not s: return ''

зачем огород городить?

py.user.next

Дек. 9, 2017 04:40:38

vic57
ну не проще на входе сделать

Нужно и так и так уметь делать. Потому что в этом случае это просто выглядит и нужно одну шпуньку проверить, а в других случаях надо проверить десять шпунек и все непростые. Просто заполнишь функцию так, что она нечитаемой станет.

Ну и ты спрашивал тоже “как это через итератор сделать?” - я тебе показал, что элементарно, нужно только питон лучше знать. Но одного знания питона мало, нужно ещё алгоритм представлять в виде схемы и видеть, просто она выглядит или запутанно.

vic57

Дек. 9, 2017 06:17:53

  def f(s):
    if not s: return ''
    it = iter(s)
    prev = next(it)
    count = 1
    out = ''
    while True:
        try:
            curr = next(it)
            if prev == curr: count += 1
            else:
                out += prev + str(count)
                count = 1
            prev = curr
        except StopIteration:
            out += prev + str(count)
            break
    return out

ну и в чем разница-то кроме проверки на пустую строку?
функция делает именно то что от нее надо, не больше и не меньше

vic57

Дек. 9, 2017 13:08:06

py.user.next
Но по скорости, понятности, стильности она, конечно, должна быть полностью переделана.

делаю простое сравнение f() - итератор, f1() - индекс, func() - из твоего поста

 def f(s):
    if not s: return ''
    it = iter(s)
    prev = next(it)
    count = 1
    out = ''
    while True:
        try:
            curr = next(it)
            if prev == curr: count += 1
            else:
                out += prev + str(count)
                count = 1
            prev = curr
        except StopIteration:
            out += prev + str(count)
            break
    return out
           
def f1(s):
    if not s: return ''
    out = ''
    prev = s[0]
    count = 1
    ln = len(s)
    for i in range(1,ln):
        curr = s[i]
        if prev == curr: count += 1
        else:
            out += prev + str(count)
            count = 1
        prev = curr
    out += prev + str(count)
    return out
    
def func(s):
    res = ''
    state = 0
    ch = ''
    n = 0    
    i = 0
    slen = len(s)
    while i < slen:
        c = s[i]
        if state == 0: # first char
            ch = c
            n = 1
            if i + 1 == slen:
                res = ch + str(n)
            state = 1
        elif state == 1: # other char
            if c == ch:  # matched
                n += 1
                if i + 1 == slen:
                    res += ch + str(n)
            else:        # didn't match
                res += ch + str(n)
                ch = c
                n = 0
                i -= 1
        i += 1
    return res
 
s = 'qqqwwweeerrrtttttyXYZ'
from time import time
t0 = time()
for i in range(100000): t = f(s)
t1 = time()
print(t1-t0,t)
t0 = time()
for i in range(100000): t = f1(s)
t1 = time()
print(t1-t0,t)
t0 = time()
for i in range(100000): t = func(s)
t1 = time()
print(t1-t0,t)

 0.9916658401489258 q3w3e3r3t5y1X1Y1Z1# итератор
0.8220779895782471 q3w3e3r3t5y1X1Y1Z1 # индекс
1.3592848777770996 q3w3e3r3t5y1X1Y1Z1 # ф-ция из поста py user next

ты пришел третьим

py.user.next

Дек. 9, 2017 15:05:39

Вот я тут написал новую версию

  
>>> def f(s):
...     if s == '':
...         return s
...     out = ''
...     prev = ''
...     n = 0
...     for ch in s:
...         if ch == prev or prev == '':
...             pass
...         else:
...             out += prev + str(n)
...             n = 0
...         prev = ch
...         n += 1
...     out += prev + str(n)
...     return out
... 
>>> f('')
''
>>> f('a')
'a1'
>>> f('aa')
'a2'
>>> f('ab')
'a1b1'
>>> f('aaaarufnnbjff')
'a4r1u1f1n2b1j1f2'
>>>

Вот ещё одна, но она медленная. Зато самая короткая.

  
import itertools
 
def f(s):
    return ''.join(c + str(len(tuple(g))) for c, g in itertools.groupby(s))

А вот тут замеры всех функций: двух твоих, моей старой (25 января 2012 года), моей новой и моей самой короткой.

#!/usr/bin/env python3

import timeit

def func1(s):
    if not s: return ''
    it = iter(s)
    prev = next(it)
    count = 1
    out = ''
    while True:
        try:
            curr = next(it)
            if prev == curr: count += 1
            else:
                out += prev + str(count)
                count = 1
            prev = curr
        except StopIteration:
            out += prev + str(count)
            break
    return out

def func2(s):
    if not s: return ''
    out = ''
    prev = s[0]
    count = 1
    ln = len(s)
    for i in range(1,ln):
        curr = s[i]
        if prev == curr: count += 1
        else:
            out += prev + str(count)
            count = 1
        prev = curr
    out += prev + str(count)
    return out

def func3(s):
    res = ''
    state = 0
    ch = ''
    n = 0

    i = 0
    slen = len(s)
    while i < slen:
        c = s[i]
        if state == 0: # first char
            ch = c
            n = 1
            if i + 1 == slen:
                res = ch + str(n)
            state = 1
        elif state == 1: # other char
            if c == ch:  # matched
                n += 1
                if i + 1 == slen:
                    res += ch + str(n)
            else:        # didn't match
                res += ch + str(n)
                ch = c
                n = 0
                i -= 1
        i += 1
    return res

def func4(s):
    if s == '':
        return s
    out = ''
    prev = ''
    n = 0
    for ch in s:
        if ch == prev or prev == '':
            pass
        else:
            out += prev + str(n)
            n = 0
        prev = ch
        n += 1
    out += prev + str(n)
    return out

import itertools

def func5(s):
    return ''.join(c + str(len(tuple(g))) for c, g in itertools.groupby(s))


def f1():
    func1('aaabbbcde' * 100)

def f2():
    func2('aaabbbcde' * 100)

def f3():
    func3('aaabbbcde' * 100)

def f4():
    func4('aaabbbcde' * 100)

def f5():
    func5('aaabbbcde' * 100)


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')
    t4 = timeit.Timer('f4()', 'from __main__ import f4')
    t5 = timeit.Timer('f5()', 'from __main__ import f5')

    for t in t1, t2, t3, t4, t5:
        print(t.repeat(3, 10000))

if __name__ == '__main__':
    main()

Вывод

[guest@localhost rlecomp]$ ./rlecompcmp.py 
[3.3369056259980425, 3.323838824995619, 3.326331812000717] # твоя итератор
[2.8052678310050396, 2.7940210589949857, 2.83161843400012] # твоя индексы
[5.913237972999923, 5.912506636996113, 5.872607308003353] # моя старая
[2.6772045339967008, 2.676720352996199, 2.6726658850020613] # моя новая
[4.964137271002983, 4.971889730004477, 4.978617688000668] # моя новая короткая
[guest@localhost rlecomp]$

Так же присоединяю архив, где есть моя новая функция, юнит-тесты для неё на pytest и измерительный скрипт со всеми функциями.

vic57

Дек. 10, 2017 15:20:05

крайний вариант оказался самым быстрым. я по аналогии с Си считал что наиболее быстрый метод - указатель(итератор).