Ускоряем вложенные циклы на 30% 

Продолжение и дополнение темы в следующем видео: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-U9b02QW9D2Q.html

В small_outer_loop еще процент попадания в кеш процессора будет выше т.к. при обращении к table[row][column] вероятность попадания в кеш выше если на предыдущей итерации мы обращались к table[row][column-1] чем если мы обращались table[row-1][column] Для чистоты эксперимента я бы попробовал с одинаковыми значениями ROWS и COLUMNS запустить чтобы еще понять на сколько влияет кеш

на 03:09 то что ты называешь iterations - это скорее количество запусков блоков кода общее количество итераций операции суммирования все равно остается ROW*COLUMN то есть переход из блока в блок выполнения отнимает время, занятно

Привет, интересные мысли, как и сам ролик. По идее разница возникает в количестве инициализации inner loop и чем больше outer loop, тем медленнее код: n + (n*m)*c, где n - outer, m - inner, c - extra time какое-то действие. Ну и по ходу, в кеш будет больше попаданий при row traversal, чем в column traversal, кеш в линию хранится конкретно в C/C++, в других языках возможно другое будет... Ведь какой из факторов наиболее важный: Количество инициализаций и итераций, доступ к памяти, хешируемость?

классненько, благодарочка!) от души:)

Круто, спасибо за полезную инфу)

Я программированием не занимаюсь и то понял в чем фишка. А фишка в том, что переменная iteretion расположена и во внешнем и во внутреннем цикле. А правильно было располагать только во внутреннем цикле. А из за того, что эта переменная нарастает в обоих циклах, то да в первом случае до 600, а во втором до 505, вот на это время и тратится, а если эту переменную оставить только во внутреннем цикле то в обоих случаях itatetion=500 будет и время выполнения большого и малого станет , наверно, одно и то же.

В более сложных структурах может появится еще одна ось z - трехмерная матрица. Там уже будет три цикла - по матрицам, по строкам и в конце по колонкам строки матрицы.

Тоопчик! Очень интересно!

Кстати, tuple(… for … in …) будет работать на ⅓ медленнее, чем tuple([… for … in …]), но во время выполнения работы должно занимать несколько больше памяти (it depends насколько)

Интересно что автор увидел лишние итерации, но не понял что именно влияет на производительность и сделал неверные выводы

было интересно, даже не задумывался об этом раньше

Пишу на второй минуте просмотра. Что если поменять местами? То есть поменять порядок выполнения. Сначала small, потом big. Что если данные из этих таблиц после первого прогона задерживаются в кэше процессора, поэтому и скорость разная?

Спасибо большое. Очень понравилась. Глаза открылыись на то,что такое есть. Прям прикольно

подскажите пожалуйста я только начал изучать пайтон в самом начале мы же просто делаем кортеж кортежей каким образом он выводиться табличкой а не одной строкой

Познавательно, спасибо

Забавно, что эта оптимизация имеет место быть в любом ЯП, никогда об этом прежде не задумывался :) Рассмотрим простейший код на ассемблере (MASM x86): mov ecx, 0 outerLoop: cmp ecx, 100 je done mov ebx, 0 innerLoop: cmp ebx, 5 je innerLoopDone inc ebx jmp innerLoop innerLoopDone: inc ecx jmp outerLoop done: ----- Видим, что ecx == row, ebx == column, и, соответственно, тела внутреннего и внешнего циклов отличаются всего одной коммандой - `mov ebx,0` - той самой инициализацией внутреннего цикла (обнулением счетчика ebx). Соответственно, единственное отличие между big_outer_loop и small_outer_loop - количество обнулений счётчика, которое и является первоисточником разницы в скорости выполнения :) Ради интереса воссоздал пример автора на C, с отключенной оптимизацией: скорость выполнения двух циклов отличается на ~15%, и, по сути, заключается в одной лишь дополнительной комманде ассембли... (ну и само собой в кэшировании данных процессором, но это уже другая история)

Супер, информативно, спасибо )

Можно ли внутри функции «пересобрать» структуру, чтобы можно было применить map и ускорит ли это исполнение?

