← Сtrl

py.user.next · Дек. 5, 2012 00:38:13

BG
добился того же, только др способом. Рационально?

def count_sogl(value):
    CONSTANTS = u'цкнгшщзхфвпрлдчсмтб'
    count = 0
    for a in CONSTANTS:
        count += value.count(a)
    return count

сложность n^2, в которой нет необходимости
нужно пройти один раз по строке, выбрав буквы, находящиеся во множестве (поиск во множесте быстрее, чем поиск в строке), тогда получится 2 * n
для слова из 100 букв будет 200 операций, а не 10000

Отредактировано py.user.next (Дек. 5, 2012 00:41:23)

pyuser · Дек. 5, 2012 01:19:40

py.user.next
для слова из 100 букв будет 200 операций, а не 10000

но на практике для слова из 100 букв вариант топикастера отрабатывает, по меньшей мере, в два раза быстрее чем подсчет количества букв, входящих в множество.
На моем рабочем ПК (довольно слабая машинка), вариант топикастера начинает работать быстрее при длине слова > 2 * len(CONSTANTS)

py.user.next · Дек. 6, 2012 00:46:03

pyuser
о на практике для слова из 100 букв вариант топикастера отрабатывает, по меньшей мере, в два раза быстрее чем подсчет количества букв, входящих в множество

непонятно, что ты сравнивал

вот ilnur'а

def count_sogl(value):
    CONSTANTS = u'цкнгшщзхфвпрлдчсмтб'
    count = 0
    for a in CONSTANTS:
        count += value.count(a)
    return count
  
for a in [u'папа', u'як', u'дорожка']:
    print a, ' -> ', count_sogl(a), u' согласных'

вот мой

CONSTANTS = set(u'цкнгшщзхфвпрлдчсмтб')
arr = [u'папа', u'як', u'дорожка']
for word in arr:
    print sum(c in CONSTANTS for c in word)

pyuser · Дек. 6, 2012 01:20:01

from timeit import timeit
CONSONANTS = set("бвгдйжзклмнпрстфхцчшщ")
WORD = "".join(CONSONANTS) * 5 # слово из 105 букв
def cons_count_1(word):
    """ вариант топикастера """
    return sum(map(word.count, CONSONANTS))
def cons_count_2(word):
    """ Ваш вариант """
    return sum(c in CONSONANTS for c in word)
if "__main__" == __name__:
    import builtins
    builtins.__dict__.update(locals())
    print(timeit("cons_count_1(WORD)"))
    print(timeit("cons_count_2(WORD)"))

результат такой:

11.795760913747419
24.30858768363018

py.user.next · Дек. 6, 2012 07:43:54

def f1(word):
    CONSONANTS = set("бвгдйжзклмнпрстфхцчшщ")
    return sum(map(word.count, CONSONANTS))
 
def f2(word):
    CONSONANTS = set("бвгдйжзклмнпрстфхцчшщ")
    return sum(c in CONSONANTS for c in word)
 
import timeit
 
s = "абвгдеёжзи"
 
t1 = timeit.Timer('f1("{}")'.format(s), 'from __main__ import f1')
t2 = timeit.Timer('f2("{}")'.format(s), 'from __main__ import f2')
t1.repeat(3)
t2.repeat(3)

>>> t1.repeat(3)
[7.500285625000288, 7.495358050000505, 7.4992152530003295]
>>> t2.repeat(3)
[4.4539746159998685, 4.457933652000065, 4.4544935840003745]
>>> 
>>> 
>>> t1.repeat(3)
[7.535601026999757, 7.525300220000645, 7.522909998000614]
>>> t2.repeat(3)
[4.449643222000304, 4.448924850000367, 4.450461745999746]
>>>

на коротком слове мой немного быстрее

def f1(word):
    CONSONANTS = set("бвгдйжзклмнпрстфхцчшщ")
    return sum(map(word.count, CONSONANTS))
 
def f2(word):
    CONSONANTS = set("бвгдйжзклмнпрстфхцчшщ")
    return sum(c in CONSONANTS for c in word)
 
import timeit
 
s = "абвгдеёжзи" * 10
 
t1 = timeit.Timer('f1("{}")'.format(s), 'from __main__ import f1')
t2 = timeit.Timer('f2("{}")'.format(s), 'from __main__ import f2')
t1.repeat(3)
t2.repeat(3)

>>> t1.repeat(3)
[8.908654792000561, 8.904308604000107, 8.908578528999897]
>>> t2.repeat(3)
[19.115710095000395, 19.11386605900043, 19.119253977999506]
>>> 
>>> 
>>> t1.repeat(3)
[8.913373002000299, 8.902025593999497, 8.913000268999895]
>>> t2.repeat(3)
[19.754902993999167, 19.19199875599952, 19.564209768000183]
>>>

на длинном слове мой во много раз медленнее

вероятно, str.count() работает быстрее генератора, и каждый ноль, который получается в генераторе, приходится прибавлять, тогда как в map() получается последовательность чисел без нулей

Отредактировано py.user.next (Дек. 6, 2012 07:49:01)

pyuser · Дек. 6, 2012 08:11:44

py.user.next
на длинном слове мой во много раз медленнее

об этом я писал в этом посте и в этом :)

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

Уведомления

#1 Дек. 5, 2012 00:38:13

По кол-ву согласных

#2 Дек. 5, 2012 01:19:40

По кол-ву согласных

#3 Дек. 6, 2012 00:46:03

По кол-ву согласных

#4 Дек. 6, 2012 01:20:01

По кол-ву согласных

#5 Дек. 6, 2012 07:43:54

По кол-ву согласных

#6 Дек. 6, 2012 08:11:44

По кол-ву согласных

Board footer