Оптимизация кода Python для 4-х строчной программы - PullRequest
Новая
       8

Оптимизация кода Python для 4-х строчной программы

0 голосов
/ 17 мая 2018

У меня сейчас есть рабочая программа: 

from math import sqrt
def list_squared(m, n):
    #sum of the squared divisors of a number
    def D(x):return sum([i**2 for i in range(1,x+1) if not x%i])
    #returns array of arrays containing each num and D(num) from m to n if D(num) is square 
    return [[i,D(i)] for i in range(m,n) if sqrt(D(i)).is_integer()]

Однако эта программа не выполняется достаточно быстро, чтобы сервер мог считать ее рабочим решением.Я никогда раньше не работал над оптимизацией кода и мог бы использовать некоторую справку о том, как сделать так, чтобы это выполнялось быстрее.

Программа является решением следующей проблемы:

Делителииз 42: 1, 2, 3, 6, 7, 14, 21, 42. Эти делители в квадрате: 1, 4, 9, 36, 49, 196, 441, 1764. Сумма квадратов делителей 2500, которая50 * 50, квадрат!Учитывая два целых числа m, n (1 <= m <= n), мы хотим найти все целые числа между m и n, у которых сумма квадратов делителей сама является квадратом.42 такое число.Результатом будет массив массивов, каждый из которых содержит два элемента: сначала число, у которого квадратные делители являются квадратами, а затем сумма квадратов. </p> 

#Examples
list_squared(1, 250) --> [[1, 1], [42, 2500], [246, 84100]]
list_squared(42, 250) --> [[42, 2500], [246, 84100]]

1 Ответ

0 голосов
/ 17 мая 2018

Вероятно, это не самый лучший ответ на этот вопрос, но я бы решил оптимизировать этот конкретный код.Это скорее начало, чем окончательный результат, но ... ну ... вот так: 

import time
from math import sqrt


ITERATIONS = 10000


def timer(func, *args, **kwargs):
    start = time.time()
    for _ in range(ITERATIONS):
        func(*args)
    print("%s at %s iterations took %s" % (func.__name__, ITERATIONS, time.time() - start))


def list_squared(m, n):
    # base function
    #sum of the squared divisors of a number
    def D(x):return sum([i**2 for i in range(1, x+1) if not x % i])
    #returns array of arrays containing each num and D(num) from m to n if D(num) is square
    return [[i, D(i)] for i in range(m, n) if sqrt(D(i)).is_integer()]


def D(x):
    return sum([i**2 for i in range(1, x + 1) if not x % i])


def list_squared_opt1(m, n):
    # reduce the amount of function overhead
    ret_list = list()
    for i in range(m, n):
        tmp = D(i)
        if sqrt(tmp).is_integer():
            ret_list.append([i, tmp])
    return ret_list


def list_squared_opt2(m, n):
    # further reduce the amount of function overhead
    ret_list = list()
    for i in range(m, n):
        tmp = sum([x**2 for x in range(1, i + 1) if not i % x])
        if sqrt(tmp).is_integer():
            ret_list.append([i, tmp])
    return ret_list


def list_squared_opt3(m, n):
    # Improve the math overhead to not check for impossible divisors
    ret_list = list()
    for i in range(m, n):
        tmp = sum([x ** 2 for x in range(1, int(i / 2 + 1)) if not i % x]) + i ** 2
        if sqrt(tmp).is_integer():
            ret_list.append([i, tmp])
    return ret_list

def list_squared_opt4(m, n):
# Further reduce function overhead
ret_list = list()
for i in range(m, n):
    a = int()
    for x in range(1, int(i / 2 + 1)):
        if not i % x:
            a += x ** 2
    a += i ** 2
    if sqrt(a).is_integer():
        ret_list.append([i, a])
return ret_list

print("Timing results for various functions, then executing them once to validate the results")
timer(list_squared, 42, 250)
print("Results are: %s" % list_squared(42, 250))
timer(list_squared_opt1, 42, 250)
print("Results are: %s" % list_squared_opt1(42, 250))
timer(list_squared_opt2, 42, 250)
print("Results are: %s" % list_squared_opt2(42, 250))
timer(list_squared_opt3, 42, 250)
print("Results are: %s" % list_squared_opt3(42, 250))
timer(list_squared_opt4, 42, 250)
print("Results are: %s" % list_squared_opt4(42, 250))

Это выводит: 

/usr/test/venv/bin/python /usr/test/blah.py
Timing results for various functions, then executing them once to validate the results
list_squared at 10000 iterations took 16.172016859054565
Results are: [[42, 2500], [246, 84100]]
list_squared_opt1 at 10000 iterations took 15.923789834976196
Results are: [[42, 2500], [246, 84100]]
list_squared_opt2 at 10000 iterations took 15.620330572128296
Results are: [[42, 2500], [246, 84100]]
list_squared_opt3 at 10000 iterations took 11.640689611434937
Results are: [[42, 2500], [246, 84100]]
list_squared_opt4 at 10000 iterations took 10.224685668945312
Results are: [[42, 2500], [246, 84100]]

Process finished with exit code 0

Теперь для некоторого объяснения.То, что я пытаюсь отобразить, является средством итеративного подхода к оптимизации кода.В первой паре модифицированных функций мы тестируем что-то довольно простое, модифицируя структуру кода, чтобы ограничить количество вызовов функций, что в теории должно сэкономить некоторое время, хотя это кажется незначительным.Пока что самый большой эффект - оптимизация математики в функцииЕсть еще несколько вещей, которые я бы попробовал:

  • Использование протектора или многопроцессорной обработки, чтобы лучше учитывать доступные системные ресурсы (в настоящее время это однопоточное приложение)
  • Ищите более эффективные способычтобы найти делители (возможно, NumPy или какой-либо лежащий в основе C lib)
  • Дальнейшая оптимизация математики ... Я не тратил много времени на это, но все же кажется, что это возможно
  • Тестирование более быстрых структур данных, возможно, кортежи в возвращаемом списке будут быстрее (в зависимости от количества результатов) и т. Д.

Надеюсь, это поможет ...

...