Если вспомнить что питон позволяет "нормально" итерировать объекты - без индексов, а просто "for item in iterable", и писать функцию в таком стиле - "for row in table: for column in row: overall_time += column", то можно сэкономить еще немного времени (у меня получается что "нормальный" цикл быстрее суммы на 15-20%)

Ну это же логично, если первый цикл содержит малый размер а второй больше, то кеш будет быстрей работать, а если сделать наоборот то кеш будет чаще обновляться тем самым появиться такая разница во времени исполнения. Это как для олдов которые с СД диска устанавливали приложения и игры, большой файл быстрей считывался и записывался, нежели чем более мелкие

И по поводу функции sum, она реализована на CPython по этому и быстрей работает чем обычные итерированные сложения

Будет чудно, если собеседующий задаст вопрос по nested loops после этого видео, а кандидат ответит потому, что посмотрел это видео.

Как работает range() в питоне? Чую что в медленном случае просто больше выделений памяти из за этого

Большое спасибо, буду знать. Как раз пишу приложение для работы с sql

Спасибо за лабу! А что интерпретатор при вызове sum() дёргает?

Урааа! Котаны долго без видео быть не могут, а тут видос подъехал!

Не очень понял, почему итерации различаются. На питоне много лет не писал, потому не очень понимаю какая итоговая размерность таблички. Допустим 5 x 100, тогда какая разница в каком порядке проходить, если в итоге нужно пройтись по 500 ячейкам? Выглядит так, что в видео была лишняя итерация и весь выхлоп в её уменьшении, но тогда не понятно отличаются ли значения после суммирования двумя методами или в чём прикол?

Алексей, можете, пожалуйста, подробнее объяснить, что вы имеете в виду на 3:45? Сейчас для меня это выглядит так, что вы отрицаете коммутативность умножения, зачем-то прибавляя единицу каждую итерацию внешнего цикла.

Все зависит от значений ROWS и COLUMNS, если сначала пробегать по значению, которое меньше - оно и будет быстрее, если они одинаковые - разницы не будет

периодически смотрю твои видео 3-5 летней давности (отличный контент) и замечаю, что ты постарел( и я тоже, просто на себя чаще смотрю), но ты еще и красавчик, отличный контент делаешь, спасибо

В университете на архитектуре вс узнал об этом и еще множество других интересностей про кластерные вычисления. Весь курс был построен на подсчете времени вычисления при разных условиях.

Кажется в комментах непонимание того, что автор имел в виду под словом "итерация", что же всё-таки подсчитывает переменная iterations. Здесь мы подсчитываем сколько раз за эти два вложеных цикла вычислялись loop conditions. Не важно, что там в теле цикла. Эти самые loop conditions не бесплатны. Ну и инкрементт переменной цикла тоже чего-то стоит. IMO

Для данного примера более подходящий такой вариант с sum print(sum(sum(matrix, []))). Вариант с функцией sum может быть быстрее, еще и из за List comprehensions. К тому же для чистоты эксперимента не был рассмотрен обратный вариант для sum.

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

Кэши, счетчики, что считать итерациями, это-то всё ладно. В итоге-то, что с чем джойнить надо? К маленькой таблице данные из большой, или к большой таблице данные из маленькой? Или что имеется в виду, как это с джойнами-то применять?

стоп на 5:52 : предполагаю, что sum должен быть может и не намного, но быстрее, поскольку очень может быть, что это просто обёртка над C, а на уровне С-кода можно использовать всякие интрисики и SIMD-инструкции.... Хотя... Может для меленькой коллекции переход на уровень C-кода сам по себе может быть достаточно дорогой, что сожрёт всю оптимизацию, поётому может быть sum использует опимизации уровня питон, что были показаны ранее. Посмотрим дальше.... UPD: а вот тут инженерная чуйка не подвела :) Осталось прокачать внимательность и навык, чтобы даже в развлекательном видео включать больше мозга и будет вообще зашибись :)

Только недавно делали лабораторку в универе Проверяли в каком порядке цикл i-j-k быстрее работает

А насколько это применимо в реальной разработке? Например, у нас есть таблица сущностей, а если количество атрибутов сущности произвольное?

С открытой челюстью всё видео сидел

