Comments 43
Хм, а сетка квадратная? Или там какие-то особенности из-за кривизны земли? Описанное в статье подозрительно похоже на задачу увеличения (или уменьшения) изображения, которая, как мне кажется, может быть решена вообще за O(width * height)
P.S. Почему-то думал что они делают бинарный поиск для каждого элемента, а они один раз ищут индексы независимо по x и y, а потом просто читают из сетки, так что у них тоже O(width * height) и всё ок.
Иногда прирост производительности можно получить вообще ничего не меняя в коде. Меня недавно удивил факт (и, думаю, удивит многих), что один и тот же код, который занимается применением регулярного выражения к разному тексту, на python на компьютере с windows 10 выполняется на 25% медленнее, чем в WSL2, которая запущена на этом же компьютере в этой же windows 10. Вероятно, тут какой-то косяк с реализацией модуля re под windows и поэтому такой неожиданный результат.
Если хотите попробовать то же самое, где я увидел этот эффект, то запустите launcher.py из https://github.com/ReinRaus/RegexCrossTool/
Суть всего этого кода проста: много раз в цикле применять регулярное выражение к разному тексту.
Заметная разница в производительности присутствует только для регулярных выражений, что скорее всего свидетельствует о проблеме в модуле re.
Забавен сам факт, что код, запущенный в WSL2 работает быстрее, чем в хостовой ОС.
Но лично мне странным кажется что прямо на много быстрее. MSVC очень не плохой компилятор так-то, как и реализация стандартных библиотек C/C++ не самая плохая у MS.
Плюс ещё совершенно разные ядра: разные реализации планировщика процессов/потоков, разные реализации системы управления памятью кучи процесса.На двух/четырёхъядерных CPU влияние это оказывает вот совсем никакое, а замеры ещё тогда делались. Это же чисто вычислительные задачи.
Но лично мне странным кажется что прямо на много быстрее. MSVC очень не плохой компилятор так-то, как и реализация стандартных библиотек C/C++ не самая плохая у MS.Мне тоже, но факт. Даже сборка mingw ранее на сайте лежала, можно было сравнить. Дело не в ОС, а в компиляторе.
Меня больше удивляет, что код который написан на ассемблере на Win7 выполняется заметней медленней чем на WinXP, а на бесятке ещё медленней. Хотя код не использует библиотек и довольно простой, и весь влезает в кэш.
Но у меня тут, код на разных Осях работал по разному.
Но думаю что срабатывают всякие прерывания, защитник виндоус, антивирус и ещё много чего. Так же библиотечные функции работают гораздо медленней. Например, если код запустить много раз подряд, то время выполнения сравнивается т.е. 7-ка = XP. А у бесятки и этого мало, всё равно что-то процесс тормозит.
Защита от Spectre/Meltdown и подобных уязвимостей скорее всего. Посмотреть состояние защиты можно PowerShell скриптом Get-SpeculationControlSettings. https://github.com/microsoft/SpeculationControl
это вы по Фрейду оговорились, или специально?
Потому как для меня она таки бесятка, без вариантов
Под виртуалкой (Windows XP mode) на 20% быстрее примерно.
Со всеми этими графическими наворотами мы забыли, насколько мощными стали наши компьютеры…
Программист математику эту задачку отнесёт первым делом, а математик скажет, что квадранты придуманы давным давно, и напишет алгебру квадрантов для программиста. А программист всё и запрограммирует радостно. Но нет. Кодеры — это кодеры. Бесполезные существа.
Осталось только Программисту понять, что тут задача для математика и отнести ему. Сколько таких мест он пропустит? Напишет неэффективное решение и никто даже не заметит, что тут можно сделать на порядки быстрее. Если же Программист будет каждую хоть сколько-нибудь математичную задачу отдавать математику, то вскоре окажется, что все задачи программиста, кроме самых тривальных формочек, проходят сначала через математика. Осталось этого Математика научить кодировать, и он полностью заменяет такого программиста.
Так они и не программисты, а некоторые ученые из всяких областей.
Я считаю что лучше брать, например, С++ и интринстики, чтобы сразу получить быстрый код, по крайней мере точно знаешь, что программа не выполняет лишний код.
Хотя быстрая программа, это прежде всего быстрый алгоритм.
Например, мне удалось создать очень быстрый алгоритм для решения «Задача о 19 ферзях»
wasm.in/threads/zadacha-o-19-ferzjax.24611
Тут я использовал битовую доску т.е. BitBoard. Алгоритм придумал лет 18-20 назад, в детстве, когда только начал увлекаться программированием, и даже личного компа не было.
И да, алгоритм заведомо предполагает, что будет реализоваться на нормальном компилирующим ЯП.
Ну вот люди вроде меня используют. Я по образованию биолог, на питоне пишу прилично, а вот на C++ дальше хэлловорлда в десятом классе не забирался. Так что у меня есть по сути три опции:
а) Заведомо медленная имплементация на питоне. Раздражает, но если это научный код — то ему обычно достаточно отработать несколько раз и не очень важно, это 4 запуска по полчаса или 4 запуска по полсекунды
б) Учить плюсы. Не мешало бы, честно говоря, но как-то не так сильно надо, чтоб прям разбираться в довольно сложном языке и его экосистеме (а ведь там надо учиться не просто кодить, а оптимизировать, иначе смысла нет)
в) Нанять сишника. Тоже неплохая идея, но ему ж платить надо. Плюс скорость итерации падает, если не сам прям сел и заговнокодил идею, а надо ещё донести её до неспециалиста.
Так как внутри у них
Очевидно, что вне numpy/scipy я тысячи чисел ворочать и не собираюсь. Плюс sklearn для всякого обучения (да даже для тривиальных визуализаций типа PCA). Проблема в том, что многие проблемы биоинформатики — это какая-нибудь история с обработкой строк, для которой в питоне я супербыстрых имплементаций не знаю.
Жаль, что сейчас Delphi даже не рассматривают. Хотя там быстрый компилятор, нативный код, и есть бесплатная Community Edition https://www.embarcadero.com/products/delphi/starter
Но я не могу понять постановку задачи!
«Мы берём показания температуры и осадков из крупномасштабной глобальной климатической модели и сопоставляем их с мелкомасштабной локальной сеткой. Допустим, глобальная сетка равна 50×25, а локальная — 1000×500. Для каждой ячейки сетки в локальной сетке мы хотим знать, какой ячейке сетки в глобальной сетке она соответствует».
Я могу нарисовать сетку 50×25, каждую ячейку разбить сеткой 1000×500… а что надо дальше определить?
Help!
Как я понял, это два разбиения одного и того же участка.
Жалко, что перевод — не спросить у автора.
Допустим есть тетрадный лист разбитый на крупную клетку, мы дополнительно этот же лист размечаем миллиметровкой на мелкую сетку. Теперь, допустим каждая крупная клетка листа имеет свой цвет (параметры погоды), а нам надо узнать цвета для каждой мелкой ячейки миллиметровой сетки, выясняя какой клетке из крупной сетки она принадлежит.
Где логика? В картографии все элементарно решается кодированием — когда каждому более мелкому участку карты присваивается код в котором указано в каком более крупном участке он лежит. И кто так задачи решает почему точку например в Африке ищут по всей сетке в том числе на северном полюсе? Тут задача не программерская, а наверное тест при собеседовании на логику.
которые написаны людьми без компьютерного образования, то есть учёными из других областей
Ничего удивительного, без профильного образования и опыта люди в любой сфере могут сотворить такую дичь, которая профессионалу позволит её разобрать и улучшить в кучу раз. Просто потому, что он уже решал такие задачи много раз. Тут надо о другом подумать — учёный хоть и плохонько, но всё же написал программу для решения своей задачи. А программист с нуля эту задачу вообще бы не решил, возможно даже и не сформулировал бы. Так что каждому своё.
Информатика даёт знания, логику и методы анализа, помогающие написать код, который выполнится за минимальное количество времени или с минимальным использованием ресурсов.
Осталось добавить временные ресурсы и человеческие, и мы можем получить в результате что работающий в 14000 раз быстрее код может оказаться более прожорливым на ресурсы. ;)
Зачастую, если программист изучал computer science, то написать хорошее решение не сильно сложнее, а иногда, даже проще. Был в моей практике пример, когда наивное решение — полный перебор — занимало 300 строк сложноватого кода, когда как хорошее решение динамическим программированием, мало того, что было сильно быстрее, еще и занимало 20 строк с комментариями.
Сегодня приличный Джуниор на собеседовании расскажет про The Big O. А годный Джуниор еще и попытается применить на практике.
Надо быть уж совсем деревянным, чтобы в подобной задаче не усмотреть очевидную возможность оптимизации.
В любой теме про собеседования толпы недовольных тем, что спрашивают никому не нужные О-большие и алгоритмы. Вон в этой же теме на полном серьезе человек пишет, что должен быть в команде математик, которому эту задачу Программист должен отнеси.
Математик даст вам квадранты, которые работают на сдвигах. И всё. Там нечего оптимизировать. Вообще нечего. [ВООБЩЕ НЕЧЕГО]
Для тех кто капитально в танке. Вы решили научиться летать. Но вы автолюбитель. Причём может быть даже крутой. А толку то?) Вот вы к своей убогой машине пилите крылья.
А на самом деле вам надо идти к инженеру авиастроителю) Однако же он вам скажет что ваша машина вообще никуда не годна, и предложит совершенно новую штуку, т.е. например вертолёт. Он вам не даст оптимизаций на авто, это же бессмыслица)))) Надо полагать, вы охотник до бессмыслиц?)
Тут не кран надо менять, а всю систему. (с)
Ускорение в 14 000 раз или Победа компьютерной науки