Здравствуйте, koenig, Вы писали:
K>топологическая сортировка — она ж про зависимости? как в принципе зависимости отрезолвить посредством скалярного атрибута (хоть size, хоть еще какого)?
Тот элемент, который ни от кого не зависит — у него size по детям будет 0. У кого будет 1 зависимый — у него size по детям будет 1. И т.д. Кто зависит от всех — у того size будет максимальный. Потому прекрасно все сортируется стандартным алгоритмом сортировки через немного нестандартный компаратор. Более того, именно это решение преподают студентам кажется в Беркли в курсе алгоритмов как наивное, и далее показывают как его улучшить если нужно быстрее. Если что, такую наивную реализацию я не сам придумал, если б курс по алгоритмам в свое время не прослушал и кое что не запомнил, может быть и гуглил бы когда понадобилось . Также запомнил, что у алгоритма кроме вычислительной сложности есть еще такой немаловажный параметр, как понятность, и если обстоятельства позволяют — лучше использовать более понятный алгоритм. Если б самообразованием не занимался в свое время — может быть и фигачил всегда сверхоптимальные копипасты когда надо и когда не надо.
Здравствуйте, elmal, Вы писали:
НС>>Ну вот ты и продемонстрировал наглядно, зачем нужны задачки. Потому что O(N) алгоритмы абсолютно тривиальны, да и их писать обычно не нужно. E>Нужно сначала гуглить, потом искать в каком пакете где это лежит, подключать зависимости и т.д.
О да, отмазок много. А по факту — косячное, запутанное и тормозное решение в коде. ЧТД.
E> У готового решения может быть не очень удобное API
А у танцора — слишком большие яйца.
E>На практике потратишь больше времени, чем на быстрое наивное решение.
На практике ты уже показал отличную иллюстрацию моих слов.
E> В твоем случае там 257 строк
Там столько строк, потому что всякими удобствами, коммнентариями и улучшизмами обвешано, чтобы потом некоторые не рассказывали про неудобный API. Да еще плюсом там детектор циклов. Сам же алгоритм — 49 строк вместе с детектором.
E>, нужно еще как то быть кверенным что там нет багов, наивное быстрое решение пишется в 1 строчку сходу и ошибиться там сложно.
Вот ты продемонстрировал вторую проблему гномикоборцев. Даже если им пальцем показать на готовое правильное решение, они будут упираться до посинения и придумывать миллион безумных аргументов, но свое первое решение неверным не признают никогда.
Здравствуйте, Тёмчик, Вы писали:
Тё>Если копнуть глубже, есть улучшения как например Тё>A space-efficient algorithm for finding strongly connected components David J.Pearce
Ну, это уже второй вопрос. Тут хотя бы самый банальный алгоритм знать бы или хотя бы простейший поисковый запрос в гугле написать.
E>>>Ибо все просто — чем более оптимизированный код, тем он всегда сложнее читается Тё>Декомпозиция для чего? Так то можно и всё приложение одной портянкой из спагетти сделать.
Здравствуйте, El Camino Real, Вы писали:
V_S>>Беда — это код математика с функциями по полторы-две тысячи строк, юзающими к тому же кучу глобальных переменных с очень информативными именами типа i, ii, iii, k, kk, kkk.... "ну а что, работает же!" ECR>Не, я обычно использую аргументацию "ну, перепиши!". Даже могу поспособствовать выделению бюджета. Но программисты всё равно взвывают.
Контр-аргументация простая, как доска — а что будете делать, когда (не "если", а именно "когда") этот математик выйдет на пенсию, и "вдруг" окажется, что код математика не масштабируется. Или "вдруг" найдутся непредусмотренные граничные условия?
Здравствуйте, smeeld, Вы писали:
S>Вижу и знаю только одно-качественный программер не проходит собеседований.
Я об этом и написал. Но до этого еще надо дорасти. Причем не только профессионально. Непризнанные гении тут не прокатывают, нужны признанные. Но если у тебя неадекватный ЧСВ, признанным ты вряд ли станешь.
Здравствуйте, elmal, Вы писали:
E>На самом деле во многих случаях достаточно квадрата, если квадрат работает нормально на расчетных данных. Вот мне на практике несколько раз требовалось писать топологическую сортировку. Я ее всегда писал с квадратичной сложностью. За 5 минут — применяю метод обхода каждой ноды и дергаю у всего этого size, и это натравливаю на стандартный sort — все.
Что такое size?
Как-то в коде был квадрат, он работал минут 10 и это не было критично. Потом оказалось, что количество входных данных перевалило за миллион и квадрат справляться перестал. Пришлось переписывать. И было это не легко, т.к. код запутанный и делал какие-то совсем не очевидные вещи, которые желательно было сохранить. Не то, чтобы это очень надо было для задачи, но заказчики уже так привыкли. Если бы сразу писали без квадрата, было бы в разы проще.
E>Весьма понятный и очевидный код получается, хоть и потенциально медленный. Ибо пофиг, это совсем не критичное место и N не превышает 100 в самом худшем случае. Если же это окажется вдруг проблемным местом, я сначала возьму простой трюк мемоизации, причем универсальной, над одним методом, в результате на практических задачах уже это будет N log N практически.
Там же алгоритм имеет O(N).
E>Ибо все просто — чем более оптимизированный код, тем он всегда сложнее читается, тем сложнее там что то менять. И без крайней необходимости лучше код не запутывать.
Здесь вопрос организации кода. Пишется абстракция графа, и пишется топологическая сортировка. Всё. Для клиента это всё выглядит как вызвать функцию для графа. А внутри может быть хоть квадратичная сложность, хоть кубическая. Но опять же алгоритмы не такие уж и сложные, чтобы быстрый алгоритм был запутанный.
Сложности возникают, если путают логику программы с алгоритмами сортировки, когда вдруг они должны знать, что сортировка производится не для графа, а для графа фотографий или ещё чего.
E>Какого хрена мне оптимизировать пусть даже секунду на топологической сортировке, если то, ради чего эта сортировка выполняется, гоняется вообще несколько часов потом на кластере стандартной коммерческой дорогой и крайне оптимизированной решалкой. Что, закон Амдала отменили чтоль ?
Можно попытаться и распараллелить. Только читаемость вряд ли улучшится.
Здравствуйте, The Passenger, Вы писали:
TP>это ладно — я вот тест в одну финансовую компанию проходил — там процентов на 80 были задачи на вращение треугольников — типа — TP>поверните направо налево — теперь ответьте как он лежит
TP>вот я до сих пор в недоумении
TP>отнесся несерьезно и не прошел.
Догадываюсь, что это за компания...
В свое время в школе на уроках черчения я обнаружил у себя талант к подобным задачам. Но, так как я терпеть не мог черчение, то считал этот талант абсолютно бесполезным. Никогда бы не догадался, что бесполезное умение поворачивать в уме треугольники в будущем так сильно повлияет на мою жизнь
До сих пор не могу понять, зачем давать программистам такие тесты, это блин даже не IQ тест и не задачи про гномиков... Он никак не проверяет абстрактное логическое мышление, которое нужно программисту. Ну, я еще могу понять если бы надо было программировать терхмерную графику, но к финансам это вообще не имеет никакого отношения (трейдеры кстати совсем другой тест проходят).
Здравствуйте, ksandro, Вы писали:
K>До сих пор не могу понять, зачем давать программистам такие тесты, это блин даже не IQ тест и не задачи про гномиков... Он никак не проверяет абстрактное логическое мышление, которое нужно программисту. Ну, я еще могу понять если бы надо было программировать терхмерную графику, но к финансам это вообще не имеет никакого отношения (трейдеры кстати совсем другой тест проходят).
Да что вы все до треугольников докопались? Это всего лишь пара вопросов из 100. Большинство вопросов вполне релевантные: логические задачки (кто в каком доме живет), найти состояние конечного автомата после n шагов, несложные финансовые задачки. Из совсем нелепых помню только задачки на внимательность типа посчитать сколько раз встречается буква A в небольшом тексте.
Здравствуйте, alzt, Вы писали:
A>Там же алгоритм имеет O(N).
На многих задачах реально на практике пофиг — N это или N*N. Даже экспонента может сойти, никто и не заметит при N = 10, когда известно что N что N никогда больше не будет. А если заметят и вдруг окажется узким местом — ловится все на раз, и чинится. Не нужно всегда и во всем иметь минимальную вычислительную сложность. В первую очередь всегда нужно думать — нужно это или не нужно. И если наивный но понятный квадрат или хуже допустим — ничего страшного не случится. Вот предположим N — это количество стран. Пофиг как ты эти 252 страны будешь сортировать, за N*N или даже за N. Стран миллион не будет при жизни очень и очень многих поколений, если вообще когда будет. Более оптимальный алгоритм практически всегда гораздо более сложный, чем наивный. И не нужно без необходимости городить лишнюю сложность, чтобы уменьшить время отклика с секунды на 999 миллисекунд. Это один из базовых принципов в Computer Science вообще то.
A>Можно попытаться и распараллелить. Только читаемость вряд ли улучшится.
Уже все, что надо, и максиматьно оптимизировано и все распараллелено. Сама задача NP Complete, она даже в упрощенной форме относится к классическим. Соответственно получается базовое решение, дальше постепенно генетическими алгоритмами это все улучшается до тех пор, пока позволяет время, и далее выдается субоптимальное решение, и этого достаточно.
Здравствуйте, elmal, Вы писали:
E>А если заметят и вдруг окажется узким местом — ловится все на раз, и чинится.
А ракета уже упала. Чинить поздно.
E>Пофиг как ты эти 252 страны будешь сортировать, за N*N или даже за N. Стран миллион не будет при жизни очень и очень многих поколений, если вообще когда будет.
"640K ought to be enough for anybody".
А потом кто-то заменит список стран на индексы, например, и приехали. Или ещё один умник засунет сортировку в другой квадратичный алгоритм.
Здравствуйте, elmal, Вы писали:
E>Здравствуйте, alzt, Вы писали:
A>>Там же алгоритм имеет O(N). E>На многих задачах реально на практике пофиг — N это или N*N. Даже экспонента может сойти, никто и не заметит при N = 10, когда известно что N что N никогда больше не будет. А если заметят и вдруг окажется узким местом — ловится все на раз, и чинится.
Ага. И потом сидят такие суперпрактики и чинят. Вот только чинят они не сложность, а демонстрируют чудеса битовыжимания. Константу починят, а О(n дохрена) осталась как была.
Здравствуйте, ned, Вы писали:
E>>А если заметят и вдруг окажется узким местом — ловится все на раз, и чинится. ned>А ракета уже упала. Чинить поздно.
Ага. И упала она потому, что какой-то умник заменил O(N^2) на O(N), чем похерил тайминги. Или, что еще более вероятно, устроил локальный расстрел памяти. Или все вместе.
Чтобы ракеты не падали, нужно не на алгоритмы этосамое вприсядку. Нужно тестировать. Тестировать все и во всех возможных вариантах.
А за использование отладчика выгонять с волчьим билетом.
Здравствуйте, Ночной Смотрящий, Вы писали:
НС>Ага. И потом сидят такие суперпрактики и чинят. Вот только чинят они не сложность, а демонстрируют чудеса битовыжимания. Константу починят, а О(n дохрена) осталась как была.
А вот как с минимальными изменениями исходного алгоритма починить сложность — какого то черта с этой простейшей практической задачей не могут справиться большинство любителей преждевременной оптимизации. У большинства оптимальные решения конкретных задач тупо зазубрены в лучшем случае. Сделать конфетку по сложности с минимальной модификацией исходного кода какого то черта могут единицы. Все полностью переписать чтоб ускорить за черти какое время при неизменных условиях — здесь много ума не надо. На практике зачастую для ускорения в тысячи раз достаточно точечных локальных изменений, которые очень быстро как делаются, так и находятся. При условии нормальной декомпозиции это вообще не задача.
Здравствуйте, elmal, Вы писали:
E>А вот как с минимальными изменениями исходного алгоритма починить сложность
Подожди. Ты нам только что тут расписывал, как прекрасно все фиксится при необходимости.
E> — какого то черта с этой простейшей практической задачей не могут справиться большинство любителей преждевременной оптимизации.
А большинство любителей преждевременной пессимизации?
E> У большинства оптимальные решения конкретных задач тупо зазубрены в лучшем случае. Сделать конфетку по сложности с минимальной модификацией исходного кода какого то черта могут единицы. Все полностью переписать чтоб ускорить за черти какое время при неизменных условиях — здесь много ума не надо.
Это что, попытка сменить тему?
E> На практике
Опять на практике. На практике ты нам тут рассказывал про топосорт с n^2, который ты, при необходимости, обещал сложным алгоритмом и кучей времени превратить в n*log n. Вот это как раз практика и есть, а не то что ты рассказываешь.
E>зачастую для ускорения в тысячи раз достаточно точечных локальных изменений, которые очень быстро как делаются, так и находятся.
А если недостаточно? Бросаем проект? Или срочно бежим искать нормального разработчика?
Здравствуйте, Ночной Смотрящий, Вы писали:
НС>Опять на практике. На практике ты нам тут рассказывал про топосорт с n^2, который ты, при необходимости, обещал сложным алгоритмом и кучей времени превратить в n*log n. Вот это как раз практика и есть, а не то что ты рассказываешь.
Каким к черту сложным алгоритмом? Он превращается в n*log n банальной универсальной мемоизацией вообще без усилий, поставить мемоизацию сразу мешает только банальная лень. На тысяче элементов ты хрен когда заметишь разницу между n и n*n, а уж между n и n log n тем более. Небольшие проблемы, когда квадрат уже полная фигня — это миллионы. А когда миллиард — вот тогда приходится очень сильно извращаться, и асимптоматика должна быть максимальной, и еще нужно о крайне многих вещах думать, например как максимально поместить данные в кеш процессора чтоб не потерять всю скорость, плюс как загрузить эффективно все ядра и многое другое.
НС>А если недостаточно? Бросаем проект? Или срочно бежим искать нормального разработчика?
А если недостаточно — тогда действительно пишем максимально оптимально конкретное место. Только снова на практике — это узкое место будет видно сразу же на этапе постановки задачи, ибо на этапе постановки задачи будет сразу понятно что данных там миллиард (да хоть и миллион даже, но будет сразу понятно, что сама эта задача является основной, а не второстепенной). Тогда сразу асимптоматика будет нужная, а уже над низкоуровневыми оптимизациями придется повозиться. Возможно несколько раз придется еще и переписывать алгоритм с изначально хорошей асимптоматикой, но на более сложный и запутанный, но лучше применимый к конкретной задаче.
Общий принцип. Чем проще у тебя изначальные алгоритмы — тем больший простор для всяких изменений кода при изменениях требований. Как только ты начинаешь оптимизировать — тем меньше у тебя простора для изменений. Приходится и данные перепаковывать определенным оптимальным образом, и зависимости ненужные делать чтоб избежать лишних проходов и т.д, там до черта приходится делать, в рехультате код очертененно теряет в универсальности, но работает быстро, зачастую на пределе возможностей железа. И уже в оптимизированный код вносить изменения получается полная жесть. Потому там, где это не нужно — не нужно излишне запутывать код. Нужно сначала найти проблемные места, и только затем их оптимизировать.
Я уж молчу о том, что на определенных N n*n бывает быстрее n log n. Ибо какого то черта в методе sort во многих либах при определенных n внутри оказывается пузырек.
Здравствуйте, ksandro, Вы писали:
K>Догадываюсь, что это за компания...
Они, к стати, сейчас на хакерранк тесты перешли — это я еще могу понять ... хотя там тоже пару раз фэйлился, но в другие конторы
фэйлился в основном на том что с английским было не очень хорошо — пока поймешь — время идет
потом долго бодался с консолью — как аргументы получить и распарсить — занимало большинство времени ... ну не работаю я давно с консолью
и в ожидании подвоха — пытался найти более элегантное решение чем в лоб, а потом понимал что в лоб и надо.
K>В свое время в школе на уроках черчения я обнаружил у себя талант к подобным задачам. Но, так как я терпеть не мог черчение, то считал этот талант абсолютно бесполезным. Никогда бы не догадался, что бесполезное умение поворачивать в уме треугольники в будущем так сильно повлияет на мою жизнь
Работаешь там?
Думаю еще раз попробовать осенью
K>До сих пор не могу понять, зачем давать программистам такие тесты, это блин даже не IQ тест и не задачи про гномиков... Он никак не проверяет абстрактное логическое мышление, которое нужно программисту. Ну, я еще могу понять если бы надо было программировать терхмерную графику, но к финансам это вообще не имеет никакого отношения (трейдеры кстати совсем другой тест проходят).
на самом деле, я так полагаю, это тест на возможность представления и просчета алгоритма по шагам в голове ... но мне, если надо, я рисую.
... но всеравно — они както умудряются описать задачи, вроде и по английски, но после одного прочтения нифига не понятно
Здравствуйте, landerhigh, Вы писали:
L>Ага. И упала она потому, что какой-то умник заменил O(N^2) на O(N), чем похерил тайминги. Или, что еще более вероятно, устроил локальный расстрел памяти. Или все вместе.
Поэтому нужно сразу писать O(N). А так да, "рефакторинг без причины – признак дурачины".
L>Чтобы ракеты не падали, нужно не на алгоритмы этосамое вприсядку. Нужно тестировать. Тестировать все и во всех возможных вариантах.
Там проблема в том что и софт и железо разрабатываются одновременно. Годами.
Здравствуйте, ned, Вы писали:
L>>Ага. И упала она потому, что какой-то умник заменил O(N^2) на O(N), чем похерил тайминги. Или, что еще более вероятно, устроил локальный расстрел памяти. Или все вместе. ned>Поэтому нужно сразу писать O(N).
Ага. Сразу. Особенно в случаях, когда O(N^2) оказывается быстрее, чем O(N) и даже, какой кошмар, O(1)
L>>Чтобы ракеты не падали, нужно не на алгоритмы этосамое вприсядку. Нужно тестировать. Тестировать все и во всех возможных вариантах. ned>Там проблема в том что и софт и железо разрабатываются одновременно. Годами.
Не вижу проблемы. Для всего сложнее онлайн-бложека это совершенно нормальная ситуация.
. Также запомнил, что у алгоритма кроме вычислительной сложности есть еще такой немаловажный параметр, как понятность, и если обстоятельства позволяют — лучше использовать более понятный алгоритм. Если б самообразованием не занимался в свое время — может быть и фигачил всегда сверхоптимальные копипасты когда надо и когда не надо.
