Я проверил различные варианты с модулем timeit . Ваш вариант работал фантастически, когда я генерировал тестовые данные, которые не повторялись часто, но для коротких строк мой stringcompress_using_string был самым быстрым методом. По мере того как струны растут дольше, все переворачивается с ног на голову, и ваш метод действий становится самым быстрым, а stringcompress_using_string - самым медленным.
Это говорит о важности тестирования в различных обстоятельствах. Мои первоначальные выводы, которые были неполными, и наличие большего количества данных испытаний показали правдивую историю об эффективности этих трех методов.
import string
import timeit
import random
def stringcompress_original(str1):
res = []
d = dict.fromkeys(string.ascii_letters, 0)
main = str1[0]
for char in range(len(str1)):
if str1[char] == main:
d[main] += 1
else:
if d[main] == 1:
res.append(main)
d[main] = 0
main = str1[char]
d[main] += 1
else:
res.append(main + str(d[main]))
d[main] = 0
main = str1[char]
d[main] += 1
res.append(main + str(d[main]))
return min(''.join(res), str1, key=len)
def stringcompress_using_list(str1):
res = []
count = 0
for i in range(1, len(str1)):
count += 1
if str1[i] is str1[i-1]:
continue
res.append(str1[i-1])
res.append(str(count))
count = 0
res.append(str1[i] + str(count+1))
return min(''.join(res), str1, key=len)
def stringcompress_using_string(str1):
res = ''
count = 0
# we can start at 1 because we already know the first letter is not a repition of any previous letters
for i in range(1, len(str1)):
count += 1
# we keep going through the for loop, until a character does not repeat with the previous one
if str1[i] is str1[i-1]:
continue
# add the character along with the number of times it repeated to the final string
# reset the count
# and we start all over with the next character
res += str1[i-1] + str(count)
count = 0
# add the final character + count
res += str1[i] + str(count+1)
return min(res, str1, key=len)
def generate_test_data(min_length=3, max_length=300, iterations=3000, repeat_chance=.66):
assert repeat_chance > 0 and repeat_chance < 1
data = []
chr = 'a'
for i in range(iterations):
the_str = ''
# create a random string with a random length between min_length and max_length
for j in range( random.randrange(min_length, max_length+1) ):
# if we've decided to not repeat by randomization, then grab a new character,
# otherwise we will continue to use (repeat) the character that was chosen last time
if random.random() > repeat_chance:
chr = random.choice(string.ascii_letters)
the_str += chr
data.append(the_str)
return data
# generate test data beforehand to make sure all of our tests use the same test data
test_data = generate_test_data()
#make sure all of our test functions are doing the algorithm correctly
print('showing that the algorithms all produce the correct output')
print('stringcompress_original: ', stringcompress_original('aabcccccaaa'))
print('stringcompress_using_list: ', stringcompress_using_list('aabcccccaaa'))
print('stringcompress_using_string: ', stringcompress_using_string('aabcccccaaa'))
print()
print('stringcompress_original took', timeit.timeit("[stringcompress_original(x) for x in test_data]", number=10, globals=globals()), ' seconds' )
print('stringcompress_using_list took', timeit.timeit("[stringcompress_using_list(x) for x in test_data]", number=10, globals=globals()), ' seconds' )
print('stringcompress_using_string took', timeit.timeit("[stringcompress_using_string(x) for x in test_data]", number=10, globals=globals()), ' seconds' )
Следующие результаты получены на четырехъядерном процессоре Intel i7-5700HQ с тактовой частотой 2,70 ГГц. Сравните различные функции внутри каждой цитаты, но не пытайтесь сравнивать результаты одной цитаты с другой, потому что размер тестовых данных будет разным.
Использование длинных строк
Тестовые данные, сгенерированные с помощью generate_test_data(10000, 50000, 100, .66)
stringcompress_original заняло 7,346990528497378 секунд
stringcompress_using_list занял 7,589927956366313 секунд
stringcompress_using_string заняло 7,713812443264496 секунд
Использование коротких строк
Тестовые данные, полученные с помощью generate_test_data(2, 5, 10000, .66)
stringcompress_original заняло 0,40272931026355685 секунд
stringcompress_using_list заняло 0,1525574881739265 секунд
stringcompress_using_string заняло 0,13842854253813164 секунд
10% шанс повторения символов
Тестовые данные, полученные с помощью generate_test_data(10, 300, 10000, .10)
stringcompress_original заняло 4,675965586924492 секунд
stringcompress_using_list заняло 6,081609410376534 секунд
stringcompress_using_string заняло 5,887430301813865 секунд
90% шанс повторения символов
Тестовые данные, полученные с помощью generate_test_data(10, 300, 10000, .90)
stringcompress_original заняло 2.6049783549783547 секунд
stringcompress_using_list занял 1,9739111725413099 секунд
stringcompress_using_string заняло 1,9460854974553605 секунд
Важно создать небольшую структуру, подобную этой, которую вы можете использовать для проверки изменений в вашем алгоритме. Часто изменения, которые кажутся бесполезными, заставляют ваш код работать намного быстрее, поэтому ключ к игре при оптимизации производительности - это попробовать разные вещи и рассчитать время. Я уверен, что есть больше открытий, которые можно найти, если вы поиграете с внесением различных изменений, но это действительно имеет значение для типа данных, для которых вы хотите оптимизировать - сжатие коротких строк против длинных строк против строк, которые не повторяются как часто против тех, которые делают.