Комментарии 43

Хм, а сетка квадратная? Или там какие-то особенности из-за кривизны земли? Описанное в статье подозрительно похоже на задачу увеличения (или уменьшения) изображения, которая, как мне кажется, может быть решена вообще за O(width * height)
P.S. Почему-то думал что они делают бинарный поиск для каждого элемента, а они один раз ищут индексы независимо по x и y, а потом просто читают из сетки, так что у них тоже O(width * height) и всё ок.

Там даже по тексту видно ):
— количество ячеек — 544 680
— вычисленные затраты — 553 076

Иногда прирост производительности можно получить вообще ничего не меняя в коде. Меня недавно удивил факт (и, думаю, удивит многих), что один и тот же код, который занимается применением регулярного выражения к разному тексту, на python на компьютере с windows 10 выполняется на 25% медленнее, чем в WSL2, которая запущена на этом же компьютере в этой же windows 10. Вероятно, тут какой-то косяк с реализацией модуля re под windows и поэтому такой неожиданный результат.

Вы не могли бы поделиться ссылкой про это (очень любопытно, но беглым поиском пока не нашёл)?

Если хотите попробовать то же самое, где я увидел этот эффект, то запустите launcher.py из https://github.com/ReinRaus/RegexCrossTool/
Суть всего этого кода проста: много раз в цикле применять регулярное выражение к разному тексту.
Заметная разница в производительности присутствует только для регулярных выражений, что скорее всего свидетельствует о проблеме в модуле re.
Забавен сам факт, что код, запущенный в WSL2 работает быстрее, чем в хостовой ОС.

Спасибо, интересно, любопытно — чисто интуитивно, другой джиттер работает, наверно.
Разные компиляторы? Blender, например, работает в Linux значительно быстрее, чем в Windows. Потому что там GCC, а тут MSVC.
Плюс ещё совершенно разные ядра: разные реализации планировщика процессов/потоков, разные реализации системы управления памятью кучи процесса.

Но лично мне странным кажется что прямо на много быстрее. MSVC очень не плохой компилятор так-то, как и реализация стандартных библиотек C/C++ не самая плохая у MS.
Плюс ещё совершенно разные ядра: разные реализации планировщика процессов/потоков, разные реализации системы управления памятью кучи процесса.
На двух/четырёхъядерных CPU влияние это оказывает вот совсем никакое, а замеры ещё тогда делались. Это же чисто вычислительные задачи.
Но лично мне странным кажется что прямо на много быстрее. MSVC очень не плохой компилятор так-то, как и реализация стандартных библиотек C/C++ не самая плохая у MS.
Мне тоже, но факт. Даже сборка mingw ранее на сайте лежала, можно было сравнить. Дело не в ОС, а в компиляторе.
Ну питон это очень высокоуровневый язык, и что там внутри не совсем понятно, и много чего может влиять на его скорость.
Меня больше удивляет, что код который написан на ассемблере на Win7 выполняется заметней медленней чем на WinXP, а на бесятке ещё медленней. Хотя код не использует библиотек и довольно простой, и весь влезает в кэш.
Меня больше удивляет, что код который написан на ассемблере на Win7 выполняется заметней медленней чем на WinXP, а на бесятке ещё медленней

а пример или ссылку можно поглядеть?

Для каждого local[x]:
bisect_search(local[x], Global[x])

Для каждого local[y]:
bisect_search(local[y], Global[y])

это только если поиск «стабилен» и не зависит от порядка поиска по отдельным осям, что далеко не факт в общем случае. А без всего этого мы перешли от брутфорса к двоичному поиску, глупо удивляться такому приросту на огромных взводных данных)
Сейчас конкретный пример не могу дать.
Но у меня тут, код на разных Осях работал по разному.
Но думаю что срабатывают всякие прерывания, защитник виндоус, антивирус и ещё много чего. Так же библиотечные функции работают гораздо медленней. Например, если код запустить много раз подряд, то время выполнения сравнивается т.е. 7-ка = XP. А у бесятки и этого мало, всё равно что-то процесс тормозит.
>>медленней чем на WinXP, а на БЕСЯТКЕ ещё медленней
это вы по Фрейду оговорились, или специально?
Потому как для меня она таки бесятка, без вариантов
Такая же закономерность для кода на фортране (числодробилка, правда довольно сложная).
Под виртуалкой (Windows XP mode) на 20% быстрее примерно.
Честно говоря, вы заинтриговали таким заявлением. Решил проверить для программы на Delphi, Win 32, работа со строками и файлами, в основном однопоток. Запустил обработку в виртуальной машине в Windows XP, и потом непосредственно в Windows 10. И что Вы думаете, в виртуальной машине тест был быстрее в полтора раза!

