python — количество циклов имеет значение для эффективности (интерпретируется против скомпилированных языков?)
Скажем, вы должны выполнить вычисления, используя 2 или даже 3 цикла. Интуитивно понятно, что более эффективно делать это с помощью одного цикла. Я попробовал простой пример Python:
import itertools
import timeit
def case1(n):
c = 0
for i in range(n):
c += 1
return c
def case2(n):
c = 0
for i in range(n):
for j in range(n):
for k in range(n):
c += 1
return c
print(case1(1000))
print(case2(10))
if __name__ == '__main__':
import timeit
print(timeit.timeit("case1(1000)", setup="from __main__ import case1", number=10000))
print(timeit.timeit("case2(10)", setup="from __main__ import case2", number=10000))
Этот код запускается:
$ python3 code.py
1000
1000
0.8281264099932741
1.04944919400441
Так что эффективно 1 цикл кажется немного более эффективным. Тем не менее у меня есть немного другой сценарий в моей проблеме, так как мне нужно использовать значения в массиве (в следующем примере я использую функцию range для упрощения). То есть, если я сверну все в один цикл, мне придется создать расширенный массив из значений другого массива, размер которого составляет от 2 до 10 элементов.
import itertools
import timeit
def case1(n):
b = [i * j * k for i, j, k in itertools.product(range(n), repeat=3)]
c = 0
for i in range(len(b)):
c += b[i]
return c
def case2(n):
c = 0
for i in range(n):
for j in range(n):
for k in range(n):
c += i*j*k
return c
print(case1(10))
print(case2(10))
if __name__ == '__main__':
import timeit
print(timeit.timeit("case1(10)", setup="from __main__ import case1", number=10000))
print(timeit.timeit("case2(10)", setup="from __main__ import case2", number=10000))
На моем компьютере этот код работает в:
$ python3 code.py
91125
91125
2.435348572995281
1.6435037050105166
Таким образом, кажется, что 3 вложенных цикла более эффективны, потому что я трачу некоторое время на создание массива b в case1, поэтому я не уверен, что я создаю этот массив наиболее эффективным способом, но если оставить это в стороне, действительно ли он окупает сворачивающиеся циклы для одного? Я использую Python, но как насчет скомпилированных языков, таких как C ++? Компилятор в этом случае делает что-то для оптимизации одного цикла? Или, с другой стороны, компилятор выполняет некоторую оптимизацию, когда у вас есть несколько вложенных циклов?
Решение
Вот почему функция с одним циклом занимает предположительно больше времени, чем следует
b = [i * j * k for i, j, k in itertools.product(range(n), repeat=3)]
Просто изменив всю функцию на
def case1(n, b):
c = 0
for i in range(len(b)):
c += b[i]
return c
Делает время возврата
case1 : 0.965343249744
case2 : 2.28501694207
Другие решения
Ваш случай достаточно прост, чтобы различные оптимизации, вероятно, многое сделали. Будь это numpy для более эффективного массива, возможно pypy для лучшего оптимизатора JIT, или различных других вещей.
Глядя на байт-код через dis Модуль может помочь вам понять, что происходит под капотом, и выполнить некоторые микрооптимизации, но в целом не имеет значения, выполняете ли вы один цикл или вложенный цикл, если ваш шаблон доступа к памяти несколько предсказуем для ЦП. Если нет, это может сильно отличаться.
В Python есть несколько дешевых байт-кодов, а другие более дорогие, например, вызовы функций намного дороже, чем простое дополнение. То же самое с созданием новых объектов и различных других вещей. Таким образом, обычная оптимизация перемещает цикл в C, что является одним из преимуществ itertools иногда.
Как только вы попадаете на уровень C, это обычно сводится к следующему: избегайте syscalls / mallocs () в тесных циклах, используйте предсказуемые шаблоны доступа к памяти и убедитесь, что ваш алгоритм поддерживает кеш.
Таким образом, приведенные выше алгоритмы, вероятно, будут сильно отличаться по производительности, если вы перейдете к большим значениям N из-за объема выделенной памяти и доступа к кешу.
Но самый быстрый способ решения указанной выше проблемы — найти замкнутую форму для функции, итерирование для этого кажется расточительным, так как должна существовать гораздо более простая формула для вычисления окончательного значения ‘c’. Как обычно, сначала получите лучший алгоритм перед выполнением микрооптимизации.
например Вольфрам Альфа говорит вам, что вы можете заменить две петли, возможно, для всех трех есть закрытая форма, но Альфа не сказала мне …
def case3(n):
c = 0
for j in range(n):
c += (j* n^2 *(n+1)^2))/4
return c