Мы получили это задание от нашего профессора.Необходимые условия:
- Использование Python 3 и использование только встроенных функций (без ошибок).
- Основная задача: найти и сохранить результат в течение 5 секунд.
- Незначительное задание, просто приятно иметь: Найти не только значение для основания b = 3, но и для оснований b = 3 ** k (при k = 2,3,4).
По сравнению с нашим 1-м прямым решением мы достигли улучшения в 96 раз (почти в 100 раз быстрее), но все равно оно не соответствует 5-секундному пределу (в настоящее время мы находимся на 25-секундном ноутбуке i7).[Наш проф также не имеет решения на чистом Python, так что это небольшая исследовательская задача.]
Полный код (включая тестовые вызовы) находится здесь: В целом, он показывает улучшение с первоначально 2400 секунд (=40 мин) до 25 секТем не менее, нам нужно еще одно повышение производительности в 5 раз. Есть ли у кого-то идеи и можно ли помочь?
# -*- coding: utf-8 -*-
#
# Convert a long random sequence of base-10 digits to integers base 3**k with k=1,2,3,4
#
# Task for phdgroupA: length of sequence is 1.5*(10**6)
# time < 5 sec
# Use Python 3 (standard libraries only, no numpy) !
#
# Testcase with a very small sequence, made purely of the digit 7:
# (see sagemath or www.math.com/tables/general/base_conv.htm)
# numlen = 12 --> 777777777777_base10
# = 2202100120200002212221010_base3
# = 2670520085833_base9
# = 2k9fi2np3_base27 ("digits": 0123456789ab...pq)
# [2, 20, 9, 15, 18, 2, 23, 25, 3]
# = 2[61]5[18]8[53][30]_base81
# [2, 61, 5, 18, 8, 53, 30]
#
# Convert decimal number n to a sequence of list elements with integer values in the range 0 to base-1.
# With divmod, it's ca. 1/3 faster than using n%b and then n//=b.
def numberToBase(n, b):
digits = []
while n:
n, rem = divmod(n, b)
digits.append(rem)
return digits[::-1]
# Step 0: Create string of nlen digits
def step0(nlen):
rd = 7 # which digit to repeat
string_val = "".join(str(rd) for i in range(nlen))
return string_val # end of step0()
# Step 1: Convert string to int (the string contains only decimal digits)
def step1(string_val, option_chunk=True):
if option_chunk == True:
string_val_len = len(string_val)
Chunk_len = 90000
Read_len = 0
int_valChunk = 0
int_valLocal = 0
ii = 0
while Read_len < string_val_len:
string_val_ChunkRead = string_val[ii*Chunk_len:(ii+1)*Chunk_len]
Chunk_lenRead = len(string_val_ChunkRead)
int_valChunk = int(string_val_ChunkRead)
ii += 1
int_valLocal = int_valLocal * 10**Chunk_lenRead + int_valChunk
Read_len += Chunk_lenRead
int_val = int_valLocal
else:
int_val = int(string_val)
return int_val # end of step1()
# Step 2: Convert given integer to another base
def step2(n, b, convsteps):
nList = []
if convsteps == 3: # Here the conversion is done in 3 steps
expos = 10000, 300
base_a = b ** expos[0]
base_b = b ** expos[1]
nList1 = numberToBase(n, base_a) # That's the time killer in this part
nList2 = [numberToBase(ll, base_b) for ll in nList1]
nList3 = [numberToBase(mm, b) for ll in nList2 for mm in ll]
nList = [mm for ll in nList3 for mm in ll]
else: # Do conversion in one bulk
nList = numberToBase(n, b)
return nList # end of step2()
if __name__ == '__main__':
# Calculate the string of digits
numlen = 1500000 # number of digits = length of sequence
string_value = step0(numlen)
# Calculate the integer value of the string_value
int_value = step1(string_value, option_chunk=True)
# Convert int_value to list of numbers of the given bases
convsteps = 3 # value of '3' makes step2() 50-60 times faster than value '1'
b = 3
numList = step2(int_value, b, convsteps)
print('3**1: numList begin:', numList[:10]) # Expect: [2, 0, 1, 0, 0, 1, 1, 0, 2, 1]
Есть идеи, что кусок на шаге 1 может иметь другой размер?Или две большие основы для промежуточных преобразований могут быть лучше сбалансированы?Или преобразование строки десятичных цифр в список базы 3 может быть выполнено более напрямую?
Описание : Алгоритм в приведенном выше коде Python работает в 3 этапа:
- шаг 0: получить данные.Здесь мы создаем - для целей тестирования - последовательность десятичных цифр длиной 1,5 миллиона цифр.Это значение обычно является значением, которое мы получим как случайное значение из файла.Затем последовательность сохраняется в виде строки.
- шаг 1: преобразовать эту строку в целое число (по умолчанию используется основание 10).
- шаг 2: преобразовать это целое число в целое число с основанием b =3.
Эти три изменения вызвали большинство улучшений (по сравнению с первоначальным прямым решением):
Вспомогательная функция numberToBase (n, b), которое используется на шаге 2, преобразует целое число n в целое число основания b.Результатом является список десятичных целых чисел каждого из базы b.Чтение списка как последовательности является результирующим числом в базе b.Улучшение было достигнуто за счет использования встроенной функции divmod вместо двух команд n% b и n // = b в цикле while.Это привело к увеличению производительности в 2 раза.
Функция step2 (n, b, convsteps) преобразует данное целое число n в целое число основания b (с b= 3).Первоначально мы вызывали вспомогательную функцию numberToBase (n, b) один раз.Затем мы ввели промежуточные шаги в step2 () - так что n не было перенесено в конечную базу за один шаг, а за 3 шага.Промежуточные основания намного больше, чем конечные основания b.Эти промежуточные базовые преобразования сделали шаг 2 намного быстрее: в 60 раз.
Функция step1 () была сделана в 4 раза быстрее, читая строку в блоках и выполняяконвертация для каждого барахла в отдельности.
Любая идея приветствуется.Пожалуйста, проверьте свои идеи с помощью time (), чтобы также дать количественное представление о его преимуществах.Другие ответы, которые мы здесь проверяли, не использовали такую длинную последовательность десятичных цифр (в строке) или не фокусировались на производительности базового преобразования.