Со всеми этими графическими наворотами мы забыли, насколько мощными стали наши компьютеры…
Сразу сходу виден кодер.
Программист математику эту задачку отнесёт первым делом, а математик скажет, что квадранты придуманы давным давно, и напишет алгебру квадрантов для программиста. А программист всё и запрограммирует радостно. Но нет. Кодеры — это кодеры. Бесполезные существа.

Осталось только Программисту понять, что тут задача для математика и отнести ему. Сколько таких мест он пропустит? Напишет неэффективное решение и никто даже не заметит, что тут можно сделать на порядки быстрее. Если же Программист будет каждую хоть сколько-нибудь математичную задачу отдавать математику, то вскоре окажется, что все задачи программиста, кроме самых тривальных формочек, проходят сначала через математика. Осталось этого Математика научить кодировать, и он полностью заменяет такого программиста.

Я вот и есть такой математик, умеющий программировать. Составив алгоритм решения очередной задачи, я, конечно, могу этот алгоритм запрограммировать. Но в обязанности программиста входит не только написание программы, но и её дальнейшая поддержка, а вот этим заниматься не хочу. Если изменилась постановка задачи, то в алгоритм я изменения с удовольствием внесу, а в программу — не хочу. Поэтому математик может заменить программиста только в одноразовых программах: написал, запустил и выбросил.

Так они и не программисты, а некоторые ученые из всяких областей.

Кстати! А на сколько для заведомо тяжёлой задачи, оптимально использовать заведомо медленные ЯП, в точности Python?
Я считаю что лучше брать, например, С++ и интринстики, чтобы сразу получить быстрый код, по крайней мере точно знаешь, что программа не выполняет лишний код.
Хотя быстрая программа, это прежде всего быстрый алгоритм.

Например, мне удалось создать очень быстрый алгоритм для решения «Задача о 19 ферзях»
wasm.in/threads/zadacha-o-19-ferzjax.24611
Тут я использовал битовую доску т.е. BitBoard. Алгоритм придумал лет 18-20 назад, в детстве, когда только начал увлекаться программированием, и даже личного компа не было.
И да, алгоритм заведомо предполагает, что будет реализоваться на нормальном компилирующим ЯП.

Ну вот люди вроде меня используют. Я по образованию биолог, на питоне пишу прилично, а вот на C++ дальше хэлловорлда в десятом классе не забирался. Так что у меня есть по сути три опции:


а) Заведомо медленная имплементация на питоне. Раздражает, но если это научный код — то ему обычно достаточно отработать несколько раз и не очень важно, это 4 запуска по полчаса или 4 запуска по полсекунды
б) Учить плюсы. Не мешало бы, честно говоря, но как-то не так сильно надо, чтоб прям разбираться в довольно сложном языке и его экосистеме (а ведь там надо учиться не просто кодить, а оптимизировать, иначе смысла нет)
в) Нанять сишника. Тоже неплохая идея, но ему ж платить надо. Плюс скорость итерации падает, если не сам прям сел и заговнокодил идею, а надо ещё донести её до неспециалиста.

Посмотрите питоновские библиотеки numpy, scipy и pandas. Они специально были сделаны для эффективной работы с массивами данных (в том числе и научных).
Так как внутри у них неонка движок на С и FORTRAN, то на типовых задачах они могут дать скорость, сравнимую с сишным кодом.

Очевидно, что вне numpy/scipy я тысячи чисел ворочать и не собираюсь. Плюс sklearn для всякого обучения (да даже для тривиальных визуализаций типа PCA). Проблема в том, что многие проблемы биоинформатики — это какая-нибудь история с обработкой строк, для которой в питоне я супербыстрых имплементаций не знаю.

