Aragaer
"а задача же тривиальная, неужели нельзя сделать за квадрат?"
Anonymous
Для того, что бы писать любой код - анализ алгоримтов не нужен. Потому что это не имеет практически ни какого отношения к реальности.
Нет. Допустим, мы с коллегой придумали 2 алгоритма вычисления чего-либо. Сравнивать мы будем его по биг оу, потому что она показывает наихудшее время работы алго
Bogdan (SirEdvin)
Aragaer
естессно
Aragaer
не, понятно, что оценивать константу тоже можно
Aragaer
но просто "вот код, он должен вызываться 100500 раз в секунду"
Bogdan (SirEdvin)
Слышал. К чему это?
К тому что *нельзя* сравнивать алгоримты по О большому. Если вы так далее, вы делаете неправильно. В качестве примера можно привести умножение матриц, где самый асимптотически быстрый алгоритм имеет слишком большую константу и не используется.
Bogdan (SirEdvin)
когда ты смотришь на код и говоришь "но это же говно, оно работает за куб!"
Почему не сказать "вместо трех вложенных циклов, можно сделать два?"
Bogdan (SirEdvin)
И будут примеры посложнее?
Aragaer
и ты такой - "ну можно сделать просто за логарифм, но это потребует квадрат памяти, а можно сделать за квадрат, но зато константа памяти"
Bogdan (SirEdvin)
Что-то в духе, у тебя тут O( n * log n + m * log m + s^3), а ведь можно ..."
Aragaer
и надо просто попробовать то и другое
Bogdan (SirEdvin)
и ты такой - "ну можно сделать просто за логарифм, но это потребует квадрат памяти, а можно сделать за квадрат, но зато константа памяти"
И тут на помощь приходят бенчмарки
Aragaer
естессно
Bogdan (SirEdvin)
Потому что правильно высчитать константу у вас не получится
Aragaer
и не надо
Bogdan (SirEdvin)
Тогда зачем думать в терминах O-большого?
Aragaer
конечно бенчмарки
Aragaer
но бенчмарк не даст готового ответа
Anonymous
И тут на помощь приходят бенчмарки
Дополнительное время для кодинга - проеб по деньгам. Можно подумать, и оценить биг оу
Aragaer
и если бенчмарк говорит "это хреново", то ты начинаешь думать, а можно ли сделать лучше
Bogdan (SirEdvin)
Дополнительное время для кодинга - проеб по деньгам. Можно подумать, и оценить биг оу
И получить абсолютно такой же проеб по деньгам. Ой. Потому что вы не можете оценить константу.
Bogdan (SirEdvin)
Bogdan (SirEdvin)
Потому что в 95% О(логН) лучше чем О(н)
Пруфы будут? Я вот откровенно говоря, не уверен
Aragaer
"да, тут хреново, потому что квадрат.... а вообще, может есть способ сделать хотя бы за н лог н?... Требует переделать все структуры данных. Пробуем?"
Aragaer
потому что это разговоры, которые я реально регулярно слышу на работе
Bogdan (SirEdvin)
Кормен в помощь
У него там есть пруф, где он посчитал все алгоритмы и такой "ну вот, в 95% случаев все ок"? Сомневаюсь
Aragaer
лайн профайлер покажет тебе, что на обработке массива в 1000 элементов ты пробегаешь по некоторой строке миллион раз.
Bogdan (SirEdvin)
потому что это разговоры, которые я реально регулярно слышу на работе
Страшные люди у вас на работе, я не знаю, мне завидно или нет
Bogdan (SirEdvin)
лайн профайлер покажет тебе, что на обработке массива в 1000 элементов ты пробегаешь по некоторой строке миллион раз.
И да, в такой момент до меня доходит, что надо переделать алгоритм
Anonymous
Bogdan (SirEdvin)
А можно было бы сесть и погрустить, но орать оно проще, да. Ведь О-большое для ора всего-то log n?
Aragaer
не, я не понимаю, чего не так в о-большом. Не рокет сайнс же
Aragaer
ты смотришь на код и видишь его о-большое.
Bogdan (SirEdvin)
Ну, я не понимаю, зачем оно нужно, если есть бенчмарки
Aragaer
их надо запускать
Bogdan (SirEdvin)
Окей
Aragaer
а на всяком эмбеддед оборудовании в дальних полях это бывает делать не очень удобно
Bogdan (SirEdvin)
Какое будет О-большое от доставания элемента из словаря?
Bogdan (SirEdvin)
И в догонку, такой же вопрос про добавление элемента в конец обычного списка
Aragaer
формально считается за константу, реально зависит от размера хэша
Aragaer
добавление в конец односвязного списка - линия от длины списка. Циклического - константа
Bogdan (SirEdvin)
На самом деле, формально - O(m), где m - это максимальное количество коллизий
Bogdan (SirEdvin)
добавление в конец односвязного списка - линия от длины списка. Циклического - константа
В список питона, который list
Aragaer
константа+время на аллокацию
Aragaer
потому что списки в питоне циклические и из связанных блоков
Anonymous
К тому же, ты понимаешь, что словарь это абстрактная структура данных и ее как следствие нельзя анализировать с помощью О?
Aragaer
На самом деле, формально - O(m), где m - это максимальное количество коллизий
это если при коллизии идет линейный поиск. Но есть другие споосбы
Tishka17
Bogdan (SirEdvin)
К тому же, ты понимаешь, что словарь это абстрактная структура данных и ее как следствие нельзя анализировать с помощью О?
А у вас есть не абстрактные структуры в питоне?
Bogdan (SirEdvin)
Кстати, не расскажешь как? А то я буду очень долго ковырять код
Aragaer
для словаря там есть где-то логарифмы, но эти логарифмы ограничены сверху какими-то размерами, поэтому "не больше константы"
Tishka17
https://m.habr.com/ru/post/247843/
Tishka17
Там хитро коллизии считаются
Ivan
на дворе ж уже 3.7, а в нём словари упорядочены
Aragaer
а у нас на работе кстати один человек действительно занимается тем, что пишет код для быстрого перемножения матриц, опираясь на какие-то там оптимизированные алгоритмы
Aragaer
но я не математик, деталей не знаю
Bogdan (SirEdvin)
Такое же замечание как у человека выше, походу надо таки читать доку в коде :(
Bogdan (SirEdvin)
Что?)
Ну, вы же понимаете, что сложность алгоримтов должна как бы складывается? Если вы оцениваете алгоримт сверху, чисто по циклу, то это как-то очень странно
Aragaer
воо
Aragaer
На самом деле, формально - O(m), где m - это максимальное количество коллизий
Прикол в том, что "максимальное количество коллизий" вполне может быть константой
Anonymous
Ну, вы же понимаете, что сложность алгоримтов должна как бы складывается? Если вы оцениваете алгоримт сверху, чисто по циклу, то это как-то очень странно
Когда Н стремится к бесконечности, член полинома с наибольшей степенью имеет наибольшее значение и другие значение из-за этого не так важны
Aragaer
и по ссылке на реализацию словаря в питоне эта константа равна 8
Bogdan (SirEdvin)
Что-то я немного туплю. А что будет, когда у меня в словаре будет 9 коллизий? Оно одну перезатрет?
Aragaer
я бы на месте словаря в этом случае поменял хэшфункцию
Aragaer
да, вставка в словарь тогда теоретически может быть медленной
Bogdan (SirEdvin)
Когда Н стремится к бесконечности, член полинома с наибольшей степенью имеет наибольшее значение и другие значение из-за этого не так важны
l = # случайный список
for i in l:
print(any(map(lambda j: i == j, l))
У вас внутри цикла может быть скрыта равнозначная или хуже операция. Тут это видно, но далеко не всегда так.
Bogdan (SirEdvin)
Но немного потупив, я думаю, что @aragaer в чем-то прав и O-big возможно неплохой путь, для того, что бы попробовать понять, что можно сделать лучше, после того как было обнаружено, что все плохо
Pavel
l = # случайный список
for i in l:
print(any(map(lambda j: i == j, l))
У вас внутри цикла может быть скрыта равнозначная или хуже операция. Тут это видно, но далеко не всегда так.
вот для таких случаев есть еще метрики читаемости и цикломатической сложности, что позволяет заставлять рефакторить это всё
Pavel
вот для таких случаев есть еще метрики читаемости и цикломатической сложности, что позволяет заставлять рефакторить это всё
s/читаемости/поддерживаемости/g
Bogdan (SirEdvin)
вот для таких случаев есть еще метрики читаемости и цикломатической сложности, что позволяет заставлять рефакторить это всё
Метрика цикломатической сложности же как раз поощряет вынос циклов из одной функции в другую. Она вроде не считает вглубь
Pavel
именно так. но при этом легче читается. и легче понять, что в цикле будет твориться какая-то дичь
Bogdan (SirEdvin)
Не уверен, в коде бывает достаточно дичи. Хотя лучше будет, скорее всего