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

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

Делает время возврата

case1 : 0.965343249744
case2 : 2.28501694207

Answer 2

Ваш случай достаточно прост, чтобы различные оптимизации, вероятно, многое сделали. Будь это 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