Основная разница в количестве запуска функции range Если убрать range, а итерироваться по готовым спискам, разница будет меньше ```python import timeit ROWS = 5 COLUMNS = 100 TIMEIT_ITERATIONS = 100_000 for i in range(ROWS): small_outer.append([1]*COLUMNS) for i in range(COLUMNS): big_outer.append([1]*ROWS) def big_outer_loop(): overall_sum = 0 for columns in big_outer: for row in columns: overall_sum += row def small_outer_loop(): overall_sum = 0 for row in small_outer: for column in row: overall_sum += column small_outer_loop_time = round(timeit.timeit(small_outer_loop, number=TIMEIT_ITERATIONS), 2) big_outer_loop_time = round(timeit.timeit(big_outer_loop, number=TIMEIT_ITERATIONS), 2) print(f"{big_outer_loop_time=}, {small_outer_loop_time=}") # big_outer_loop_time=1.01, small_outer_loop_time=0.78 delta = round(100*(big_outer_loop_time - small_outer_loop_time) / big_outer_loop_time) print(f"{delta}%") # 20% ```

Одно не понял, где это нужно использовать?

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

Сначала показалось, что автор что-то не понял, мне казалось, что проблема с обращением к памяти. Решил потестить на js. Аналогичный пример как у автора 35% процентов в туже сторону(итераций было побольше правда). Заменил обращение к памяти на Math.random. Разница снизилась до около 1%, причем иногда менялась функция которая выполнялась быстрее. Решил, что вот оно, т.к. запусков много было, результат болтался в районе 1% и значит автор не прав. Заменил Math.random на 1(грубо говоря сумма равна в итоге 500) и разница по времени стала равна около 13%. Видимо все-таки проблема во вложенных циклах, надо попробовать на чем-нибудь компилируемом, возможно там будет другая картина. P.S. с универа как-то привык сначала по строкам итерировать, затем по колонкам, но никогда не думал о таком поведении, автору спасибо

Как разработчик на С++, был сильно удивлён. Не поверил и пошёл проверять с ROWS = 100 и COLUMNS = 5. Из примера выходит, что производительность определяет не количество суммирований и обращений к таблице (оно в обоих функциях одинаковое), а количество операций for ... in ... Работа циклов НАСТОЛЬКО медленная, что при увеличении операций с 500 до 600, получается на 30% дольше... Не знаю насколько в этом случаем решает кэш, т.к. не знаю как питон хранит в памяти tuple.

Тестировал не на локальной машине, в онлайн редакторе, но если немного увеличить количество данных, например 50х100. То независимо от того, чего будет больше(строк или столбцов) цикл сначала по строкам, а потом по столбцам работает быстрее. Т.е. в обоих случаях ROWS = 100 COLUMNS = 50 и ROWS = 50 COLUMNS = 100 цикл сначала по строкам предпочтительней. Так что совет "меньшее количество шагов во внешнем цикле - лучше" - не универсальный. Так что дефолту лучше использовать стандартный обход - сначала по строкам, потом по столбцам, если речь идет о двумерном массиве. Sum скорее всего может использовать SIMD.

Похоже это базовая особенность вложенных циклов как алгоритма... Вот уж спасибо вам что обратили внимание на такой эффект!

вспоминаем недавний видос про клин код и оптимизацию. "да кому эта оптимизация нужна. это все io задержки, тут ускоришь - там замедлишь и т.д". ну вот кому эта оптимизация на 30% в вебе нужна?)

прикольно) для меня неочевидная штука была)

Забавно, но если поменять местами 5 и 100 в количестве элементов, то пример с суммой начинает жестко проигрывать big_outer_loop_time=2.58, small_outer_loop_time=3.56, with_sum_time=5.21 Тут по сути сейчас названия big и small нужно бы поменять местами, но речь не о них

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

Что за конструкция генерации таблицы? Синтаксис странно выглядит

Интересно, интересно :)))))))) Спасибо за видосик!

не привычно видеть у тебя бесплатные видосы :)

В реальной жизни, даже если вдруг приспичило проитерироваться по n-мерной структуре, логика обычно требует еще и нужного порядка итерирования.

Здарова. очень интересно, вылизывать код конечно нужно, в данном случае внешних циклов нужно делать меньше а вложенные с большими циклами, ладно если запомню то может когда понадобится так сделаю.

