Число циклов имеет значение эффективности (интерпретируется как скомпилированные языки?)

Question

Скажите, что вам нужно выполнить вычисление с использованием 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++? Составляет ли компилятор в этом случае что-то для оптимизации одного цикла? Или, с другой стороны, делает ли компилятор некоторую оптимизацию, когда у вас несколько вложенных циклов?

Answer 1

Поэтому функция одноконтурный занимает предположительно больше, чем это должно

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 

делает возвращение timeit:

case1 : 0.965343249744 
case2 : 2.28501694207 

Answer 2

Ваш случай достаточно прост, что различные оптимизации, вероятно, многое сделают. Будь то numpy для более эффективного массива, может быть pypy для лучшего оптимизатора JIT или других вещей.

Глядя на байт-код через модуль dis, вы можете понять, что происходит под капотом, и сделать некоторые микро оптимизации, но в целом не имеет значения, если вы делаете один цикл или вложенный цикл, если ваш шаблон доступа к памяти несколько предсказуемо для CPU. Если нет, это может сильно отличаться.

У Python есть несколько байт-кодов, которые дешевы, и другие, которые стоят дороже, например. вызовы функций намного дороже, чем простое дополнение. То же самое с созданием новых объектов и других вещей. Таким образом, обычная оптимизация перемещает цикл на C, что иногда является одним из преимуществ itertools.

Как только вы находитесь на уровне C, он обычно сводится к: Избегайте syscalls/mallocs() в узких петлях, имеют предсказуемые шаблоны доступа к памяти и убедитесь, что ваш алгоритм является кешем.

Таким образом, ваши алгоритмы выше, вероятно, будут сильно отличаться в производительности, если вы перейдете к большим значениям N из-за объема выделения памяти и доступа к кешу.

Но самым быстрым способом для конкретной проблемы, описанной выше, было бы найти закрытую форму для функции, для нее кажется ненужной итерация, поскольку для вычисления конечного значения «c» должна быть гораздо более простая формула. Как обычно, сначала получите лучший алгоритм, прежде чем выполнять микрооптимизацию.

например. Wolfram Alpha говорит вам, что вы могли бы заменить две петли с, вероятно, есть замкнутая форма для всех трех, но Альфа не сказал мне ...

def case3(n): 
    c = 0 
    for j in range(n): 
     c += (j* n^2 *(n+1)^2))/4 
    return c