Почему разница времени выполнения генерации матриц настолько большая?

Question

Я занимаюсь профилированием кода на Python, а именно - сравнением времени выполнения двух методов генерации матриц: с помощью поэтапного заполнения циклами for, и с помощью генератора списков. При профилировании, оказалось, что разница между двумя этими способами очень большая: 0,148 сек. Выходит, что разница производительности будет больше 100%: 592%. С чем это связанно? К вопросу прилагаю код и статистику:

Код:

import cProfile
# Размеры матриц

m = 1000
n = 1000

def main_for() -> list: # Метод поэтапной генерации
    _list = [None] * 1000000

    for i in range(n):
        sec_list = []
        for j in range(m):
            sec_list.append(j)
        _list.append(sec_list)
    return _list

def main_gen() -> list: # Метод с генеератором списков
    _list = [[j for j in range(m)] for i in range(n)]
    return _list

# Запуск профилирования
cProfile.run('main_for()')
cProfile.run('main_gen()')

Статистика:

$ for.py
         1001004 function calls in 0.173 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.005    0.005    0.173    0.173 <string>:1(<module>)
        1    0.094    0.094    0.167    0.167 for.py:6(main_for)
        1    0.000    0.000    0.173    0.173 {built-in method builtins.exec}
  1001000    0.073    0.000    0.073    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


         4 function calls in 0.025 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.004    0.004    0.025    0.025 <string>:1(<module>)
        1    0.021    0.021    0.021    0.021 for.py:16(main_gen)
        1    0.000    0.000    0.025    0.025 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Answer 1

Ваши функции отличаются, как уже написано в комментарии. _list = [None] * 1000000 лишняя инициализация, которой нет во второй функции. _list = [] если бы, тогда было бы одинаково.
Вопрос, почему списковое сокращение быстрее, уже неоднократно тут обсуждался. Списковое сокращение сразу создаёт список нужного размера, если знает заранее целевой размер списка, а тут это именно так, размер range известен заранее. А вот когда список создаётся через .append, то изначально список создаётся минимального размера, а потом массив внутри списка по мере его заполнения создаётся в 2 раза больший и старый массив копируется в новый. И так много раз. А выделение памяти и копирование данных - это долго.
Такого вида матрицы проще и быстрее создать через Numpy:

import numpy as np

def main_np():
    arr = np.zeros((1000, 1000), dtype=np.int32)
    arr[:] = np.arange(1000)
    return arr

cProfile.run('main_np()')

Вывод на моём слабеньком ноуте, у вас будет ещё быстрее:

         6 function calls in 0.003 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.002    0.002    0.003    0.003 2438616932.py:3(main_np)
        1    0.001    0.001    0.003    0.003 <string>:1(<module>)
        1    0.000    0.000    0.003    0.003 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {built-in method numpy.arange}
        1    0.000    0.000    0.000    0.000 {built-in method numpy.zeros}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

А дальше можете думать - зачем вообще оптимизировать код на Питоне, когда для работы с матрицами есть специальные очень быстрые библиотеки?

БЛОГ НА HUSL

Почему разница времени выполнения генерации матриц настолько большая?

Ответы (1 шт):