Вы неверно посчитали итерациии. Точнее не все из них равноценные. Смысл подсчета итераций есть лишь тогда, когда на каждую из них производится определенное действие, требующее вычислительной мощности (притом всегда одинаковой) Рассмотрим пример. Надо подятнуться на турнике 500 раз. Подтягивание - то самое действие, которое требует сил (вычислительной мощности). Пройдемся по вашему алгоритму подсчета. 5 подходов по 100 потягиваний 1) Еще не начав потягиваться мы защитали себе одно подтягивание 2) Потом потянулись 100 раз и защитали себе 100 потягиваний 3) Опять защитали себе одно потягивание 4) Потянулись 100 раз и защитали себе 100 потягиваний ... Итого получиться, что мы потянулись 500 раз, но защитали себе 500 + 5 = 505 подтягиваний 100 подходов по 5 подтягиваний 1) Еще не начав потягиваться мы защитали себе одно подтягивание 2) Потом потянулись 5 раз и защитали себе 5 потягиваний и так п.1-2 повторяем 100 раз. Получается, что мы защитаем уже лишних 100 подтягиваний. Итого получиться, что мы потянулись 500 раз, но защитали себе 500 + 100 = 600 подтягиваний Но это же бред так считать подтягивания) Вот бы я в школе на физре их так считал)

Такой подсчет итераций противоречит алгоритмической сложности, да и лишние 100 элементов из воздуха не возьмутся от перестановки циклов. То что здесь считается, это количество сравнений. Кеш тут тоже не причем т.к. из структур которые должны туда попадать тут (конкретно в коде из закрепленного комментария) 3 счетчика и 2 константы на функцию. Разница по большей части из-за операций сравнения. Но, что я не понял почему плоский цикл ниже выполняется дольше малого. ROWS = 5 COLUMNS = 100 ALL = ROWS * COLUMNS def flat_loop(): overall_sum = 0 for _ in range(ALL): overall_sum +=1

Интересно ещё было бы посмотреть на вариант sum(cell for row in table for cell in row) Имею подозрение, что это будет самое быстрое нативное решение. UPD: увидел, что тему уже поднимали

Годно

Что то мне подсказывает , что количество строк или колонок будет коррелировать с разницей производительности.

Ничего не понял как это получается циклов меньше (надо проверять самому, а сейчас лень), но было ОЧЕНЬ интересно!

В других языках такое-же поведение? в PHP, C++, Go, TS ?

Действительно, если внешний цикл выполняется i-раз, а внутренний j-раз, то всего будет: i * j + i вычислений в области видимости строк "for". А так сходу и не очевидно было.

Когда-то я по приколу писал алгоритм, заменяющий в тексте все согласные на противоположные им (для согласной являющейся пятой с начала алфавита берётся согласная пятая с конца алфавита и так далее). Так вот, взял я словарь от какого-то русского синтезатора речи, словарь на 70 мегабайт в koi-8r кодировке. Изначально мой алгоритм работал с этим словарём примерно за 59 секунд. После перевкладывания циклов так, чтобы внешний цикл был меньше, я получил ускорение с 59 секунд до 14 секунд. Там конечно вмешалось и существенное уменьшение количества вызовов replace, но это было прям вау как круто. Только вот тот же алгоритм, будучи реализованным на Go, работает примерно за 6 секунд, а реализация на Lua отрабатывает примерно за 10 11 секунд, что увы не в пользу Питона.

1:10 Ответ на вопрос до просмотра видео - да, есть разница, выгоднее внешний цикл делать с меньшей стороной, так уменьшается количество _инициализаций_ внутреннего цикла. 2:52 Замечание по ходу - было бы правильнее называть не итерациями, а проверкой условия в цикле, поскольку итерации внутреннего проходят во время итерации внешнего, а не где-то рядом дополнительно. В итоге сумма всегда увеличивалась 500 раз, а условия циклов проверялись соответственно 100+5*100=600 и 5+100*5=505 раз. Параллельное представлено как последовательное. И отмечу, что это не 30% разница, то есть не единственный фактор. Но общая мысль интересная, спасибо.

про функцию with_sum, на сколько знаю комприхеншены быстрее обычных циклов, тоже свою роль сыграло

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

Фантастика!

sum на C же написана?