К есть еще вариант использовать numba. В сочетании с numpy — приличное ускорение.
Интересная статья, и я имею дело с сетками.
Но я не могу понять постановку задачи!
«Мы берём показания температуры и осадков из крупномасштабной глобальной климатической модели и сопоставляем их с мелкомасштабной локальной сеткой. Допустим, глобальная сетка равна 50×25, а локальная — 1000×500. Для каждой ячейки сетки в локальной сетке мы хотим знать, какой ячейке сетки в глобальной сетке она соответствует».
Я могу нарисовать сетку 50×25, каждую ячейку разбить сеткой 1000×500… а что надо дальше определить?
Help!
Не очень понятно. Ну и данных мало. Самое веселое если это две неструктурированных сетки. Но вроде структурированные — если прям задано сколько на сколько. Тогда ничего обходить не надо, а надо просто пересчитать алгебраически. Или ячейки разных размеров причем неизвестно каких? Тогда можно гибридно…
Жалко, что перевод — не спросить у автора.
Я понял задачу так (аналогия):
Допустим есть тетрадный лист разбитый на крупную клетку, мы дополнительно этот же лист размечаем миллиметровкой на мелкую сетку. Теперь, допустим каждая крупная клетка листа имеет свой цвет (параметры погоды), а нам надо узнать цвета для каждой мелкой ячейки миллиметровой сетки, выясняя какой клетке из крупной сетки она принадлежит.

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

ну как бы масштаб это коэффициент. умножаешь/делишь на него и переходишь от крупного/мелкого масштаба к другому

Где логика? В картографии все элементарно решается кодированием — когда каждому более мелкому участку карты присваивается код в котором указано в каком более крупном участке он лежит. И кто так задачи решает почему точку например в Африке ищут по всей сетке в том числе на северном полюсе? Тут задача не программерская, а наверное тест при собеседовании на логику.

которые написаны людьми без компьютерного образования, то есть учёными из других областей

Ничего удивительного, без профильного образования и опыта люди в любой сфере могут сотворить такую дичь, которая профессионалу позволит её разобрать и улучшить в кучу раз. Просто потому, что он уже решал такие задачи много раз. Тут надо о другом подумать — учёный хоть и плохонько, но всё же написал программу для решения своей задачи. А программист с нуля эту задачу вообще бы не решил, возможно даже и не сформулировал бы. Так что каждому своё.
Информатика даёт знания, логику и методы анализа, помогающие написать код, который выполнится за минимальное количество времени или с минимальным использованием ресурсов.

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

Зачастую, если программист изучал computer science, то написать хорошее решение не сильно сложнее, а иногда, даже проще. Был в моей практике пример, когда наивное решение — полный перебор — занимало 300 строк сложноватого кода, когда как хорошее решение динамическим программированием, мало того, что было сильно быстрее, еще и занимало 20 строк с комментариями.

Сегодня приличный Джуниор на собеседовании расскажет про The Big O. А годный Джуниор еще и попытается применить на практике.


Надо быть уж совсем деревянным, чтобы в подобной задаче не усмотреть очевидную возможность оптимизации.

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

Естественно. А что в природе есть программисты, знающие математические алгоритмы? Чё правда что ли?)) Вы чего там оптимизировать собрались-то? Зачем?
Математик даст вам квадранты, которые работают на сдвигах. И всё. Там нечего оптимизировать. Вообще нечего. [ВООБЩЕ НЕЧЕГО]

Для тех кто капитально в танке. Вы решили научиться летать. Но вы автолюбитель. Причём может быть даже крутой. А толку то?) Вот вы к своей убогой машине пилите крылья.
А на самом деле вам надо идти к инженеру авиастроителю) Однако же он вам скажет что ваша машина вообще никуда не годна, и предложит совершенно новую штуку, т.е. например вертолёт. Он вам не даст оптимизаций на авто, это же бессмыслица)))) Надо полагать, вы охотник до бессмыслиц?)

Тут не кран надо менять, а всю систему. (с)
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.