Ускоряем вложенные циклы на 30%
Мой курс «Хардкорная веб-разработка» - course.to.digital
Книжный клуб Ботаним!, где мы читаем хорошие ИТ-книги: botanim.to.digital/
Telegram - t.me/t0digital
/****************** about ******************/
Меня зовут Алексей Голобурдин, я программирую с 2004 года и на этом канале делюсь своим опытом. Я основатель и руководитель компаний:
- Диджитализируй digitalize.team, разрабатываем сложные IT системы для бизнеса;
- Salesbeat salesbeat.pro, комплексный модуль доставки для интернет магазинов.
Telegram канал - t.me/t0digital
ВК - digitalize.team
RuTube - rutube.ru/channel/24802975/ab...
Дзен - dzen.ru/id/6235d32cb64df01e6e...
Пікірлер: 398
Продолжение и дополнение темы в следующем видео: kzread.info/dash/bejne/h22WkpSKh5yqYrQ.html
@user-vr6qh7ve5b
14 күн бұрын
Но ведь в этом варианте тоже влияет кеш, так как достаются значения row и column из результата вызова функции range.
@t0digital
14 күн бұрын
в обоих случаях они достаются, как кеш объясняет разницу результатов?
@HaisTous
14 күн бұрын
В big_outer_loop() range вызывается 1 + 100 = 101 раз, а в small_outer_loop() - 1 + 5 = 6 раз. В иделе еще вызов функции range вынести за циклы.
@strikez3831
14 күн бұрын
Тогда и стоило, наверное, такой пример юзать в видосе, а не разные проходы по таблице, где твоя оптимизация наоборот сильно ухудшит ситуацию с большим количеством строк
@user-vr6qh7ve5b
14 күн бұрын
@@t0digital могу предположить, что сам объект range (c-шный) лежит в кеше разное время, также в процессорах существуют механизмы предсказания ветвления и более предсказуемые задачи быстрее выполняются.
В small_outer_loop еще процент попадания в кеш процессора будет выше т.к. при обращении к table[row][column] вероятность попадания в кеш выше если на предыдущей итерации мы обращались к table[row][column-1] чем если мы обращались table[row-1][column] Для чистоты эксперимента я бы попробовал с одинаковыми значениями ROWS и COLUMNS запустить чтобы еще понять на сколько влияет кеш
@t0digital
15 күн бұрын
Если таблица квадратная, то внешний цикл равен внутреннему по количеству итераций ведь:) нечего менять тестить
@losos6069
15 күн бұрын
@@t0digital > то внешний цикл равен внутреннему по количеству итераций ведь Одна ф-ия обходит матрицу по строкам, другая по столбцам. И я считаю что будет разный процент попадания в кеш процессора при обращении к элементу массива. Но на сколько реально заметна разница будет я не очень уверен. Возможно эффект будет виден только на матрицах больших размерностей попробую у себя потестить P.S. Для матрицы 10x10 нет разницы как ее обходить по столбцам или строкам, но на размерности 1000x1000 уже разница в 25%
@undefined4992
15 күн бұрын
@@losos6069 у себя потестил, вроде нет никакой статистически значимой разницы (вбил просто код из начала видео, взял 10 * 10 матрицу и 100_000 итераций)
@crazy_kayaker
15 күн бұрын
Для полной чистоты эксперимента можно тогда попробовать число столбцов и строк местами поменять, чтобы строк было больше чем столбцов. Уверен что в таком случае если прирост в производительности и будет, то явно меньше чем в рассмотренном случае. Соглашусь с автором комментария и скажу, что скорее всего бОльший прирост дало эффективное использование кэша процессора, нежели экономия инкрементов счетчика) Хотя не сомневаюсь, что такая микрооптимизация тоже может сыграть свою роль в подходящей ситуации. P. S. Стоит отметить, что нюанс с памятью более заметен в языках, которые могут оперировать с указателями (в частности C++), но от этого питон не перестает быть для меня одним из любимых языков)
@MrApachik
15 күн бұрын
@@undefined4992 матрица 10*10 недостаточно велика по сравнению с длиной строки кэша...
на 03:09 то что ты называешь iterations - это скорее количество запусков блоков кода общее количество итераций операции суммирования все равно остается ROW*COLUMN то есть переход из блока в блок выполнения отнимает время, занятно
@t0digital
14 күн бұрын
> общее количество итераций операции суммирования все равно остается ROW*COLUMN Да. Но это НЕ общее количество итераций двух циклов, а на производительность влияет не только операция суммирования overall_sum (как видно хотя бы из результата теста)
@t0digital
13 күн бұрын
@@IvanIvanov-sx2fy а увеличение счетчика на каждой итерации цикла, проверка счетчика на каждой итерации цикла это тоже инициализация, да, уважаемый незапутавшийся комментатор:)?
@t0digital
13 күн бұрын
@@user-uc6wo1lc7t возвожу в степень 0.5!
@t0digital
12 күн бұрын
@@IvanIvanov-sx2fy итерация внешнего цикла связана с работой внешнего цикла, итерация внутреннего цикла связана с внутренним циклом. Это 2 разные итерации. В итерации внешнего цикла происходит работа со счетчиком внешнего цикла, в итерации внутреннего цикла происходит работа со счётчиком внутреннего цикла.
Привет, интересные мысли, как и сам ролик. По идее разница возникает в количестве инициализации inner loop и чем больше outer loop, тем медленнее код: n + (n*m)*c, где n - outer, m - inner, c - extra time какое-то действие. Ну и по ходу, в кеш будет больше попаданий при row traversal, чем в column traversal, кеш в линию хранится конкретно в C/C++, в других языках возможно другое будет... Ведь какой из факторов наиболее важный: Количество инициализаций и итераций, доступ к памяти, хешируемость?
классненько, благодарочка!) от души:)
Круто, спасибо за полезную инфу)
@t0digital
14 күн бұрын
завтра выпущу дополнение. Не всё так однозначно😂
Я программированием не занимаюсь и то понял в чем фишка. А фишка в том, что переменная iteretion расположена и во внешнем и во внутреннем цикле. А правильно было располагать только во внутреннем цикле. А из за того, что эта переменная нарастает в обоих циклах, то да в первом случае до 600, а во втором до 505, вот на это время и тратится, а если эту переменную оставить только во внутреннем цикле то в обоих случаях itatetion=500 будет и время выполнения большого и малого станет , наверно, одно и то же.
@AlexanderBorshak
14 күн бұрын
Так и есть, кол-во итераций должно быть 500 и в том, и в другом случае. Время исполнения все же может отличаться, и это может быть связано с разными факторами - помещаются ли все данные итерации в кеш, как данные хранятся / индексируются внутри языка (доступ к рядом лежащим ячейкам строки может быть быстрее доступа разных строк) и т.д.
@t0digital
14 күн бұрын
количество итераций != количество операций суммирования overall_sum
@t0digital
14 күн бұрын
@@artemxilosof8946 итерация цикла это выполнение выражений тела цикла. Итерация внешнего цикла - это выполнение операции инициализации внутреннего цикла, итерация внутреннего цикла это выполнение вычисления overall_sum. Я даже не знаю, где можно найти определение итерации цикла, на которое можно сослаться, настолько это в моей картине мира очевидное понятие.
@RAlex061
14 күн бұрын
@@t0digital складывать количество итераций внешнего и внутреннего цикла - все равно что складывать яблоки с грушами. Вы пытаетесь обосновать то, что скорость самого итерирования в Пайтоне достаточно невысока и занимает существенную часть времени для каждого исполнения тела внутреннего цикла. Это давно известно. Я для проверки написал код на компилируемом языке (в данном случае на PascalАВС.NЕТ), максимально приблизив его к коду на Python и выполнил его десять миллионов раз, потому что сто тысяч для компилятора дает время в десятки миллисекунд и различить разницу там невозможно. Получены ожидаемые результаты: 00:00:08.5172238 и 00:00:08.5776699. Легко видеть, что эти значения времени отличаются в 1.007 раза, т.е. практически совпадают. Вывод очевиден: заморачиваться с ускорением вложенных циклов для прохода по многомерным структурам может иметь смысл только в интерпретаторах.
@t0digital
14 күн бұрын
> складывать количество итераций внешнего и внутреннего цикла - все равно что складывать яблоки с грушами. Итерации есть итерации. def my_range(limit): counter = 0 while counter yield 1 counter += 1 my_range.called += counter my_range.called = 0 for _ in my_range(100): for _ in my_range(5): pass print(my_range.called) # 600 my_range.called = 0 for _ in my_range(5): for _ in my_range(100): pass print(my_range.called) # 505
В более сложных структурах может появится еще одна ось z - трехмерная матрица. Там уже будет три цикла - по матрицам, по строкам и в конце по колонкам строки матрицы.
Тоопчик! Очень интересно!
Кстати, tuple(… for … in …) будет работать на ⅓ медленнее, чем tuple([… for … in …]), но во время выполнения работы должно занимать несколько больше памяти (it depends насколько)
Интересно что автор увидел лишние итерации, но не понял что именно влияет на производительность и сделал неверные выводы
@t0digital
14 күн бұрын
Давай конкретику!
@youcancallmepups
14 күн бұрын
@@t0digital в одном из комментариев говорили, что при разных обходах таблицы кэш работает с разной скоростью
@user-bc5rm4rk5e
14 күн бұрын
согласен
@user-bc5rm4rk5e
14 күн бұрын
здесь таблица вообще не причём. итераций одинаковое количество дело в обращении к элементы по индексу
@user-bc5rm4rk5e
14 күн бұрын
в первом цикле лишние обращения, поэтому и времени уходит больше
было интересно, даже не задумывался об этом раньше
Пишу на второй минуте просмотра. Что если поменять местами? То есть поменять порядок выполнения. Сначала small, потом big. Что если данные из этих таблиц после первого прогона задерживаются в кэше процессора, поэтому и скорость разная?
@t0digital
15 күн бұрын
проверял, не влияет на результат
@t0digital
14 күн бұрын
@@12345_qwerty вот тебе наглядно о 600 и 505. Если не хочется называть это итерациями - назови как хочется, важна суть:) def my_range(limit): counter = 0 while counter yield 1 counter += 1 my_range.called += counter my_range.called = 0 for _ in my_range(100): for _ in my_range(5): pass print(my_range.called) # 600 my_range.called = 0 for _ in my_range(5): for _ in my_range(100): pass print(my_range.called) # 505
Спасибо большое. Очень понравилась. Глаза открылыись на то,что такое есть. Прям прикольно
подскажите пожалуйста я только начал изучать пайтон в самом начале мы же просто делаем кортеж кортежей каким образом он выводиться табличкой а не одной строкой
@notyuki256
14 күн бұрын
Автор использовал pretty print: from pprint import pprint pprint(table)
Познавательно, спасибо
Забавно, что эта оптимизация имеет место быть в любом ЯП, никогда об этом прежде не задумывался :) Рассмотрим простейший код на ассемблере (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%, и, по сути, заключается в одной лишь дополнительной комманде ассембли... (ну и само собой в кэшировании данных процессором, но это уже другая история)
@t0digital
14 күн бұрын
Почему количество итераций это некорректная формулировка? Вот ты привел ASM-код, каждый цикл это инициализация счетчика (mov ecx, 0 для внешнего и mov ebx, 0 для внутреннего - инициализация есть), каждая итерация это инкремент счётчика (inc ebx и inc ecx - есть инкремент), это проверка счетчика на условие выхода из цикла (cmp ecx, 100 и cmp ebx, 5 - есть проверка). Чем больше циклов и чем больше итераций, тем больше операций надо сделать. В чём конкретно ты видишь некорректность формулировки?
@lemopsone
14 күн бұрын
Да уж, мозги уже у самого потихоньку начинают отказывать, забираю свои слова назад) конечно это итерация, за годы написания кода на более высокоуровневых языках в голове укоренилось (ошибочное) представление, что итерация == выполнение тела вложенного цикла, само собой это не так. Приношу свои извинения :)
Супер, информативно, спасибо )
Можно ли внутри функции «пересобрать» структуру, чтобы можно было применить map и ускорит ли это исполнение?
@AlexanderBorshak
14 күн бұрын
Скорее всего будут большие потери на реаллокации памяти при "пересборе" структуры. Раз элементы уже лежат в кортеже (или в листе), то доступ по индексу (т.е. по указателю) будет самым быстрым. Хотя, как по мне, не стоит так упирать на микрооптимизации, лучше применять более инженерный подход. Для примера, вынести обработку одной строки в отдельную функцию - а потом вызывать ее для всех строк. Так намного меньше вероятность ошибиться.
@gsm7490
14 күн бұрын
@@AlexanderBorshak я наверное примерно это и пытался сказать, (но не получилось ибо свой кофе еще не выпил), что пример какой то от жизни оторванный: методы кортежей питона позволяют без таких циклов "в лоб" обойтись (sum(sum(tuple) for tuple in tuple_of_tuples) или что-то подобное). можно и numpy подключить если требуется. питон высокоуровневый язык. имеет смысл по максимуму его фичи использовать, а не пытаться писать так же как пишут на си и тп. тот же join в sql из примера написан явно не на питоне) ps. 99%того что я читал по оптимизации кода на питоне сводится к : применяйте кортежи вместо списков, генераторы, функции стандартной библиотеки вместо пользовательских и чаще юзайте numpy
@t0digital
14 күн бұрын
а если задача не про sum? А если там вообще нет обхода структуры? Ну не об этом же видос-то)
@gsm7490
14 күн бұрын
@@t0digital да, безусловно, это полезный нюанс, но все же вынужден настаивать: если говорим именно при питон, в первую очередь поискал бы возможность решить без вложенного цикла )
@AlexanderBorshak
14 күн бұрын
@@t0digital А вот если задача не про sum и не про обход конкретной структуры, то нам как раз и стоит хорошо подумать, надо ли нам 1) писать все итеративно, стараясь выжать лишние 100 мс но получив в итоге неидиоматичный код, что плохо читается или поддерживается, или 2) пожертвовать 100 мс (на итерацию), но использовать идиоматичные средства используемого языка (типа более подходящей структуры данных или встроенной функции а-ля SUM), или даже абстрагировав операцию в функцию или метод класса. Вопрос в том, что важнее. Если легкость поддерживания и отсутствие ошибок - то 2-й вариант явно предпочтительнее. Если же нам критичны 100 мс (на каждой итерации), то может стоит взять что-то типа numpy, или даже переписать весь модуль на С или Zig и подключить через биндинг, или даже переписать всю программу на Go, C, Rust, Zig. А так, переворачивать циклы в приложении, что запускается пару раз на день, только потому что там выигрыш в 100 мс - выглядит как экономия на спичках. Так и до ручного разворачивания циклов недалеко...
Если вспомнить что питон позволяет "нормально" итерировать объекты - без индексов, а просто "for item in iterable", и писать функцию в таком стиле - "for row in table: for column in row: overall_time += column", то можно сэкономить еще немного времени (у меня получается что "нормальный" цикл быстрее суммы на 15-20%)
Ну это же логично, если первый цикл содержит малый размер а второй больше, то кеш будет быстрей работать, а если сделать наоборот то кеш будет чаще обновляться тем самым появиться такая разница во времени исполнения. Это как для олдов которые с СД диска устанавливали приложения и игры, большой файл быстрей считывался и записывался, нежели чем более мелкие
Будет чудно, если собеседующий задаст вопрос по nested loops после этого видео, а кандидат ответит потому, что посмотрел это видео.
И по поводу функции sum, она реализована на CPython по этому и быстрей работает чем обычные итерированные сложения
Как работает range() в питоне? Чую что в медленном случае просто больше выделений памяти из за этого
Большое спасибо, буду знать. Как раз пишу приложение для работы с sql
Спасибо за лабу! А что интерпретатор при вызове sum() дёргает?
@t0digital
14 күн бұрын
sum определен в С-шном коде
Урааа! Котаны долго без видео быть не могут, а тут видос подъехал!
Не очень понял, почему итерации различаются. На питоне много лет не писал, потому не очень понимаю какая итоговая размерность таблички. Допустим 5 x 100, тогда какая разница в каком порядке проходить, если в итоге нужно пройтись по 500 ячейкам? Выглядит так, что в видео была лишняя итерация и весь выхлоп в её уменьшении, но тогда не понятно отличаются ли значения после суммирования двумя методами или в чём прикол?
@t0digital
15 күн бұрын
Общее количество итераций двух циклов отличается. Внутренний цикл всегда отработает суммарно 500 раз, а внешний 5 раз или 100 раз. Каждая итерация цикла это инкремент счетчика и проверка счётчика - доп действия. Меньше доп действий - быстрее работает
@selden1890
15 күн бұрын
@@t0digital а зачем вообще считать количество итераций внешнего цикла? действие же выполняется внутри тела внутреннего цикла
@AlexanderBorshak
15 күн бұрын
+! Кол-во итераций надо считать только во внутреннем цикле. Во всех случаях оно должно быть ровно 5 * 100 = 500.
@user-zw6vz4ec7n
15 күн бұрын
Итераций там всегда одинаково, дело не в этом. Между двумя for вставлять увеличение счётчика iterations неправильно. Автор так себя обманул, ну и свою аудиторию заодно. Там должен быть другой счётчик. Дело в оверхеде при содании циклов, в питоне это не zero-cost операция. Внешний цикл всегда один, а внутри либо 5 раз создастся цикл, либо 100 раз. Создание 5 циклов занимает меньше времени, чем создание 100. Если из результатов 505 и 600 вычесть 500, то как раз и получится 5 и 100. 5 и 100 - это один счётчик, а 500 другой. В Rust итераторы, кажется, zero-cost абстракция, там должны быть почти идентичные результаты. Там уже может влиять попадание в кеш процессора, как в других комментариях отмечали.
@t0digital
15 күн бұрын
1. Итерация - повторение цикла. Если есть 2 цикла, то у каждого из них свои итерации. Я считаю итерации обоих циклов, потому что на каждой итерации цикла выполняются действия как минимум со счетчиком цикла - например, его увеличение и проверка условия на выход из цикла. И в одном случае таких операций больше (при большем внешнем цикле), в другом случае меньше (при меньшем внешнем цикле). 2. Дело не только в оверхеде на создание внутреннего цикла, хотя и в этом тоже. Аналогичное поведение наблюдается не только в Python, но и в компилируемых языках. У Макконнелла были исследования для С++ и Java, результаты аналогичны.
Алексей, можете, пожалуйста, подробнее объяснить, что вы имеете в виду на 3:45? Сейчас для меня это выглядит так, что вы отрицаете коммутативность умножения, зачем-то прибавляя единицу каждую итерацию внешнего цикла.
@t0digital
14 күн бұрын
Каждый цикл не бесплатен, сам for не бесплатен. На каждой итерации каждого цикла происходит работа со счётчиком, его инкремент и проверка, и я считаю это количество операций. Отработала нулевая итерация внешнего цикла - счетчик внешнего цикла установился в 0, выполнилась проверка, что 0 < ограничения количества итераций в цикле. Мы посчитали выполнение этой логики. Затем отрабатывает нулевая итерация внутреннего цикла, там выполняется та же логика для уже внутреннего цикла и его счетчика - мы посчитали выполнение этой логики. И так далее до полного выполнения обоих циклов.
периодически смотрю твои видео 3-5 летней давности (отличный контент) и замечаю, что ты постарел( и я тоже, просто на себя чаще смотрю), но ты еще и красавчик, отличный контент делаешь, спасибо
Все зависит от значений ROWS и COLUMNS, если сначала пробегать по значению, которое меньше - оно и будет быстрее, если они одинаковые - разницы не будет
В университете на архитектуре вс узнал об этом и еще множество других интересностей про кластерные вычисления. Весь курс был построен на подсчете времени вычисления при разных условиях.
Кажется в комментах непонимание того, что автор имел в виду под словом "итерация", что же всё-таки подсчитывает переменная iterations. Здесь мы подсчитываем сколько раз за эти два вложеных цикла вычислялись loop conditions. Не важно, что там в теле цикла. Эти самые loop conditions не бесплатны. Ну и инкрементт переменной цикла тоже чего-то стоит. IMO
@t0digital
14 күн бұрын
Ну как бы это и есть итерация, она включает в себя помимо прочего на нулевой итерации инициализацию и на каждый последующей итерации действия со счетчиком. Уважаемые комментаторы не в курсе просто, что это не бесплатно и каждая операция кушает ресурсы.
@AlexanderBorshak
14 күн бұрын
Разница в скорости скорее вызвана количеством инициализаций цикла. Внешний в любом случае инициализируется 1 раз, внутренний - или 5, или 100. Именно эти цифры и получил автор (505 - 500 = 5, 600 - 500 = 100), но он сложил кол-во инициализаций с тем, что обычно понимают под "итерацией", чем всех и запутал.
@aalexren
13 күн бұрын
@@AlexanderBorshakточно, вот это прямо хороший комментарий
Для данного примера более подходящий такой вариант с sum print(sum(sum(matrix, []))). Вариант с функцией sum может быть быстрее, еще и из за List comprehensions. К тому же для чистоты эксперимента не был рассмотрен обратный вариант для sum.
@fahrenheit1863
15 күн бұрын
И давайте вообще напишем все на Си и обойдемся для этого примера одним циклом в 500 итераций.
Во многих базах данных есть встроенный оптимизатор запросов, поэтому нет разницы как ты пишешь запрос, джоинишь ли ты а к б или б к а, постгресс сам за тебя уже оптимизирует и проджоинит, так чтоб все было максимально быстро и эффективно. В этом можно убедиться с помощью explain analyze на запросе и разном порядке джоинов.
@t0digital
11 күн бұрын
Да, это так. Но приятно понимать, как все работает под капотом
Кэши, счетчики, что считать итерациями, это-то всё ладно. В итоге-то, что с чем джойнить надо? К маленькой таблице данные из большой, или к большой таблице данные из маленькой? Или что имеется в виду, как это с джойнами-то применять?
@t0digital
14 күн бұрын
Постгрес умный и в общем случае он сам поймёт, какой набор данных больше (если собрана правильная статистика), сам найдёт правильный способ соединения (вложенные циклы, hash join, merge join) и сам во вложенный узел поставит операцию с меньшим объёмом данных. Но вот в рамках этих своих поисков оптимального способа выполнения запроса он и будет в том числе полагаться на внешний цикл с меньшим количеством итераций, потому что количество обращений к внутреннему набору данных равно количеству итераций внешнего цикла
@t0digital
14 күн бұрын
хотя мне сейчас всё же удалось, отключив пачкой кучу опций оптимизатора, заставить его выполнить вложенный цикл с бОльшим размером внешнего цикла. Но для этого надо действительно постараться:) set enable_hashjoin=off; set enable_mergejoin=off; set enable_indexscan=off; set enable_bitmapscan=off; set enable_material=off; Думаю, это актуально только для теоретического интереса в контексте постгреса. В реальном сценарии без отключения всего этого едва ли получится реализовать такой сценарий.
@trankov
13 күн бұрын
@@t0digital Спасибо) Интересно, только ли Постгрес такой умный.
стоп на 5:52 : предполагаю, что sum должен быть может и не намного, но быстрее, поскольку очень может быть, что это просто обёртка над C, а на уровне С-кода можно использовать всякие интрисики и SIMD-инструкции.... Хотя... Может для меленькой коллекции переход на уровень C-кода сам по себе может быть достаточно дорогой, что сожрёт всю оптимизацию, поётому может быть sum использует опимизации уровня питон, что были показаны ранее. Посмотрим дальше.... UPD: а вот тут инженерная чуйка не подвела :) Осталось прокачать внимательность и навык, чтобы даже в развлекательном видео включать больше мозга и будет вообще зашибись :)
Только недавно делали лабораторку в универе Проверяли в каком порядке цикл i-j-k быстрее работает
С открытой челюстью всё видео сидел
@hollygreen8663
14 күн бұрын
hahahahah
@leonidgrishenkov4183
14 күн бұрын
закрой, лишний цикл залетит
А насколько это применимо в реальной разработке? Например, у нас есть таблица сущностей, а если количество атрибутов сущности произвольное?
Основная разница в количестве запуска функции 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.
@t0digital
10 күн бұрын
Посмотри следующее видео, если интересно:) там копнулось глубже и больше тестов
Тестировал не на локальной машине, в онлайн редакторе, но если немного увеличить количество данных, например 50х100. То независимо от того, чего будет больше(строк или столбцов) цикл сначала по строкам, а потом по столбцам работает быстрее. Т.е. в обоих случаях ROWS = 100 COLUMNS = 50 и ROWS = 50 COLUMNS = 100 цикл сначала по строкам предпочтительней. Так что совет "меньшее количество шагов во внешнем цикле - лучше" - не универсальный. Так что дефолту лучше использовать стандартный обход - сначала по строкам, потом по столбцам, если речь идет о двумерном массиве. Sum скорее всего может использовать SIMD.
@MrLagger1996
12 күн бұрын
может использовать конечно, но не с кортежами и списками. мейби если использовать array и ctypes
Похоже это базовая особенность вложенных циклов как алгоритма... Вот уж спасибо вам что обратили внимание на такой эффект!
вспоминаем недавний видос про клин код и оптимизацию. "да кому эта оптимизация нужна. это все io задержки, тут ускоришь - там замедлишь и т.д". ну вот кому эта оптимизация на 30% в вебе нужна?)
@t0digital
15 күн бұрын
Говорил в прошлом видосе и говорю в этом о том, что это не оптимизация как отдельное действие, а просто способ сразу писать более эффективный код - без загрязнения кода.
@_test_test
15 күн бұрын
@@t0digital чисто технически, загрязнения тут нет. в примерах было 2 абсолютно одинаковых цикла, но от перемены мест слагаемых скорость поменялась. может ли программист не думать о том, в каком порядке составлять вложенные циклы? может. зачем ему тогда об этом думать, если производительность - это не главное?)
@t0digital
14 күн бұрын
Сложность работы разработчика в том числе в том, что надо держать в голове факторов больше, чем один главный приоритет
@SplashDmg2011
14 күн бұрын
Суть в том, что оптимизация без ухудшения читаемости и поддерживаемости кода (т.е. считай бесплатная) - это ок. А вот когда оптимизация такая, что код превращается в макароны, которые работают на 10% быстрее - то любой энтерпрайз-проект через пару лет помрёт от таких оптимизаций
прикольно) для меня неочевидная штука была)
Забавно, но если поменять местами 5 и 100 в количестве элементов, то пример с суммой начинает жестко проигрывать big_outer_loop_time=2.58, small_outer_loop_time=3.56, with_sum_time=5.21 Тут по сути сейчас названия big и small нужно бы поменять местами, но речь не о них
@t0digital
14 күн бұрын
Ну так поменяв местами, вы не меняете логику работы кода. Код с большим внешним циклом работает по-прежнему медленнее.
Я однажды на такое наткнулся на практике, но не понял почему так произошло. Там производительность увеличивалась с нескольких часов до нескольких минут. Я подумал что это была магия хаскеля и фильтров, но не поверил. С тех пор в жирных вычислениях всегда проверяю вложенность циклов.
Что за конструкция генерации таблицы? Синтаксис странно выглядит
Интересно, интересно :)))))))) Спасибо за видосик!
не привычно видеть у тебя бесплатные видосы :)
@t0digital
14 күн бұрын
Бубубу!
В реальной жизни, даже если вдруг приспичило проитерироваться по 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 подтягиваний Но это же бред так считать подтягивания) Вот бы я в школе на физре их так считал)
@t0digital
14 күн бұрын
На каждой итерации есть действия со счетчиком и любые действия небесплатны. Здравствуйте:)
Такой подсчет итераций противоречит алгоритмической сложности, да и лишние 100 элементов из воздуха не возьмутся от перестановки циклов. То что здесь считается, это количество сравнений. Кеш тут тоже не причем т.к. из структур которые должны туда попадать тут (конкретно в коде из закрепленного комментария) 3 счетчика и 2 константы на функцию. Разница по большей части из-за операций сравнения. Но, что я не понял почему плоский цикл ниже выполняется дольше малого. ROWS = 5 COLUMNS = 100 ALL = ROWS * COLUMNS def flat_loop(): overall_sum = 0 for _ in range(ALL): overall_sum +=1
@t0digital
14 күн бұрын
Я и не говорю, что возьмутся лишние 100 «элементов» - я говорю об итерациях циклов, и на каждой итерации выполняются свои действия со счётчиком цикла, которые я и считаю. В одном случае этих операций 100 + 5*100 = 600, а в другом 5 + 100*x = 505. Какие именно это операции можно посмотреть в байт-коде с помощью dis.
@sadpotato7563
14 күн бұрын
@@t0digital Ни в коем случае не противоречу подсчётам. Лишь пытался внести ясность в них. Проще, и на мой взгляд правильнее, относится к этому как счётчику сравнений (достигли конца или нет) в цикле. Понятие итерации как повтора действий слишком размыто. Тем не менее, отличный байт на комментарии 🤣
Интересно ещё было бы посмотреть на вариант sum(cell for row in table for cell in row) Имею подозрение, что это будет самое быстрое нативное решение. UPD: увидел, что тему уже поднимали
Годно
Что то мне подсказывает , что количество строк или колонок будет коррелировать с разницей производительности.
Ничего не понял как это получается циклов меньше (надо проверять самому, а сейчас лень), но было ОЧЕНЬ интересно!
@harry-smith404
14 күн бұрын
тут два понятия, Алексей их просто немного смешал типо в целом количеств операций конкретно суммирования **overal_sum += table[row][column]** остается одно и тоже - ROW*COLUMNS чисто механически проходов по блокам кода меньше, тк ROW < COLUMN и соотвтественно вызовов тела внешнего цикла тоже меньше
В других языках такое-же поведение? в PHP, C++, Go, TS ?
@t0digital
14 күн бұрын
оптимизаторы могут схлопывать разные сценарии в целях собственно оптимизации. В целом лучше всегда тестить :)
Когда-то я по приколу писал алгоритм, заменяющий в тексте все согласные на противоположные им (для согласной являющейся пятой с начала алфавита берётся согласная пятая с конца алфавита и так далее). Так вот, взял я словарь от какого-то русского синтезатора речи, словарь на 70 мегабайт в koi-8r кодировке. Изначально мой алгоритм работал с этим словарём примерно за 59 секунд. После перевкладывания циклов так, чтобы внешний цикл был меньше, я получил ускорение с 59 секунд до 14 секунд. Там конечно вмешалось и существенное уменьшение количества вызовов replace, но это было прям вау как круто. Только вот тот же алгоритм, будучи реализованным на Go, работает примерно за 6 секунд, а реализация на Lua отрабатывает примерно за 10 11 секунд, что увы не в пользу Питона.
@TheBaronsimon
15 күн бұрын
мне тоже луа нравится. если правильно писать (без конкатенаций, локальные переменные, без функциональщины и другие трюки), получается очень быстро
@mslq
15 күн бұрын
на версии 3.12 не пробовали? а то нам втирают что чуть ли не в 50 раз кое что ускорилось.
Действительно, если внешний цикл выполняется i-раз, а внутренний j-раз, то всего будет: i * j + i вычислений в области видимости строк "for". А так сходу и не очевидно было.
1:10 Ответ на вопрос до просмотра видео - да, есть разница, выгоднее внешний цикл делать с меньшей стороной, так уменьшается количество _инициализаций_ внутреннего цикла. 2:52 Замечание по ходу - было бы правильнее называть не итерациями, а проверкой условия в цикле, поскольку итерации внутреннего проходят во время итерации внешнего, а не где-то рядом дополнительно. В итоге сумма всегда увеличивалась 500 раз, а условия циклов проверялись соответственно 100+5*100=600 и 5+100*5=505 раз. Параллельное представлено как последовательное. И отмечу, что это не 30% разница, то есть не единственный фактор. Но общая мысль интересная, спасибо.
@t0digital
15 күн бұрын
на каждой итерации каждого цикла происходит как минимум операция со счетчиками - надо считать итерации и внутреннего, и внешнего циклов
@dolotube
15 күн бұрын
@@t0digital Если мы считает операции, то мое замечание актуально - нужно называть подсчетом операций, а не итераций. Итерации внутреннего происходят во время итерации внешнего - это не последовательные сущности, а вложенные. Да, идет изменение счетчиков и проверка условий - это требует ресурсов, поэтому должно учитываться. И обратите внимание - разница в количестве итераций у вас составила 16%, а разница в быстродействии добивала до 30%, поэтому для объяснения нужно таки добавить еще что-то помимо "итераций". Я предположил, что играет роль инициализация - в первом случае циклы инициализируются 1+100 раз, а во втором случае 1+5 раз.
@t0digital
15 күн бұрын
> нужно называть подсчетом операций, а не итераций Почему? Поясните, я допускаю, что я чего-то не понимаю. Почему я не могу назвать итерацию цикла итерацией и должен называть операцией:)?
@dolotube
14 күн бұрын
@@t0digital Вы увеличили счетчик итераций во внешнем цикле - ок, и вот итерация еще продолжается, не закончилась, но вы уже увеличиваете счетчик во внутреннем цикле - и это не ок. Вы считаете не итерации, а входы в итерации. Которые соответствуют сущности "условие проверки выполнилось". Это даже не "сколько раз мы увеличивали счетчик" или "сколько раз мы проверяли условие входа" - последние операции не зарегистрировались счетчиком, поскольку не было входа в тело цикла. Итерации, которые Вы считаете, - это ничто, абстракция, которая ничего не стоит процессору. Считать нужно конкретные операции, которые съедают время, а не "повторы". В данном случае - операции по инициализации цикла, операции по изменению счетчиков и проверки на условие входа. И что важнее пустого спора о терминологии - как Вы объясняете разницу между тем, что количество "итераций" меняется на 16%, а скорость работы меняется на 30%?
@t0digital
14 күн бұрын
Я не знаком с понятием «входа в итерацию», знаком только с понятием «итерация», и каждый работающий цикл создаёт итерации. Есть итерация внешнего цикла и есть итерация внутреннего цикла. Стив Макконнелл, «Совершенный код», стр. 609, аналогичный код, цитирую: «Ключ к улучшению цикла в том, что внешний цикл состоит из гораздо большего числа итераций, чем внутренний». У Стива то же понимание итераций, что и у меня. Скорость меняется, потому что меняется количество итераций и соответственно операций в них, в операции входит всё - и операции со счёткиками циклов, и всё остальное, в частности, в одном случае внутренний цикл инициализируется 100 раз, а во втором 5 раз, все операции занимают время.
про функцию with_sum, на сколько знаю комприхеншены быстрее обычных циклов, тоже свою роль сыграло
sum на C же написана?
это все логично, большой код на низком уровне обработается быстрее, чем много раз маленький
Фантастика!
Что за sum(column for column for row)? Оно же эквивалентно sum(row)
@t0digital
13 күн бұрын
>>> sum(row for row in ((10, 20), (30, 40))) TypeError: unsupported operand type(s) for +: 'int' and 'tuple' >>> sum(sum(row) for row in ((10, 20), (30, 40))) 100
@user-mobilnik
13 күн бұрын
@@t0digital да, ок, я про последнюю строчку, где sum(column for column in row) можно заменить на sum(row) (5:37 line 25)
По видимому интерпретация цикла имеет свои издержки, по крайней мере для интерпретатора. Поэтому важно, сколько раз будет интерпретироваться вложенный цикл. От этого думаю и разница. В компилируемых языках возможно разницы не будет.
@t0digital
14 күн бұрын
разница будет и в компилируемых языках
@reydan6707
14 күн бұрын
на плюсах проверил, разницы нет, если, конечно, во внешнем цикле нет операций
@t0digital
14 күн бұрын
значит интерпретатор сейчас умнее стал и такие простые операции умеет оптимизировать сам, но сумеет ли он оптимизировать более сложные сценарии, когда логика есть в обоих циклах - это вопрос. У Макконнела были тесты на момент на издания книги и на тот момент для плюсов и Java разница была - для плюсов 33%, для Java 34%.
@t0digital
14 күн бұрын
На сишке в соседнем комменте пишут, что разница есть. Что при большом разбросе размера циклов внешний меньший цикл работает лучше. Без структуры код
@user-pv8it1ml9y
14 күн бұрын
@@t0digital возможно. Если рассмотреть машинные коды после компиляции, то очевидно, для вложенного цикла надо как минимум счетчик заново инициировать и вероятно ещё какие либо действия выполнять, к памяти обращаться и пр. Но это все очень быстро должно происходить. Не думаю, что сравнение при почти пустом теле вложенного цикла имеет практический смысл. Т.е. по сути сравниваются издержки на инициализацию цикла с одной простой командой сложения.
А ксли сделать ROWS=100, а COLUMNS=5?
@alexg3522
12 күн бұрын
Тогда big... будет быстрее ;)
То, что вы считаете итерации внешнего и внутреннего циклов - это как складывать кислое с красивым. Их, конечно, можно сложить, т.к. это просто числа, но никакого смысла эта переменная не несет. Учитывается всегда произведение кол-ва элементов цикла, что и является сложностью вложенных циклов. В вашем случае различие во времени скорее всего объясняется, как тут уже говорили, накладными расходами обращения к столбцам одного индекса внутри строк и различиями в использовании кэша. Если мы будем варьировать размер матрицы, то определенных значениях производительность будет меняться. В контексте PostgreSQL то, о чем вы говорите, обусловлено кол-ом обращений к памяти за данными и операциями ввода-вывода. На больших объемах это играет существенную роль.
@t0digital
14 күн бұрын
на каждой итерации цикла выполняются действия со счетчиком цикла и я считаю количество этих действий. ПОТОМУ ЧТО ОНИ НЕБЕСПЛАТНЫ!
@user-dd4fh6pd2i
14 күн бұрын
@@t0digital количество операций со счетчиками циклов будет одинаковой. Если есть два массива по 10 и 100 значений. В первом случае будет 10 проверок и 10 увеличений счетчика, и внутри по 100 проверок и увеличений. Во втором 100 проверок и 100 увеличений, и внутри по 10 проверок и увеличений. В итоге кол-во проверок и увеличений будет одинаковым. Скорее влияние будут оказывать накладные расходы на создание внутренних циклов, но не общее кол-во итераций и операций со счетчиками, т.к. они равны.
Может всё потому что в памяти все двумерные массивы содержаться в виде массива из массивов элементов. То есть строки, содержат колонки элементов.
все равно не понятно, как количество итераций разное. в первом случае ROWS*COLUMNS, во втором COLUMNS*ROWS - должно же совпадать. разница в производительности доказана, вопросов нет. но объяснение не объясняет :)
Я в шоке от того, насколько это лежит на поверхности, но несмотря на это даже никогда не задумывался об этом. Круто!
@ivandrivan
14 күн бұрын
блин реально я тоже такой сначала аааа а потом такой уууу я так и не понял
Я так понимаю, это справедливо для всех подобных случаев и всех ЯП?
@t0digital
15 күн бұрын
Да. Возможно где-то компилятор научился сам определять такое в простых случаях, но едва ли в сложных сможет что-то сделать, когда есть логика в обоих циклах, разные continue, break и тп
а в школе между прочим нас учили что от перестановки двух чисел множимого и множителя ничего не меняется, а тут на тебе, оказывается есть разница, ну кроме ответа конечно.
@user-jp2zc3lo9o
15 күн бұрын
замечу, что учили то как раз что "сумма/произведение не меняется", про побочные последствия и оптимизацию циклов подло умалчивают в начальной школе((
@t0digital
15 күн бұрын
Ниггадяи! Они это скрывают от нас! Возможно, это даже мировой заговор!
@astralromance9052
14 күн бұрын
Там в школе ещё всякие умные знания про ассоциативность, коммутативность и вот это все рассказывали. А для тех, кто не вывез в школе, повторяли в университете. А это, оказывается, открытие теперь.
Блин, думал я о том, что это влияет, но не знал, что настолько сильно. Постараться бы теперь это учесть при кодинге.
@xeqxeq4287
15 күн бұрын
Смысл заморачиватся на этом? 😀 Эффективность кода на питоне - смешно...
@Vorono4ka
15 күн бұрын
@@xeqxeq4287 с тем же успехом можно сказать "а зачем на си заморачиваться? он итак в сотни раз быстрее питона, давайте просто писать на нём и пофиг на оптимизации, зачем заморачиваться". Если ты пренебрегаешь оптимизациями, то твой код везде будет медленнее, не важно на каком языке у тебя написан код. Поэтому будь паинькой и хорошим программистом, оптимизируй что можешь, особенно когда это так легко.
@t0digital
14 күн бұрын
@@xeqxeq4287 стремиться быть хорошим разработчиком или не стремиться быть хорошим разработчиком - выбор каждого, да
@Vorono4ka
13 күн бұрын
@@t0digital опять ютуб мои ответы не публикует зараза, я ещё предложил ему перейти на си, чтобы не писать на этом "жалком медленном питоне" 😁
@t0digital
13 күн бұрын
@@user-uc6wo1lc7t хорошо, буду включать теперь голову, от души, брат!
Алексей в этом видео похож на Колина Фаррелла в Джентельменах)
Так это зависит от задачи, если у тебя будет 100 рядков и 5 колонок то первый отработает быстрее, это же логика в количестве переключений как раз таки, в одном случае мы переключаемся как ты сказал всего 5 раз а в другом 100, потому что разрядность матрицы - 100
@t0digital
15 күн бұрын
так речь не о таблице и строках/колонках, а о количстве итераций во внешнем и внутреннем циклах
@nickolayfetlistov4416
15 күн бұрын
@@t0digital да, так это зависит от количества колонок и рядков же
@t0digital
15 күн бұрын
вот пример без обхода структуры, но с подтверждением того, что меньшей внешний цикл работает эффективнее: import timeit ROWS = 5 COLUMNS = 100 TIMEIT_ITERATIONS = 100_000 def big_outer_loop(): overall_sum = 0 for column in range(COLUMNS): for row in range(ROWS): overall_sum += 1 def small_outer_loop(): overall_sum = 0 for row in range(ROWS): for column in range(COLUMNS): overall_sum += 1 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=}") delta = round(100*(big_outer_loop_time - small_outer_loop_time) / big_outer_loop_time) # big_outer_loop_time=2.18, small_outer_loop_time=1.37 print(f"{delta}%") # 37%
@nickolayfetlistov4416
15 күн бұрын
@@t0digital тяжело в понятиях внешний и внутренний, ты проходишься по структуре, чем больше переключений тем хуже, когда ты переключаешься всего 5 раз это немного лучше чем 100, поменяй значения местами, и большой цикл будет отрабатывать лучше big_outer_loop_time=1.24, small_outer_loop_time=0.8 35% Твой вариант big_outer_loop_time=0.79, small_outer_loop_time=1.25 Я свопнул значения
@t0digital
15 күн бұрын
в моём примере выше я не прохожу по структуре, её вообще нет
Из серии 'лучше быть богатым и здоровым, чем бедным и больным'. И так все очевидно. Чем меньше обращений к памяти, тем быстрее. Читать большой чвнк и бежать по нему проще, чем по куче мелких чанков. Да и суммирующая функция (скорее всего написана на С) бежит по внутренним структурам объекта, игнорируя интерпретационные накладные расходы.
Офигеть. Сначала мозг сломался а потом понял, типа rows умножаем на columns только внутри а во внешнем цикле кол-во интераций равно внешнему, а я всегда думал что кол-во итераций просто можно получить умножением)
@t0digital
15 күн бұрын
вот и вот:)
@t0digital
14 күн бұрын
@@sergey53689 🤗
В small_outer_loop числа с большей вероятностью будут находиться в одних линиях кэша. Поэтому и быстрее
@t0digital
15 күн бұрын
Аналогичные результаты будут и без обхода и вообще наличия структуры table. Дело в количестве итераций внешнего и внутреннего цикла.
@denyskarpov5905
14 күн бұрын
@@t0digital А чем это поясняется? Разве элементы в одной строке не ближе друг другу в памяти?
@t0digital
14 күн бұрын
@@denyskarpov5905 это поясняется разным общим количеством операций, которые надо выполнить, для большего внешнего цикла и для меньшего внешнего цикла. Если внешний цикл больше - суммарное количество операций больше, из-за этого производительность ниже
Вот блин... Очевидно же, но не задумываешься... Хотя я внешним циклом всегда по строками иду по привычке, но всё равно прикольно
вместо sum(sum(item for item in row) for row in table) стоило использовать sum(item for row in table for item in row)
@t0digital
14 күн бұрын
да, 52% прирост к big_outer_loop против 44% в случае двух sum
А еще в sql join большой таблицы к маленькой быстрее чем наоборот
Все такие удивленные)) Это база при решении алго задач, то чувству когда думал что это очевидная штука, а её ни кто не знает:DD
@denyskarpov5905
14 күн бұрын
У Вас есть ссылка на литературу где это описано?
У меня чере sum() чуть быстрей получилось, еще чуть быстрее через enumerate(), и 30% быстрее for r in table: for c in r: sum+=c
Скорее всего особенность языка - на c++ оба обхода идентичны по производительности
@t0digital
14 күн бұрын
оптимизации компилятора, которые умеют схлопывать такие простые варианты. Надо смотреть ASM-код на выходе. Для более сложных циклов оптимизации могут не сработать. В общем случае надо смотреть каждый конкретный случай на конкретном ЯП, да.
@thecooltema4895
14 күн бұрын
@@t0digital Да, я специально отключил оптимизации и отсмотрел сгенерированный объектник, чтобы убедиться в корректности сравнения.
@t0digital
14 күн бұрын
если убрать создание и обход таблицы и на каждой итерации просто инкрементить overall_sum - результаты идентичны? А ASM-код тоже идентичен? Давай посмотрим, интересно же ж:)
@thecooltema4895
14 күн бұрын
Тестил циклы с a) overall_sum++; и b) overall_sum += cos(overall_sum); Оптимизации выключил, векторизацию тоже (-O0 -mno-avx -fno-builtin) Внутри (a) и (b) Асм генерировался идентичный (с точностью до верхних границ циклов) Результаты не идентичны, но лидер меняется, т.е нет более эффективного метода.
@t0digital
14 күн бұрын
лидеры меняются при повторном прогоне теста или при изменении количества итераций внешнего и внутреннего циклов?
есть вариант быстрее всех этих (но хуже по памяти в некоторых случаях): sum(reduce(operator.add, table))
@t0digital
14 күн бұрын
у меня этот код на CPython 3.12 показал ухудшение на 34% по сравнению с big_outer_loop
@artyomby4125
14 күн бұрын
@@t0digital m1 3.12.0 with_sum_reduce 0.36 big_outer_loop 1.88 small_outer_loop 1.39
@t0digital
14 күн бұрын
закинь весь код сюда, пожалуйста
@t0digital
14 күн бұрын
а, ну ты уже изменил код в начальной комменте и тестишь не то, что предлагал сразу, айяйяй:)
@artyomby4125
14 күн бұрын
@@t0digital да, я просто скопипастил не ту строчку, сразу изменил. видимо ютуб коммент обновил с задержкой
sum(map(sum, table)) в 10 раз быстрее, чем оба варианта с циклами
@t0digital
7 күн бұрын
Это понятно, что суммирование можно сделать проще. Вопрос не о том, как эффективно суммировать последовательности, а о том, как их эффективно обходить для выполнения более сложной логики.
блин, всегда делаю вложенные джойны с более точным условием, чтобы выборка в джойне была меньше, на код ревью уже какой раз лид заворачивает, чтобы часть условия в джойне перенес в общее условие where ) ... показать ему видео, чтоли )))
@Vorono4ka
13 күн бұрын
А можете показать пример запроса? Уж очень интересно посмотреть!
@aleksandrdemidov6058
13 күн бұрын
@@Vorono4ka case 1 (I prefer) : select * from table1 t1 join table2 t2 ON ( t1.col1 = t2.col1 and t2.col2 = 'something2' ) where t1.col3 = 'somthing1' ..... case 2 (the lead pregers) select * from table1 t1 join table2 t2 ON ( t1.col1 = t2.col1 ) where t1.col3 = 'somthing1' and t2.col2 = 'somthing2'
@Vorono4ka
13 күн бұрын
@@aleksandrdemidov6058 Спасибо! А не будет ли в таком случае возможности занести и вторую проверку в условие джоина? Или так уже потеряется эффективность? Сложилось ощущение, что тяжело именно сложить две строки вместе, ведь в проверке итак уже участвуют обе таблицы и сыграть это на скорости не должно (или должно?)
@aleksandrdemidov6058
13 күн бұрын
@@Vorono4ka нет нельзя, первое условие относится только к первой таблице )
Суммарное количество итерация: s = i + ij, а не ij получается, здорово!
Количество итераций не правильно считаете
@t0digital
14 күн бұрын
Правильно
Что за взрыв мозга 🤯 в хорошем смысле))))
Не понимаю, зачем считать одну итерацию больше одного раза (когда счетчик инкрементируется во внутреннем и внешнем циклах), полная же глупость. И вся оптимизация, скорее всего (с питоном не знаком), заключается в количестве промахов в кеш процессора. Я для тестов использовал такой же код и таблицу размером 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
@user-vr6qh7ve5b
14 күн бұрын
python --version Python 3.12.1
@t0digital
14 күн бұрын
Посмотри прикрепленный коммент. Пример не про обход структуры, структуру можно выбросить с сохранением поведения, когда меньший внешний цикл работает эффективнее, чем больший.
если бы это было правдой, то компиляторы давно бы так все коды оптимизировали
@t0digital
14 күн бұрын
Они и оптимизируют то, что могут, это одна из причин, по которой (почти) не пишут на ASM сейчас. Байткод на выходе часто вообще не тот, что можно ожидать по высокоуровневому коду.
А имеет ли смысл итерироваться по колонкам ? Колонка сама по себе не несёт ценности. Например возьмём колонку и там будет Анна, Сергей, Денис. А нам интересно Анна, 22.02.1992, аналитик, 100000 рублей