Что за sum(column for column for row)? Оно же эквивалентно sum(row)

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

А ксли сделать ROWS=100, а COLUMNS=5?

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

Может всё потому что в памяти все двумерные массивы содержаться в виде массива из массивов элементов. То есть строки, содержат колонки элементов.

все равно не понятно, как количество итераций разное. в первом случае ROWS*COLUMNS, во втором COLUMNS*ROWS - должно же совпадать. разница в производительности доказана, вопросов нет. но объяснение не объясняет :)

Я в шоке от того, насколько это лежит на поверхности, но несмотря на это даже никогда не задумывался об этом. Круто!

Я так понимаю, это справедливо для всех подобных случаев и всех ЯП?

а в школе между прочим нас учили что от перестановки двух чисел множимого и множителя ничего не меняется, а тут на тебе, оказывается есть разница, ну кроме ответа конечно.

Блин, думал я о том, что это влияет, но не знал, что настолько сильно. Постараться бы теперь это учесть при кодинге.

Так это зависит от задачи, если у тебя будет 100 рядков и 5 колонок то первый отработает быстрее, это же логика в количестве переключений как раз таки, в одном случае мы переключаемся как ты сказал всего 5 раз а в другом 100, потому что разрядность матрицы - 100

Офигеть. Сначала мозг сломался а потом понял, типа rows умножаем на columns только внутри а во внешнем цикле кол-во интераций равно внешнему, а я всегда думал что кол-во итераций просто можно получить умножением)

Из серии 'лучше быть богатым и здоровым, чем бедным и больным'. И так все очевидно. Чем меньше обращений к памяти, тем быстрее. Читать большой чвнк и бежать по нему проще, чем по куче мелких чанков. Да и суммирующая функция (скорее всего написана на С) бежит по внутренним структурам объекта, игнорируя интерпретационные накладные расходы.

В small_outer_loop числа с большей вероятностью будут находиться в одних линиях кэша. Поэтому и быстрее

Вот блин... Очевидно же, но не задумываешься... Хотя я внешним циклом всегда по строками иду по привычке, но всё равно прикольно

Алексей в этом видео похож на Колина Фаррелла в Джентельменах)

вместо sum(sum(item for item in row) for row in table) стоило использовать sum(item for row in table for item in row)

А еще в sql join большой таблицы к маленькой быстрее чем наоборот

Все такие удивленные)) Это база при решении алго задач, то чувству когда думал что это очевидная штука, а её ни кто не знает:DD

У меня чере sum() чуть быстрей получилось, еще чуть быстрее через enumerate(), и 30% быстрее for r in table: for c in r: sum+=c

есть вариант быстрее всех этих (но хуже по памяти в некоторых случаях): sum(reduce(operator.add, table))

Скорее всего особенность языка - на c++ оба обхода идентичны по производительности

sum(map(sum, table)) в 10 раз быстрее, чем оба варианта с циклами

блин, всегда делаю вложенные джойны с более точным условием, чтобы выборка в джойне была меньше, на код ревью уже какой раз лид заворачивает, чтобы часть условия в джойне перенес в общее условие where ) ... показать ему видео, чтоли )))

Суммарное количество итерация: s = i + ij, а не ij получается, здорово!

Количество итераций не правильно считаете

Что за взрыв мозга 🤯 в хорошем смысле))))

Не понимаю, зачем считать одну итерацию больше одного раза (когда счетчик инкрементируется во внутреннем и внешнем циклах), полная же глупость. И вся оптимизация, скорее всего (с питоном не знаком), заключается в количестве промахов в кеш процессора. Я для тестов использовал такой же код и таблицу размером 5x1000, но после первого прогона пересоздал таблицу как 1000x5, результаты ниже. ROWS: 5 COLS: 1000 big_outer_loop_time: 18.37 small_outer_loop_time: 14.28 ROWS: 1000 COLS: 5 big_outer_loop_time: 14.33 small_outer_loop_time: 18.4

если бы это было правдой, то компиляторы давно бы так все коды оптимизировали

А имеет ли смысл итерироваться по колонкам ? Колонка сама по себе не несёт ценности. Например возьмём колонку и там будет Анна, Сергей, Денис. А нам интересно Анна, 22.02.1992, аналитик, 100000 рублей