Здравствуйте, so5team, Вы писали:
S>Ну вот, чуть какие-то сложности встречаешь и сразу сдриснуть хочешь. Нет, Тёмчик, одних публичных обосратушек недостаточно, ты можешь еще. Расскажи почтенной публике, что будет делать этот самый коллектор в своем деструкторе, если его разрушают до очередного вызова sweep(), но после того, как в него засунули очередной набор коннекшенов?
Я, я знаю!! Спросите меня! Надо сделать коллектор коллекторов!!!
Здравствуйте, AmSpb, Вы писали:
AS>Можно не знать реализации тех или иных структур и алгоритмов, но знать сложность обязан, а если лень знать, распечатываешь и вешаешь перед собой
Знать за сложность надо, да. Но надо ж ещё понимать что именно за этим стоит. А то куча народу дрочит на big-О вприсядку до состояния слепой веры.
А то ж порой бывает и так что алгоритм с линейной сложностью работает быстрее чем с логарифмической, просто потому что цена одного "шага" разная.
Здравствуйте, Тёмчик, Вы писали:
Тё>Такие приходили собеседоваться, включая и онлайн из России. Судя по тому, как у некоторых участников раскалён коллектор на bigO, как они пытаются доказать, что bigO не на первом месте по важности, делаю выводы.
Здравствуйте, cppguard, Вы писали:
C>На самом деле задачки-то лёгкие. Я открыл статью в надежде найти очередной снобизм олимпиадников восьмидесятого уровня, а оказалось, что автор даже подумать не хочет, а сразу пишет первое, что пришло в голову (не очень-то читаемое). Я сам противник проверки книжных знаний на собеседовании, но вот, видимо, не зря их спрашивают.
особенно понравилось
Тут же меня спросили, какова сложность алгоритма — ок, норм, это нужно знать, потому что в реальном программировании мне это потребовалось целых 0 раз.
Реально питон головного мозга. Вроде и программист, но как с другой планеты.
aik>Ну и какой смысл спрашивать вот этот вот кодинг раз за разом? Он же точно не будет целыми днями только этим и заниматься
Поэтому нужно спрашивать архитектуру высоконагруженного приложения! Ведь программисты точно целыми днями только этим и занимаются. По 3 высоконагруженных приложения в час выпекают в среднем.
Здравствуйте, so5team, Вы писали:
S>Тёмчик, тебя до сих пор травма с C++ не отпускает потому, что ты откровенно хреновый C++ник и тебе,
Когда я был плюсником, приходилось ассенизировать последствия после таких, как ты, глотающих все исключения в цикле. И кстати, эти глотальщики долго не задерживались. Может быть, в Бабруйске ты первый хакер на деревне, а я работал в более крутых компаниях. Судя что до Москвы ты не доехал, может быть, не смог строку развернуть? После откровений про глотания не удивлен.
Здравствуйте, sergey2b, Вы писали:
S>в принципе задачки нормальные, не чем не хуже реверса отдельных слов в строке S>и поиск цикла в list
S>https://habr.com/ru/post/550088/ S>Собеседование в Яндекс: театр абсурда :/
На самом деле задачки-то лёгкие. Я открыл статью в надежде найти очередной снобизм олимпиадников восьмидесятого уровня, а оказалось, что автор даже подумать не хочет, а сразу пишет первое, что пришло в голову (не очень-то читаемое). Я сам противник проверки книжных знаний на собеседовании, но вот, видимо, не зря их спрашивают.
Здравствуйте, so5team, Вы писали:
S>самый коллектор в своем деструкторе, если его разрушают до очередного вызова sweep()
Ты прямо как персонаж из human centipede, не унимаешься с деструктором.
Я могу сказать
1) забить на остаток конекшенов в коллекции, ничего не закрывать
2) пойти и дать вызывальщику деструктора до очередного вызова sweep() в табло. Такое копрофильное вредительство решительно невозможно терпеть.
Здравствуйте, Тёмчик, Вы писали:
S>>Тёмчик, тебя до сих пор травма с C++ не отпускает потому, что ты откровенно хреновый C++ник и тебе,
Тё>Когда я был плюсником, приходилось ассенизировать последствия после таких, как ты, глотающих все исключения в цикле.
Тёмчик, внедрение "решений" в виде коллектора коллекторов чего-либо там -- это не ассенизация, это как раз откладывание большущих говн, которые затем превращаются в неподдерживаемые копролиты.
Тё>И кстати, эти глотальщики долго не задерживались.
Еще бы, работать в компаниях где тебе, Тёмчик, доверяют принятие хоть каких-либо технических решений, откровенный путь в никуда. Думающие люди просто все понимали и делали ноги.
Тё>Может быть, в Бабруйске ты первый хакер на деревне, а я работал в более крутых компаниях.
Написяла мышка в море и кричит: "Здесь и моя доля!"
Тё>Судя что до Москвы ты не доехал, может быть, не смог строку развернуть? После откровений про глотания не удивлен.
Москва сама ко мне приехала. Можно сказать в прямом смысле: сперва я здесь на местности принимал участие в создании центра R&D для компании из Москвы, а потом даже немного порулил разработкой в этой же компании, территориально находясь здесь же, а не в Москве. Так что у меня нет повода стесняться своей карьеры и переживать о том, что у кого-то где-то что-то и как-то лучше/длинее/толще.
А вот то, что ты все время пытаешься перевести стрелки в направлении "да вы в своем Бобруйске лаптем щи, тогда как я Австралии, в крупнейших компаниях..." говорит о том, что тебе очень нужно почувствовать себя выше хоть кого-нибудь. Хоть ноунейма из условного Бобруйска.
Здравствуйте, Тёмчик, Вы писали:
Тё>Особо доставляют плюсники конечно, те, кто верует в святаго C++ и шаблоны его, и считает алгоритмы ересью.
Не кури это больше!
S>Да ладно у меня сегодня уволился коллега, S>Рассказаликакие у него были задачки, просто жесть S>Правда и зарплата как я понял 280
ходю я гдето какждые полтора, два года на интервью в гиганты, благо они тут рядом все расположены у нас.
где то месяц полтора готовлюсь и вперед.
сложные задачи мне давали только в гугле.
фэйсбук и амазон средние по сложности — но я забил на подготовку по дизайн-интервью, за что был расстрелян неоднократно со всех сторон
один раз случайно затащили на интервью в макрософт.
так микрософт вообще интервьюировал только по спецухе и никаких реверсов строки и прочих глупостей, но там было недопонимание в личном плане, не был показан достаточно высокий уровень энтузАЗИЗМА, с легким пофигизмом проходил интервью, за что был отказ.
хотя технически все было ок — инсайдеры доложили что дедушка-немец, руководитель проекта хотел видеть больше юношеского задора в глазах
половина успеха это soft skills, а уж остальное кодинг задачек, дизайн и опытЪ.
еще один раз будучи в фэйсбуке я в открытую поржал над чуваком который пытался меня убедить в преимуществах и богоизбранности react native.
он сильно обиделся, для него жабаскрипт это религия. так что тут тоже понятно почему не взяли
так что задачи это не проблема.
а вот не послать в пеший тур за просьбу процитировать Четырнадцать принципов лидерства от самого БЕЗОСА очень тяжело. сектантов не люблю
Здравствуйте, sergii.p, Вы писали:
SP>особенно понравилось SP>
SP>Тут же меня спросили, какова сложность алгоритма — ок, норм, это нужно знать, потому что в реальном программировании мне это потребовалось целых 0 раз.
SP>Реально питон головного мозга. Вроде и программист, но как с другой планеты.
Можно не знать реализации тех или иных структур и алгоритмов, но знать сложность обязан, а если лень знать, распечатываешь и вешаешь перед собой https://i.imgur.com/wKP9etH.png
Здравствуйте, Тёмчик, Вы писали:
Тё>Вот ты, хотя на шаблоны не мастурбируешь, а веришь в константу минимальную, перекрывающую алгоритмическую сложность.
Ох Артёмка, какой же ты иногда забавный в своём упорстве.
Ну да, в теории логарифмическая сложность побивает линейную. Но нас то интересует практика, на конкретных интервалах n, а не стремящегося к бесконечности.
Потому инженерами алгоритмы для решения задачи выбираются из практических соображений этой конкретной задачи.
А вот такие вот теоретики как ты как раз и лепят всё на шаблонах, чтоб на все случаи жизни параметризовалось.
Вот и выходит у них примерно как тут:
Здравствуйте, Тёмчик, Вы писали:
Тё>Да, но можно ведь убить производительность неаккуратной обвязкой. Как у автора статьи — море пафоса и квадратичная сложность на ровном месте. Особо доставляют плюсники конечно, те, кто верует в святаго C++ и шаблоны его, и считает алгоритмы ересью.
У меня на практике было, когда квадратичная сложность по скорости превосходила линейную при обработке картинок: нашлась аппаратная инструкция, которая умела 4 операции делать за один раз. Далее оказалось, что при квадратичном алгоритме идёт последовательное чтение данных из памяти и линейный алгоритм слился по скорости. Оптимизировать код тоже надо уметь, зачастую даёт выигрыш в разы и константа побеждает алгоритм.
Здравствуйте, so5team, Вы писали:
Тё>>Ну это как сказать "нужно съесть миску говна. Нужно."
S>Нет, это как в ситуации: "у тебя в доме прорвало канализацию и нужно убрать говно. Нужно". Поскольку суть не в говне, а в том, что убирать нужно. Нравится это тебе или нет.
Если это говно написал ты, тебе должно быть стыдно. Если же не ты, то ассенизируй. Или уходи из той говноконторы.
S>>>Во-первых, какое отношение проглатывание исключений имеет к пенисометрии на лучшее понимание big-O? Тё>>Какое отношение имеет поедание говна к пониманию bigO?
S>Это у тебя нужно спросить. Ты же приплел пример с проглатыванием исключений в разговор про понимание big-O.
А ты натянул сову на глобус с деструктором.
S>Так что не суть важно что именно ты считаешь говном, вопрос в том, причем оно здесь?
Есть корелляция у программистов между непониманием bigO и генерацией говна. Можно строить классификатор.
S>Ответить сможешь или в очередной раз публично обосрешься?
Я уже ответил в прошлом сообщении. Ты не можешь или не хочешь понять.
S>>>Во-вторых, что Тёмчик предложит делать в деструкторе класса, когда нужно вызвать close() для 100500 объектов connection, а этот close() бросающий? Есть какой-то другой рецепт? Тё>>Сделать какой-то коннекшен коллектор, в деструкторе отдавать этих конекшенов туда. Периодически вызывать к коннекшен коллектора метод sweep, который таки может бросать.
S>Остается только повторить: вот уж, воистину, когда кажется, что Тёмчик достиг дна и падать дальше некуда, он неожиданно начинает копать.
Похоже, что по существу ты обсуждать не готов. Досвидания.
Здравствуйте, so5team, Вы писали:
S>Остается только повторить: вот уж, воистину, когда кажется, что Тёмчик достиг дна и падать дальше некуда, он неожиданно начинает копать.
Здравствуйте, so5team, Вы писали:
S>Только вот исходя из количества генерируемого тобой говна остается вопрос: либо этой корреляции нет, либо ты не понимаешь bigO.
Процитирую себя же: "Но надо ж ещё понимать что именно за этим стоит. А то куча народу дрочит на big-О вприсядку до состояния слепой веры."
Ты покушаешься на его прелесссссссть
Здравствуйте, Тёмчик, Вы писали:
Тё>Может быть, в Бабруйске ты первый хакер на деревне, а я работал в более крутых компаниях. Судя что до Москвы ты не доехал, может быть, не смог строку развернуть? После откровений про глотания не удивлен.
Тут надо бы сказать, что твой оппонет принимал цчастие в качестве докладчика на международных конференциях о С++, на которых лично (вживую и оффлайн) выступали такие люди, как например Александреску, Daveed Vandevoorde и другие, многие из которых члены комитета по стандартизации С++. Так что в этом плане в условном "Бобруйске" всё таки находишься ты.
Здравствуйте, Nuzhny, Вы писали:
N>Ты серьезно?! Сравнить местечковые мииапы с ежегодной международной конференцией, где выступают люди первой величины в профессии?
Местечковые конференции в HFT-й конторе в Сиднее vs международные в Нью-Васюки?
N> Видео может где-то может и лежит, я его воспринимать не могу, предпочитаю лично присутствовать.
Ну так найди именно состима, интересно же посмотреть. Ибо его откровения про его практики кодирования ни в какие ворота, это даже на бангалор код не дотягивает.
Здравствуйте, Тёмчик, Вы писали:
S>>Тёмчик, внедрение "решений" в виде коллектора коллекторов чего-либо там -- это не ассенизация, это как раз откладывание большущих говн, которые затем превращаются в неподдерживаемые копролиты. Тё>Я не предлагал "коллекторов коллекторов", это твои подхалимы что-то там ко ко.
Люди просто за меня довели твою мысль до логического завершения.
Тё>На твой вопрос, как избежать исключение в деструкторе и не заглатывать, я напомнил про давно известный дизайн с коллектором, которому можно отдавать право владения ненужным конекшеном, и который может бросать. Коллектор может быть синглтоном и его не нужно удалять.
Это не дизайн, это даже всерьез обсуждать невозможно.
Тё>Должно быть удивительно, что я объясняю маститому плюснику очевидные и давно известные вещи, но я уже ничему от сиплюсплюсников не удивляюсь. Умные плюсники остались в прошлом, в 1995-2005гг, а теперь какая-то дичь.
Тут уместно задать вопрос "А судьи кто?"
Если у тебя откровенная дурь в башке, то ты даже нормальные вещи будешь видеть как говно. Что, собственно, мы в этом разговоре и наблюдаем.
Тё>Ну какбэ я уже давно заметил, что адекваты в большинстве свалили из C++ в другие языки, в принципе уже и никто в здравом уме не хочет в него идти. Остались такие вот упёртые религиозные фанатики, кто даже не может линукс запустить и делает свои докладики из форточки.
Это сейчас какие-то голоса из твой головы прорвались? Или что это вообще было?
Здравствуйте, AmSpb, Вы писали:
L>>А вот это плохая задача для собеседований. Ибо, к ней нужен весьма специальный подход. И если его не знаешь, то не решишь, скорее всего.
AS>какой специальный подход ? два указателя "быстрый" и "медленный", догнал быстрый указатель медленный значит есть циклы.
Ну в принципе, этот алгоритм не то, чтобы совсем очевидный. Если тебе его не рассказали, сам можешь и не придумать.
Комменты вообще огонь я считаю и реально театр абсурда. Каждый второй сводится к тому, что "я хотел бы в Яндекс, но как только захожу на Литкод, корона нестерпимо давить начинает".
Здравствуйте, CreatorCray, Вы писали:
AS>>Можно не знать реализации тех или иных структур и алгоритмов, но знать сложность обязан, а если лень знать, распечатываешь и вешаешь перед собой CC>Знать за сложность надо, да. Но надо ж ещё понимать что именно за этим стоит. А то куча народу дрочит на big-О вприсядку до состояния слепой веры. CC>А то ж порой бывает и так что алгоритм с линейной сложностью работает быстрее чем с логарифмической, просто потому что цена одного "шага" разная.
Да, понимать тоже стоит, но без деталей, т.к. детали со временем забываются, остается только общее понимание.
Здравствуйте, sergey2b, Вы писали:
S>Да автору не зачёт S>Большая честь задач не сложные
пост же не про задачи сами по себе, а что одну и ту же пластинку ставят раз за разом. такое ощущение что это какие то hunger games заочные, ищут самого выносливого и/или мотиварованного что ли.
Здравствуйте, sergey2b, Вы писали:
S>в принципе задачки нормальные, не чем не хуже реверса отдельных слов в строке S>и поиск цикла в list
S>https://habr.com/ru/post/550088/ S>Собеседование в Яндекс: театр абсурда :/
Я как-то собеседовался в Яндекс (в Минске) лет 6 назад. Причём честно предупредил, что у меня нет высшего образования, только среднее специальное, а остальное доучиваю сам по необходимости.
В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта?
Как бы для своих решений я могу посчитать алгоритмическую сложность. Даже объяснял это с примерами.
Убило то, что на этим вопросом меня мурыжили 45 минут не давая никаких наводящих вопросов, а на все мои рассуждения и попытки найти истину отвечали: это неправильно.
Оказалось, что от меня хотели, чтобы я просто взял предел.
Я конечно всё понимаю и не утверждаю, что это бесполезные знания, но по-моему это уже какой-то бзик, где такие вот вопросы ставят выше умений проектировать архитектуру и знаний языка.
Здравствуйте, Marty, Вы писали:
M>Это всё скорее всего "отсчитывается" библиотеками, которые ты подцепил
Да, но можно ведь убить производительность неаккуратной обвязкой. Как у автора статьи — море пафоса и квадратичная сложность на ровном месте. Особо доставляют плюсники конечно, те, кто верует в святаго C++ и шаблоны его, и считает алгоритмы ересью.
SaZ>>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта? N>Задача некорректна. Константа должна быть в обоих выражениях.
Корректна.
N>Хотя, смысла в такой задаче на собеседовании я не вижу.
Смысл- отсеять таких, кто не видит в bigO смысла.
Здравствуйте, smeeld, Вы писали:
S>Здравствуйте, AmSpb, Вы писали:
S>Мне в своё время приходилсь вытравливать из себя математика, когда ударился в разработку софта. Вот так вот, обрах мышления, который способстовал решению задач из матанализа, сильно мешал писать программный код. Это не только у меня так, судя по тому, какие отзывы о том коде, который пишут математики. Но и образ мышления прогера-практика достаточно далёк от образа мышления математика-теоретика. Выше задачка для математика, а не для разработчика программного кода.
Зачем вытравливать, математика полезна, и математический склад ума вполне пригождается в софтописании.
Здравствуйте, so5team, Вы писали:
Тё>>глотал все исключения в цикле
S>Во-первых, какое отношение проглатывание исключений имеет к пенисометрии на лучшее понимание big-O?
S>Во-вторых, что Тёмчик предложит делать в деструкторе класса, когда нужно вызвать close() для 100500 объектов connection, а этот close() бросающий? Есть какой-то другой рецепт?
Здравствуйте, Тёмчик, Вы писали:
S>>Во-вторых, что Тёмчик предложит делать в деструкторе класса, когда нужно вызвать close() для 100500 объектов connection, а этот close() бросающий? Есть какой-то другой рецепт?
Тё>Не вызывать из деструктора бросающих методов.
Вот уж, воистину, когда кажется, что Тёмчик достиг дна и падать дальше некуда, он неожиданно начинает копать.
Тёмчик, сосредоточься, прочитай внимательно. Если что не понятно, переспроси, я постараюсь объяснить максимально подробно. Но задача максимально простая: в деструкторе нужно вызвать N бросающих исключения методов. Нужно.
А теперь, пожалуйста, ответь на оба поставленных вопроса, а именно:
Во-первых, какое отношение проглатывание исключений имеет к пенисометрии на лучшее понимание big-O?
Во-вторых, что Тёмчик предложит делать в деструкторе класса, когда нужно вызвать close() для 100500 объектов connection, а этот close() бросающий? Есть какой-то другой рецепт?
Здравствуйте, so5team, Вы писали:
S>>>Во-вторых, что Тёмчик предложит делать в деструкторе класса, когда нужно вызвать close() для 100500 объектов connection, а этот close() бросающий? Есть какой-то другой рецепт?
Тё>>Не вызывать из деструктора бросающих методов.
S>Вот уж, воистину, когда кажется, что Тёмчик достиг дна и падать дальше некуда, он неожиданно начинает копать.
Самокритично.
S> в деструкторе нужно вызвать N бросающих исключения методов. Нужно.
Ну это как сказать "нужно съесть миску говна. Нужно."
S>А теперь, пожалуйста, ответь на оба поставленных вопроса, а именно:
S>Во-первых, какое отношение проглатывание исключений имеет к пенисометрии на лучшее понимание big-O?
Какое отношение имеет поедание говна к пониманию bigO?
S>Во-вторых, что Тёмчик предложит делать в деструкторе класса, когда нужно вызвать close() для 100500 объектов connection, а этот close() бросающий? Есть какой-то другой рецепт?
Сделать какой-то коннекшен коллектор, в деструкторе отдавать этих конекшенов туда. Периодически вызывать к коннекшен коллектора метод sweep, который таки может бросать.
Здравствуйте, Тёмчик, Вы писали:
Тё>Ну это как сказать "нужно съесть миску говна. Нужно."
Нет, это как в ситуации: "у тебя в доме прорвало канализацию и нужно убрать говно. Нужно". Поскольку суть не в говне, а в том, что убирать нужно. Нравится это тебе или нет.
S>>Во-первых, какое отношение проглатывание исключений имеет к пенисометрии на лучшее понимание big-O? Тё>Какое отношение имеет поедание говна к пониманию bigO?
Это у тебя нужно спросить. Ты же приплел пример с проглатыванием исключений в разговор про понимание big-O.
Так что не суть важно что именно ты считаешь говном, вопрос в том, причем оно здесь?
Ответить сможешь или в очередной раз публично обосрешься?
S>>Во-вторых, что Тёмчик предложит делать в деструкторе класса, когда нужно вызвать close() для 100500 объектов connection, а этот close() бросающий? Есть какой-то другой рецепт? Тё>Сделать какой-то коннекшен коллектор, в деструкторе отдавать этих конекшенов туда. Периодически вызывать к коннекшен коллектора метод sweep, который таки может бросать.
Остается только повторить: вот уж, воистину, когда кажется, что Тёмчик достиг дна и падать дальше некуда, он неожиданно начинает копать.
S>>Ну вот, чуть какие-то сложности встречаешь и сразу сдриснуть хочешь. Нет, Тёмчик, одних публичных обосратушек недостаточно, ты можешь еще. Расскажи почтенной публике, что будет делать этот самый коллектор в своем деструкторе, если его разрушают до очередного вызова sweep(), но после того, как в него засунули очередной набор коннекшенов?
F>Я, я знаю!! Спросите меня! Надо сделать коллектор коллекторов!!!
Как вариант, но не лучше ли сразу сдриснуть от копрофилов? Или тебя предложением поесть этих французских какашек не напугать?
Здравствуйте, smeeld, Вы писали:
S>Старая тема, когда код, написанный математиком, вызывает батхерд у ремесленников. Выше упоминается код, похожий на математические выкладки.
Ну, я тоже видел код, написанный "математиком", который я бы предпочел выкинуть нафиг. Но, сдается мне, дело было совсем не в том, что автор был математиком, а в том, что он был посредственным разработчиком (не имел нужного опыта и знаний).
Здравствуйте, vsb, Вы писали:
Pzz>>Ну в принципе, этот алгоритм не то, чтобы совсем очевидный. Если тебе его не рассказали, сам можешь и не придумать.
vsb>Его даже Флойд смог придумать. Если ты не уровня Флойда, что ты вообще делаешь в программировании? Может пора метлу осваивать?
Это тот Флойд, которого летом в штатах копы придушили?
Здравствуйте, Nuzhny, Вы писали:
Тё>>Мало ли что докладчики докладывают (часто откровенную хрень), это не ставит докладчика на уровень Александреску.
N>Это рецензируемые конференции как минимум. Это даже круче, чем работа в хорошей конторе чаще всего, потому что там неизвестно чем человек занимался, а тут полная публичность, обсуждение, рецензии со стороны. Более объективный критерий.
Ссылку на видео дашь?
Ходил я на митапы раньше, и что неприятно поразило именно на плюсниковых- 3/4 докладчиков было с позорной форточкой запускали в ней позорную студию. Это не говоря про сами доклады "смотрите, какая прогрессивная фича", а этой фичей уже 20 лет в питоне например пользуются. Сектанты, как они есть.
Здравствуйте, Тёмчик, Вы писали:
Тё>>>Я не предлагал "коллекторов коллекторов", это твои подхалимы что-то там ко ко.
S>>Люди просто за меня довели твою мысль до логического завершения. Тё>Я не говорил этот бред про "коллекторов коллекторов".
Прочитай то, что тебе пишут. Не утверждалось что ты такое предлагал. Говорилось, что это логическое завершение твоей мысли.
Тё>Это на твоей и твоих подхалимов совести.
Ну ладно мне, другим-то ты зачем хамишь?
S>>Это не дизайн, это даже всерьез обсуждать невозможно. Тё>А что дизайн? Вот ты что-то когда-то предложил по дизайну, помимо самолюбования и базарного хамства?
У меня никто и не спрашивал. Ты завел речь про то, что ловить исключения в цикле -- это плохо. Отсюда и возникает вопрос о том, а что делать, например, в деструкторах, когда нужно вызвать N бросающих исключения методов. Вопрос к тебе. И ты ответив на него, окрасил себя в те цвета, в которые окрасил себя. В очередной раз.
Ко мне вопросов не было.
Тё>Глотать все исключения- это ненормально и никогда не было нормальным. Ни В C++, ни в Java.
Главное верить.
Тё>Наблюдал минимум на 2 митапах плюсных в 2016-17гг. Что характерно, на митапах кложурных все с линуксом.
Здравствуйте, CreatorCray, Вы писали:
Тё>>Но как можно примером функции с мультистратегией защищать безграмотность чуваков, которые везде лепят пузырёк и на вопрос "какая в этом написанном тобой коде сложность" говорят "наверное медленно? можно быстрее, да?" CC>Я что то не помню чтоб кто либо кроме тебя про таких тут хоть что то говорил.
Такие приходили собеседоваться, включая и онлайн из России. Судя по тому, как у некоторых участников раскалён коллектор на bigO, как они пытаются доказать, что bigO не на первом месте по важности, делаю выводы.
Здравствуйте, so5team, Вы писали:
S>>>Люди просто за меня довели твою мысль до логического завершения. Тё>>Я не говорил этот бред про "коллекторов коллекторов".
S>Прочитай то, что тебе пишут. Не утверждалось что ты такое предлагал. Говорилось, что это логическое завершение твоей мысли.
Необязательно. Я уже указал, почему вызывать деструктор у непустого коллектора- натягивание совы на глобус.
Тё>>Это на твоей и твоих подхалимов совести.
S>Ну ладно мне, другим-то ты зачем хамишь?
Посмотри на твои посты. Там же оскорбления на уровне базарных продавцов. И ты после этого называешь "хамишь" за оценку поведения твоих подпевал?
S>>>Это не дизайн, это даже всерьез обсуждать невозможно. Тё>>А что дизайн? Вот ты что-то когда-то предложил по дизайну, помимо самолюбования и базарного хамства?
S>У меня никто и не спрашивал.
Я сейчас спросил. Сначала ты попросил дизайн, как избежать ловить исключения в цикле в деструкторе- вот тебе дизайн. Так ты вместо благодарности или конструктивности назвал это
S>Это не дизайн, это даже всерьез обсуждать невозможно.
Ну так аргументируй, конструктивно. Ведь проблему исключений в деструкторе этот дизайн решает, Ч.Т.Д.
S> Ты завел речь про то, что ловить исключения в цикле -- это плохо. Отсюда и возникает вопрос о том, а что делать, например, в деструкторах, когда нужно вызвать N бросающих исключения методов. Вопрос к тебе. И ты ответив на него, окрасил себя в те цвета, в которые окрасил себя. В очередной раз.
А не нужно вызывать бросающие методы в деструкторах, и один из вариантов, как этого избежать, я предлржил по твоей же просьбе.
S>Ко мне вопросов не было.
К тебе вопрос- конструктивно аргументируй критику предложенного дизайна.
Тё>>Глотать все исключения- это ненормально и никогда не было нормальным. Ни В C++, ни в Java.
S>Главное верить.
Мне тут коллега предлагает
[9/4, 10:12] : Catch all это путь к стрессу, согласен
[9/4, 10:13] : На пипку садить можно за кэтч ол
Тё>>Наблюдал минимум на 2 митапах плюсных в 2016-17гг. Что характерно, на митапах кложурных все с линуксом.
S>Понятно, голоса.
Ага, голоса. На 100 участников из самых крутых плюсных контор.
Здравствуйте, Тёмчик, Вы писали:
S>>Прочитай то, что тебе пишут. Не утверждалось что ты такое предлагал. Говорилось, что это логическое завершение твоей мысли. Тё>Необязательно. Я уже указал, почему вызывать деструктор у непустого коллектора- натягивание совы на глобус.
Нет, не указал. Вызов деструктора -- неотъемлемая часть жизни объекта в C++, соответственно, деструктор должен корректно отработать при всех корректных инвариантах объекта. В том числе и когда список не пуст. Это же корректный инвариант.
А вот то, что ты пытаешься изобразить картину, когда непустой список -- это корректный инвариант в обычной жизни, но вдруг он становится некорректным непосредственно перед вызовом деструктора, говорит о том, что ты не умеешь решать проблемы. И вместо поиска общего решения предлагаешь набор откровенных костылей.
И да, убеждать я тебя ни в чем не собираюсь, да и невозможно это, как показывает практика.
S>>Ну ладно мне, другим-то ты зачем хамишь? Тё>Посмотри на твои посты. Там же оскорбления на уровне базарных продавцов. И ты после этого называешь "хамишь" за оценку поведения твоих подпевал?
Если тебе кажется, что я (именно я) тебе хамлю, то мне ты можешь отвечать той же монетой. Мне фиолетово. Но вот когда ты начинаешь других людей, никак не аффилированных со мной, обзывать якобы из-за моего хамства в твой адрес, то это уже ни в какие ворота.
Из тех, кто отметился в этой ветке я общался несколько раз по почте только с ут.тов.Nuzhny. И то мы с ним в реальной жизни не знакомы и, наверное, никогда друг друга в офлайне и не видели.
Навесить на этих людей ярлык "твои подпевала" -- это ты, Тёмчик, со зла.
S>>У меня никто и не спрашивал. Тё>Я сейчас спросил. Сначала ты попросил дизайн, как избежать ловить исключения в цикле в деструкторе- вот тебе дизайн. Так ты вместо благодарности или конструктивности назвал это Тё>
S>>Это не дизайн, это даже всерьез обсуждать невозможно.
Тё>Ну так аргументируй, конструктивно.
Аргументирование, по самым грубым прикидкам, потребует мини-лекции минут на 15-20. Такую лекцию я мог бы провести джуну из своей команды. Один, максимум, два раза. Потом бы джун пошел искать другую работу. Мог бы провести ее заказчику, после чего бы обязательно включил бы это время в калькуляцию трудозатрат.
Выписывать же это все текстом на форуме -- дело полутора-двух часов, не меньше. Чего, естественно, делать не буду.
Так что проссыте, но учить альтернативно одаренных на форуме за бесплатно... Вот уж дудки. Твои работодатели должны страдать, разу уж взяли тебя на работу и доверяют тебе собеседовать соискателей.
Тё>Ведь проблему исключений в деструкторе этот дизайн решает, Ч.Т.Д.
Решение проблемы -- это не тогда когда более серьезные проблемы возникают в других местах.
S>>Главное верить. Тё>Мне тут коллега предлагает Тё>
Тё>[9/4, 10:12] : Catch all это путь к стрессу, согласен
Тё>[9/4, 10:13] : На пипку садить можно за кэтч ол
Так если ты этого коллегу собеседовал и он попал на работу по твоей рекомендации, то и не удивительно. Тем более, что тут явно нет обсуждения контекста, в котором catch all применяется. И если твой коллега не представляет себе контекст, в котором catch all использовали, то столь категоричные утверждения многое говорит о его квалификации.
S>>Понятно, голоса. Тё>Ага, голоса. На 100 участников из самых крутых плюсных контор.
Я сейчас общаюсь не с теми участниками, а с тобой. И мне приходится расшифровать выплески потоков сознания от голосов из твоей головы. Так что претензия не к участникам каких-то митапов, а к твоим рассказам об этих самых митапах. Бессмысленным и бессвязным.
Здравствуйте, sergii.p, Вы писали:
SP>особенно понравилось SP>
SP>Тут же меня спросили, какова сложность алгоритма — ок, норм, это нужно знать, потому что в реальном программировании мне это потребовалось целых 0 раз.
SP>Реально питон головного мозга. Вроде и программист, но как с другой планеты.
Господа, ну зачем сразу "питон'? Вы вообще в курсе, что на питоне отсчитывают всякие там корелляции и финансы- там сложность — первое требование.
А отквоченный текст- это я считаю, типичный руссо-укро-беларусский программист. Да. 99% таких чуваков можно опознать ещё по упоминаниям мифических индусов, за которыми они разгребают.
Здравствуйте, CreatorCray, Вы писали:
Тё>>Особо доставляют плюсники конечно, те, кто верует в святаго C++ и шаблоны его, и считает алгоритмы ересью. CC> CC>Не кури это больше!
Вот ты, хотя на шаблоны не мастурбируешь, а веришь в константу минимальную, перекрывающую алгоритмическую сложность.
Здравствуйте, namespace, Вы писали:
SaZ>>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта? N>Задача некорректна. Константа должна быть в обоих выражениях. Иначе результат сравнения зависит от ее размера. При С бесконечно большом, условие не выполняется.
C — константа, n — переменная. Какую бы огромную С ты заранее ни взял, всегда можно найти такое n, где C*n < n*n. Собственно при n = С+1 оно уже так.
Некорректность тут разве что только в том, что человек сразу сказал что в универе это не проходил, понимает так, как понимает и 45 минут про это мучать просто бессмысленно. Или приняли бы его объяснения "на пальцах" или уж засчитали минус да успокоились.
Здравствуйте, AmSpb, Вы писали:
AS>Ну если хотели аналитическое обоснование, то тут тоже довольно просто: AS>1. O(С*n) < O(n^2) AS>2. O(С*n) / O(n^2) < 1 AS>3. С/n < 1 для всех C < n AS>4. lim C/n -> 0 при n -> oo
Мне в своё время приходилсь вытравливать из себя математика, когда ударился в разработку софта. Вот так вот, обрах мышления, который способстовал решению задач из матанализа, сильно мешал писать программный код. Это не только у меня так, судя по тому, какие отзывы о том коде, который пишут математики. Но и образ мышления прогера-практика достаточно далёк от образа мышления математика-теоретика. Выше задачка для математика, а не для разработчика программного кода.
Здравствуйте, AmSpb, Вы писали:
AS>Зачем вытравливать, математика полезна, и математический склад ума вполне пригождается в софтописании.
Да вот нифига. С 10-ти лет решал задачки по математике, любил это дело, особенно матанализ. Но когда стал пытаться писать код, то стало понятно, что думать нужно по-другому. При написании кода режим мышления должен быть другим, больше писательским, чем математическим. Иначе код получается похожим на математические выкладки.
Здравствуйте, SaZ, Вы писали:
SaZ>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта?
Потому, что при достаточно большом n ("n, стремящемся к бесконечности"), n^2 завсегда обгонит C*n ("всегда найдется такой n, что для любого числа, болешего или равного ему...").
Тё>>Вот ты, хотя на шаблоны не мастурбируешь, а веришь в константу минимальную, перекрывающую алгоритмическую сложность. CC>Ох Артёмка, какой же ты иногда забавный в своём упорстве.
CC>Ну да, в теории логарифмическая сложность побивает линейную. Но нас то интересует практика, на конкретных интервалах n, а не стремящегося к бесконечности.
Если у тебя чисто конкретно 10 элементов, пузырёк тоже сойдёт.
CC>Потому инженерами алгоритмы для решения задачи выбираются из практических соображений этой конкретной задачи.
Ога, главное, чтоб как всегда не оказалось- на 10 элементах у программиста с овер 6000 ядер и 100555гб памяти никогда не торзомозило, и тут в продакшене опять.
CC>А вот такие вот теоретики как ты как раз и лепят всё на шаблонах, чтоб на все случаи жизни параметризовалось.
Я не пишу на плюсах уже весьма давно. А так да, всё параметризуется.
CC>Вот и выходит у них примерно как тут:
CC>Image: ml52dfe504.jpg
Самокритично.
Здравствуйте, smeeld, Вы писали:
S>Да вот нифига. С 10-ти лет решал задачки по математике, любил это дело, особенно матанализ. Но когда стал пытаться писать код, то стало понятно, что думать нужно по-другому. При написании кода режим мышления должен быть другим, больше писательским, чем математическим. Иначе код получается похожим на математические выкладки.
Не понятно, что такое писательский и математический режимы мышления. Лично мне математическое образование никогда не мешало писать код. И ничего из себя не приходилось вытравливать. Наоборот, иногда математика помогает, когда нужно какую-нибудь оценку сделать или доказать корректность алгоритма.
Здравствуйте, Тёмчик, Вы писали:
Тё>Согласен. Но это случайность же- могло также попасть инструкция и последовательное чтение на линейный алгоритм, и срыв кеша- на квадратичный. Cache locality это такая штука- если чел на ровном месте городит квадратичную, от куда ему знать про cache locality.
Здравствуйте, fmiracle, Вы писали:
F>C — константа, n — переменная. Какую бы огромную С ты заранее ни взял, всегда можно найти такое n, где C*n < n*n. Собственно при n = С+1 оно уже так.
Это в математике, в программировании n таки ограничено.
Здравствуйте, Тёмчик, Вы писали:
Тё>Я могу сказать Тё>1) забить на остаток конекшенов в коллекции, ничего не закрывать Тё>2) пойти и дать вызывальщику деструктора до очередного вызова sweep() в табло. Такое копрофильное вредительство решительно невозможно терпеть.
Тёмчик, тебя до сих пор травма с C++ не отпускает потому, что ты откровенно хреновый C++ник и тебе, видимо, слишком часто на это указывали. Причем, судя по твоим "предложениям", указывали совершенно по делу. И мне даже страшно представить, насколько часто, если ты работал с людьми хоть чуть-чуть толковее, чем я (а их более чем достаточно).
L>Не понятно, что такое писательский и математический режимы мышления.
Старая тема, когда код, написанный математиком, вызывает батхерд у ремесленников. Выше упоминается код, похожий на математические выкладки.
>Лично мне математическое образование никогда не мешало писать код. Наоборот, иногда математика помогает, когда нужно какую-нибудь оценку сделать или доказать корректность алгоритма.
Вот именно, что иногда. Это на стадии формирования модели, когда вся система у тебя в голове в виде мыслей и соображений, которые иногда даже можно кратко выразить математически. Но когда начинаешь описывать это языком программирования, то приходится переставать думать как математик, нужно включать именно писателя.
Здравствуйте, so5team, Вы писали:
S>>>Тёмчик, тебя до сих пор травма с C++ не отпускает потому, что ты откровенно хреновый C++ник и тебе,
Тё>>Когда я был плюсником, приходилось ассенизировать последствия после таких, как ты, глотающих все исключения в цикле.
S>Тёмчик, внедрение "решений" в виде коллектора коллекторов чего-либо там -- это не ассенизация, это как раз откладывание большущих говн, которые затем превращаются в неподдерживаемые копролиты.
Я не предлагал "коллекторов коллекторов", это твои подхалимы что-то там ко ко. На твой вопрос, как избежать исключение в деструкторе и не заглатывать, я напомнил про давно известный дизайн с коллектором, которому можно отдавать право владения ненужным конекшеном, и который может бросать. Коллектор может быть синглтоном и его не нужно удалять. Должно быть удивительно, что я объясняю маститому плюснику очевидные и давно известные вещи, но я уже ничему от сиплюсплюсников не удивляюсь. Умные плюсники остались в прошлом, в 1995-2005гг, а теперь какая-то дичь.
Тё>>И кстати, эти глотальщики долго не задерживались.
S>Еще бы, работать в компаниях где тебе, Тёмчик, доверяют принятие хоть каких-либо технических решений, откровенный путь в никуда. Думающие люди просто все понимали и делали ноги.
Да наздоровье, ветерок в спину.
Тё>>Может быть, в Бабруйске ты первый хакер на деревне, а я работал в более крутых компаниях.
S>Написяла мышка в море и кричит: "Здесь и моя доля!"
Тё>>Судя что до Москвы ты не доехал, может быть, не смог строку развернуть? После откровений про глотания не удивлен.
S>Москва сама ко мне приехала. Можно сказать в прямом смысле: сперва я здесь на местности принимал участие в создании центра R&D для компании из Москвы, а потом даже немного порулил разработкой в этой же компании, территориально находясь здесь же, а не в Москве. Так что у меня нет повода стесняться своей карьеры и переживать о том, что у кого-то где-то что-то и как-то лучше/длинее/толще.
Ну какбэ я уже давно заметил, что адекваты в большинстве свалили из C++ в другие языки, в принципе уже и никто в здравом уме не хочет в него идти. Остались такие вот упёртые религиозные фанатики, кто даже не может линукс запустить и делает свои докладики из форточки.
S>А вот то, что ты все время пытаешься перевести стрелки в направлении "да вы в своем Бобруйске лаптем щи, тогда как я Австралии, в крупнейших компаниях..." говорит о том, что тебе очень нужно почувствовать себя выше хоть кого-нибудь. Хоть ноунейма из условного Бобруйска.
Я ещё до Австралии начал миграцию с плюсов на жаву и с форточки на линух, почти год последний в Москве полностью конвертировался на жаву.
Здравствуйте, Nuzhny, Вы писали:
N>Тут надо бы сказать, что твой оппонет принимал цчастие в качестве докладчика на международных конференциях о С++
Мало ли что докладчики докладывают (часто откровенную хрень), это не ставит докладчика на уровень Александреску.
Здравствуйте, Тёмчик, Вы писали:
Тё>Но как можно примером функции с мультистратегией защищать безграмотность чуваков, которые везде лепят пузырёк и на вопрос "какая в этом написанном тобой коде сложность" говорят "наверное медленно? можно быстрее, да?"
Я что то не помню чтоб кто либо кроме тебя про таких тут хоть что то говорил.
Здравствуйте, Sharov, Вы писали:
S>если у нас будет в 100(1000,10000 и т.д.) раз больше элементов, то мы точно сможем сказать, что log(n) быстрее.
Точно можно сказать только померяв. Тем практика от теории и отличается, что на практике есть туча "движущихся частей" которые на первый взгляд не видны пока не посмотришь профайлером и не станешь разбираться что за фигня происходит.
S>В любом случае, если про это спрашивают на общих основаниях, то явно имеется в виду понимание сложности,
С этим никто не спорит. Речь была про то, что мало просто знать теорию, надо ещё иметь понимание нюансов, отсутствующих в этой теории + практику применения, чтобы всё это эффективно применять. Кроме того в сложных алгоритмах стоимость шага (та самая С) нифига не константа, а состоит из супа других подалгоритмов, так что сравнение реальной производительности "на бумаге" получается ещё веселее.
Здравствуйте, Nuzhny, Вы писали:
Тё>>Мало ли что докладчики докладывают (часто откровенную хрень), это не ставит докладчика на уровень Александреску.
N>Это рецензируемые конференции как минимум. Это даже круче, чем работа в хорошей конторе чаще всего, потому что там неизвестно чем человек занимался, а тут полная публичность, обсуждение, рецензии со стороны. Более объективный критерий.
Мне эти конференции напоминают "Голубой огонёк"... во всех смыслах.
Здравствуйте, sergey2b, Вы писали:
S>в принципе задачки нормальные, не чем не хуже реверса отдельных слов в строке
Лучше, в основном. Реверс строки или слов в строке — это уже заезженная пластинка.
S>и поиск цикла в list
А вот это плохая задача для собеседований. Ибо, к ней нужен весьма специальный подход. И если его не знаешь, то не решишь, скорее всего.
S>https://habr.com/ru/post/550088/ S>Собеседование в Яндекс: театр абсурда :/
Скорее там "питон головного мозга" у автора текста.
Здравствуйте, Pzz, Вы писали:
Pzz>А ты сможешь решить такую задачу: есть массив, он разделен на две, возможно неравные, части (0...N, N+1...M), надо переставить эти две части местами? Pzz>[AAAA][BBBBB] -> [BBBBB][AAAA]
Переворачиваем сначала весь массив, а потом переворачиваем каждую часть.
Переворачиваем = переставляем в обратном порядке. Т.е. меняем первый элемент с последним, второй с предпоследним и т.д.
Здравствуйте, AmSpb, Вы писали:
AS>какой специальный подход ? два указателя "быстрый" и "медленный", догнал быстрый указатель медленный значит есть циклы.
Это и есть специальный подход. В других задачах и в реальной жизни он не встречается, практически.
Наличие цикла, кстати, можно и без этого определить, как и его длину. А вот его начало без этого приема уже определить проблематично.
AS>проще через хэш-таблицу решить, но обычно говорят, что нельзя её использовать.
Логично, ибо это O(N) по памяти против O(1) у "зайца и черепахи".
Здравствуйте, sergii.p, Вы писали:
C>>На самом деле задачки-то лёгкие. Я открыл статью в надежде найти очередной снобизм олимпиадников восьмидесятого уровня, а оказалось, что автор даже подумать не хочет, а сразу пишет первое, что пришло в голову (не очень-то читаемое). Я сам противник проверки книжных знаний на собеседовании, но вот, видимо, не зря их спрашивают.
SP>особенно понравилось SP>
SP>Тут же меня спросили, какова сложность алгоритма — ок, норм, это нужно знать, потому что в реальном программировании мне это потребовалось целых 0 раз.
SP>Реально питон головного мозга. Вроде и программист, но как с другой планеты.
Ну так эффект Даннинга-Крюгера и систематическая ошибка выжившего.
Здравствуйте, Буравчик, Вы писали:
Pzz>>А ты сможешь решить такую задачу: есть массив, он разделен на две, возможно неравные, части (0...N, N+1...M), надо переставить эти две части местами? Pzz>>[AAAA][BBBBB] -> [BBBBB][AAAA]
Б>Переворачиваем сначала весь массив, а потом переворачиваем каждую часть. Б>Переворачиваем = переставляем в обратном порядке. Т.е. меняем первый элемент с последним, второй с предпоследним и т.д.
Мне когда в реальной жизни понадобилось, я сделал рекурсивно: выбираем ту "половину", которая поменьше, и меняем ее местами с соседней с ней частью такого же размера. Потом во второй половине рекурсивно меняем ту часть, которую мы только что туда записали, и оставшуюся.
[AAAA][BBBBB] -> [BBBB][AAAA][B] -> [BBBB][BAAAA]
Про тройной переворот я не знал/не догадался. Но рекурсивный вариант вроде как делает меньше обращений к памяти (на каждом шаге одна из частей массива оказывается уже на своем окончательном месте).
Здравствуйте, SaZ, Вы писали:
SaZ>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта? SaZ>Как бы для своих решений я могу посчитать алгоритмическую сложность. Даже объяснял это с примерами. SaZ>Убило то, что на этим вопросом меня мурыжили 45 минут не давая никаких наводящих вопросов, а на все мои рассуждения и попытки найти истину отвечали: это неправильно. SaZ>Оказалось, что от меня хотели, чтобы я просто взял предел.
А причем тут предел ?
Можно график начертить, и увидеть, что квадратичная фунция растет быстрее линейной, и при n стремящимся в бесконечность, значение C можно принять за 1, т.к. это константа, т.е. она не зависит от n
Здравствуйте, Тёмчик, Вы писали:
Тё>Господа, ну зачем сразу "питон'? Вы вообще в курсе, что на питоне отсчитывают всякие там корелляции и финансы- там сложность — первое требование.
Это всё скорее всего "отсчитывается" библиотеками, которые ты подцепил
Здравствуйте, AmSpb, Вы писали:
SaZ>>Рисовал график. От меня требовали именно теоретическое обоснование.
AS>Наверное аналитическое обоснование. Ту же производную можно обосновать геометрически, а можно аналитически, чисто через формулы. AS>Ну если хотели аналитическое обоснование, то тут тоже довольно просто: AS>1. O(С*n) < O(n^2) AS>2. O(С*n) / O(n^2) < 1 AS>3. С/n < 1 для всех C < n AS>4. lim C/n -> 0 при n -> oo
Да, мне это как раз и объяснили. Просто до собеса я даже не задавался такими вопросами. Повторюсь — я практически не знаю высшей математики (минимально, векторную алгебру, тригонометрию для геймдева).
По факту меня не взяли, но я и не расстроился. Сейчас всё хорошо и в профессиональном и в карьерном плане.
Здравствуйте, Mr.Delphist, Вы писали:
MD>Здравствуйте, SaZ, Вы писали:
SaZ>>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта?
MD>1) Графически: рисуем графики функций y = Cx и y = x^2, показываем что первый растёт медленнее. MD>2) Вычитаем функции друг из друга и получаем y = x^2 — Cx, показываем что на правой полуплоскости это возрастающая функция (если уж очень прикопались, через взятие производной y = 2x)
Здравствуйте, σ, Вы писали:
aik>>Ну и какой смысл спрашивать вот этот вот кодинг раз за разом? Он же точно не будет целыми днями только этим и заниматься σ>Поэтому нужно спрашивать архитектуру высоконагруженного приложения! Ведь программисты точно целыми днями только этим и занимаются. По 3 высоконагруженных приложения в час выпекают в среднем.
где то разворачивают строки за деньги? и прочая олимпиада без остановки, со своевременной оплатой? что за компания? искренне любопытно.
Здравствуйте, Nuzhny, Вы писали:
N>У меня на практике было, когда квадратичная сложность по скорости превосходила линейную при обработке картинок: нашлась аппаратная инструкция, которая умела 4 операции делать за один раз. Далее оказалось, что при квадратичном алгоритме идёт последовательное чтение данных из памяти и линейный алгоритм слился по скорости. Оптимизировать код тоже надо уметь, зачастую даёт выигрыш в разы и константа побеждает алгоритм.
Согласен. Но это случайность же- могло также попасть инструкция и последовательное чтение на линейный алгоритм, и срыв кеша- на квадратичный. Cache locality это такая штука- если чел на ровном месте городит квадратичную, от куда ему знать про cache locality.
Здравствуйте, CreatorCray, Вы писали:
Тё>>Согласен. Но это случайность же- могло также попасть инструкция и последовательное чтение на линейный алгоритм, и срыв кеша- на квадратичный. Cache locality это такая штука- если чел на ровном месте городит квадратичную, от куда ему знать про cache locality.
CC> CC>Не юли, Артёмка.
Мы не знаем, что там на самом деле было. А вот примеров, когда чувак с бекграундом в C++ , обращался в цикле к элементам связного списка по индексу, или глотал все исключения в цикле, у меня есть дюжина. Верующие в быстроту C++, они такие.
Здравствуйте, Тёмчик, Вы писали:
S>>Нет, это как в ситуации: "у тебя в доме прорвало канализацию и нужно убрать говно. Нужно". Поскольку суть не в говне, а в том, что убирать нужно. Нравится это тебе или нет. Тё>Если это говно написал ты, тебе должно быть стыдно. Если же не ты, то ассенизируй. Или уходи из той говноконторы.
Еще раз, для тебя персонально: есть случаи, когда просто нужно. Но ты, видимо, настолько ссущийся товарищ, что сразу же сдриснешь в другую контору как только тебе придется столкнуться с чужим кодом.
S>>Это у тебя нужно спросить. Ты же приплел пример с проглатыванием исключений в разговор про понимание big-O. Тё>А ты натянул сову на глобус с деструктором.
Аргумент из категории "а у вас негров линчуют". Ну, Ok.
S>>Так что не суть важно что именно ты считаешь говном, вопрос в том, причем оно здесь? Тё>Есть корелляция у программистов между непониманием bigO и генерацией говна. Можно строить классификатор.
Понятно.
Только вот исходя из количества генерируемого тобой говна остается вопрос: либо этой корреляции нет, либо ты не понимаешь bigO.
S>>Ответить сможешь или в очередной раз публично обосрешься? Тё>Я уже ответил в прошлом сообщении.
Тебе показалось.
S>>>>Во-вторых, что Тёмчик предложит делать в деструкторе класса, когда нужно вызвать close() для 100500 объектов connection, а этот close() бросающий? Есть какой-то другой рецепт? Тё>>>Сделать какой-то коннекшен коллектор, в деструкторе отдавать этих конекшенов туда. Периодически вызывать к коннекшен коллектора метод sweep, который таки может бросать.
S>>Остается только повторить: вот уж, воистину, когда кажется, что Тёмчик достиг дна и падать дальше некуда, он неожиданно начинает копать. Тё>Похоже, что по существу ты обсуждать не готов. Досвидания.
Ну вот, чуть какие-то сложности встречаешь и сразу сдриснуть хочешь. Нет, Тёмчик, одних публичных обосратушек недостаточно, ты можешь еще. Расскажи почтенной публике, что будет делать этот самый коллектор в своем деструкторе, если его разрушают до очередного вызова sweep(), но после того, как в него засунули очередной набор коннекшенов?
Здравствуйте, CreatorCray, Вы писали:
S>>Только вот исходя из количества генерируемого тобой говна остается вопрос: либо этой корреляции нет, либо ты не понимаешь bigO. CC>Процитирую себя же: "Но надо ж ещё понимать что именно за этим стоит. А то куча народу дрочит на big-О вприсядку до состояния слепой веры." CC>Ты покушаешься на его прелесссссссть
Так что стоит, кроме временной сложности от кол-ва данных?
Здравствуйте, Тёмчик, Вы писали:
Тё>Мало ли что докладчики докладывают (часто откровенную хрень), это не ставит докладчика на уровень Александреску.
Это рецензируемые конференции как минимум. Это даже круче, чем работа в хорошей конторе чаще всего, потому что там неизвестно чем человек занимался, а тут полная публичность, обсуждение, рецензии со стороны. Более объективный критерий.
Здравствуйте, so5team, Вы писали:
S>>>Тёмчик, внедрение "решений" в виде коллектора коллекторов чего-либо там -- это не ассенизация, это как раз откладывание большущих говн, которые затем превращаются в неподдерживаемые копролиты. Тё>>Я не предлагал "коллекторов коллекторов", это твои подхалимы что-то там ко ко.
S>Люди просто за меня довели твою мысль до логического завершения.
Я не говорил этот бред про "коллекторов коллекторов". Это на твоей и твоих подхалимов совести.
Тё>>На твой вопрос, как избежать исключение в деструкторе и не заглатывать, я напомнил про давно известный дизайн с коллектором, которому можно отдавать право владения ненужным конекшеном, и который может бросать. Коллектор может быть синглтоном и его не нужно удалять.
S>Это не дизайн, это даже всерьез обсуждать невозможно.
А что дизайн? Вот ты что-то когда-то предложил по дизайну, помимо самолюбования и базарного хамства? У тебя коллектор пригорает, что в яндекс не берут, ну очевидно, в яндексе не нужны такие копрокодофилы, и яндексовские задачки на алгоритмы позволяют держать таких вот глотальшиков исключений подальше.
Тё>>Должно быть удивительно, что я объясняю маститому плюснику очевидные и давно известные вещи, но я уже ничему от сиплюсплюсников не удивляюсь. Умные плюсники остались в прошлом, в 1995-2005гг, а теперь какая-то дичь.
S>Тут уместно задать вопрос "А судьи кто?" S>Если у тебя откровенная дурь в башке, то ты даже нормальные вещи будешь видеть как говно. Что, собственно, мы в этом разговоре и наблюдаем.
Глотать все исключения- это ненормально и никогда не было нормальным. Ни В C++, ни в Java.
Тё>>Ну какбэ я уже давно заметил, что адекваты в большинстве свалили из C++ в другие языки, в принципе уже и никто в здравом уме не хочет в него идти. Остались такие вот упёртые религиозные фанатики, кто даже не может линукс запустить и делает свои докладики из форточки.
S>Это сейчас какие-то голоса из твой головы прорвались? Или что это вообще было?
Наблюдал минимум на 2 митапах плюсных в 2016-17гг. Что характерно, на митапах кложурных все с линуксом.
Здравствуйте, Sharov, Вы писали:
S>Так что стоит, кроме временной сложности от кол-ва данных?
Стоимость итерации алгоритма. В итоге получается что в реальности на реальных данных O(n) может быть быстрее чем O(log n). При n -> inf есессна log n выиграет, но данные то у нас конечны.
Здравствуйте, Nuzhny, Вы писали:
N>Ты серьезно?! Сравнить местечковые мииапы с ежегодной международной конференцией, где выступают люди первой величины в профессии?
Просто держи в памяти что он — wannabe позёр, причём во всём. Тонна вопросов просто сразу отпадёт.
Здравствуйте, CreatorCray, Вы писали:
S>>Так что стоит, кроме временной сложности от кол-ва данных? CC>Стоимость итерации алгоритма. В итоге получается что в реальности на реальных данных O(n) может быть быстрее чем O(log n). При n -> inf есессна log n выиграет, но данные то у нас конечны.
А есть реальные примеры с объяснением почему? Ибо суть O-нотации как раз в том, что мы предполагаем n очень большим, т.е.
n -> inf, соотв. любой константой можно пренебречь.
Здравствуйте, Sharov, Вы писали:
S>А есть реальные примеры с объяснением почему? Ибо суть O-нотации как раз в том, что мы предполагаем n очень большим, т.е. S>n -> inf, соотв. любой константой можно пренебречь.
Типа, реальная жизнь сложнее и разнообразней. Тот же std::sort скрывает за собой не какой-то определённый алгоритм сортировки, а несколько в зависимости от длины последовательности. Сложность сложностью, а на практике надо не идеально, но быстро в среднем всегда.
Далее можно посмотреть на упорядоченный словарь, который в С++ представлен в виде std::map. Для него есть альтернатива в бусте (и никак не попадёт в стандарт) flat_map, который совсем не дерево уже, а больше std::vector, очень быстрый на маленьких размерах данных при редкой вставке и частом поиске. И даже быстрее хэш-таблицы при некоторых не сильно больших объёмах. То есть надо отталкиваться от сценария использования, надо знать константы, надо смотреть по факту, а не по O-нотации.
Здравствуйте, Sharov, Вы писали:
CC>>Стоимость итерации алгоритма. В итоге получается что в реальности на реальных данных O(n) может быть быстрее чем O(log n). При n -> inf есессна log n выиграет, но данные то у нас конечны. S>А есть реальные примеры с объяснением почему? Ибо суть O-нотации как раз в том, что мы предполагаем n очень большим, т.е. S>n -> inf, соотв. любой константой можно пренебречь.
Ну это в математической теории. А на практике при создании информационных систем ты никогда не работаешь с бесконечностями, а есть какие-то ограничения этого n в конкретной решаемой задаче. И их стоит учитывать. А соотношение констант в двух разных агоритмах может быть огромным. И когда n по факту является ограниченным, величина C вполне может оказаться важным фактором.
Здравствуйте, Nuzhny, Вы писали:
N>Типа, реальная жизнь сложнее и разнообразней. Тот же std::sort скрывает за собой не какой-то определённый алгоритм сортировки, а несколько в зависимости от длины последовательности. Сложность сложностью, а на практике
Здравствуйте, Nuzhny, Вы писали:
Тё>>Но это никак не противоречит bigO
N>Конечно нет, это лишь показывает на его место. Реальные программы примерно так и выглядят (очень грубо): N>
N>И часто оказывается, что the_best_bigO_alg вообще не используется.
Т.е. авторы этой функции заморочились с балансировкой константы и количества элементов. А ещё такое понятие как сложность worst case, в среднем, best case и amortized. Всё это про bigO. Но как можно примером функции с мультистратегией защищать безграмотность чуваков, которые везде лепят пузырёк и на вопрос "какая в этом написанном тобой коде сложность" говорят "наверное медленно? можно быстрее, да?"
Здравствуйте, Sharov, Вы писали:
S>>>А есть реальные примеры с объяснением почему? CC>>Например потому что cache locality обеспечивает существенный прирост алгоритмов с линейным доступом.
S>А как это влияет на O(log(n)) vs O(n)? Типа при O(n) locality будет лучше? Почему также нельзя сделать для O(log(n))?
Хорошо если можно. Тут просто речь о том, что на практике вполне можно столкнуться с тем, что один алгоритм может иметь лучшую алгоритмическую сложность, если брать ее в чистой теории, но перебирать данные так, что они, например, хуже ложатся на кэш процессора, а другой алгоритм имеет худшую алгоритмическую сложность, но зато отлично ложится на все кэши и потому при весьма большом диапазоне n работает гораздо быстрее первого алгоритма.
При каком-то n первый алгоритм все же окажется лучше, но если на практике у тебя таких n не будет, то более предпочтительным внезапно оказывается второй алгоритм.
Здравствуйте, fmiracle, Вы писали:
F>Хорошо если можно. Тут просто речь о том, что на практике вполне можно столкнуться с тем, что один алгоритм может иметь лучшую алгоритмическую сложность, если брать ее в чистой теории, но перебирать данные так, что они, например, хуже ложатся на кэш процессора, а другой алгоритм имеет худшую алгоритмическую сложность, но зато отлично ложится на все кэши и потому при весьма большом диапазоне n работает гораздо быстрее первого алгоритма.
Дополню: теория предполагает что шаг алгоритма имеет константную "стоимость", тогда как в реальности на реальном железе это довольно редко соблюдается. Даже тупо компаратор в сортировке может иметь сложность позаковыристее самой сортировки.
Так что когда речь заходит за производительность сначала пишем черновой вариант "по теории" а потом допиливаем это всё под реалии под пристальным наблюдением профайлера.
Здравствуйте, Sharov, Вы писали:
S>Мне кажется теоретическую границу можно вывести каким-нибудь отношением "доступ RAM/L1", т.е. S>пусть k="доступ RAM/L1", тогда если log n > k, то типа можно и нужно использовать log(n). Как-то так.
Там ж не только для разных алгоритмов но и для разных типов обрабатываемых данных будут разные соотношения выходить.
Подобные ускорения за счёт locality лучше всего применяются когда юнит данных маленький, меньше чем cache line
Здравствуйте, so5team, Вы писали:
Тё>>Мне тут коллега предлагает Тё>>
Тё>>[9/4, 10:12] : Catch all это путь к стрессу, согласен
Тё>>[9/4, 10:13] : На пипку садить можно за кэтч ол
S> если твой коллега не представляет себе контекст, в котором catch all использовали,
Ого, уже на коллегу оскорбления.
Когда случился зашквар, то контекст этого нерелевантен по отношению к факту случившегося.
S>>>Понятно, голоса. Тё>>Ага, голоса. На 100 участников из самых крутых плюсных контор.
S>Я сейчас общаюсь не с теми участниками, а с тобой. И мне приходится расшифровать выплески потоков сознания от голосов из твоей головы. Так что претензия не к участникам каких-то митапов, а к твоим рассказам об этих самых митапах. Бессмысленным и бессвязным.
Туши коллектор.
Здравствуйте, Lexey, Вы писали:
S>>и поиск цикла в list
L>А вот это плохая задача для собеседований. Ибо, к ней нужен весьма специальный подход. И если его не знаешь, то не решишь, скорее всего.
какой специальный подход ? два указателя "быстрый" и "медленный", догнал быстрый указатель медленный значит есть циклы.
проще через хэш-таблицу решить, но обычно говорят, что нельзя её использовать.
Здравствуйте, vsb, Вы писали:
Pzz>>Ну в принципе, этот алгоритм не то, чтобы совсем очевидный. Если тебе его не рассказали, сам можешь и не придумать.
vsb>Его даже Флойд смог придумать. Если ты не уровня Флойда, что ты вообще делаешь в программировании? Может пора метлу осваивать?
Флойд — это тот самоучка без диплома, которому Тьюринговскую премию дали?
Здравствуйте, Pzz, Вы писали:
Pzz>>>Ну в принципе, этот алгоритм не то, чтобы совсем очевидный. Если тебе его не рассказали, сам можешь и не придумать.
vsb>>Его даже Флойд смог придумать. Если ты не уровня Флойда, что ты вообще делаешь в программировании? Может пора метлу осваивать?
Pzz>Флойд — это тот самоучка без диплома, которому Тьюринговскую премию дали?
Ну если верить вики, хватает у него дипломов, в том числе и профессором стал в 28 лет.
Здравствуйте, sergey2b, Вы писали:
S>Собеседование в Яндекс: театр абсурда :/
Ну а что Вы хотите. В Яндексе списки гномиков переворачивают звезды. Сотни тысяч программистов делают свою работу. Не каждому дано переворачивать списки гномиков над люками.
Здравствуйте, Lexey, Вы писали:
L>Здравствуйте, sergey2b, Вы писали:
S>>в принципе задачки нормальные, не чем не хуже реверса отдельных слов в строке
L>Лучше, в основном. Реверс строки или слов в строке — это уже заезженная пластинка.
Для тебя заезженная. Для многих нет.
S>>и поиск цикла в list
L>А вот это плохая задача для собеседований. Ибо, к ней нужен весьма специальный подход. И если его не знаешь, то не решишь, скорее всего.
Если не знаешь, можно поговорить. Там 3 варианта решения, соответственно, "без использования памяти и модификации"- можно подсказать.
Здравствуйте, Тёмчик, Вы писали:
Pzz>>Ну в принципе, этот алгоритм не то, чтобы совсем очевидный. Если тебе его не рассказали, сам можешь и не придумать.
Тё>Наблюдал, как весьма хорошие программисты, успешно и быстро решившие тот же переворот, впадали в ступор при подсказках про поиск цикла.
А ты сможешь решить такую задачу: есть массив, он разделен на две, возможно неравные, части (0...N, N+1...M), надо переставить эти две части местами?
Здравствуйте, Pzz, Вы писали:
Pzz>А ты сможешь решить такую задачу: есть массив, он разделен на две, возможно неравные, части (0...N, N+1...M), надо переставить эти две части местами?
Pzz>[AAAA][BBBBB] -> [BBBBB][AAAA]
Можно как разворот строки решить, сходу, за 2с*O(N). Можно заморочиться чтоб за c*O(N-1), то мне лень мозг вывихивать.
Здравствуйте, Pzz, Вы писали:
Б>>Переворачиваем сначала весь массив, а потом переворачиваем каждую часть. Б>>Переворачиваем = переставляем в обратном порядке. Т.е. меняем первый элемент с последним, второй с предпоследним и т.д.
Pzz>Мне когда в реальной жизни понадобилось, я сделал рекурсивно: выбираем ту "половину", которая поменьше, и меняем ее местами с соседней с ней частью такого же размера. Потом во второй половине рекурсивно меняем ту часть, которую мы только что туда записали, и оставшуюся.
Pzz>[AAAA][BBBBB] -> [BBBB][AAAA][B] -> [BBBB][BAAAA]
Pzz>Про тройной переворот я не знал/не догадался. Но рекурсивный вариант вроде как делает меньше обращений к памяти (на каждом шаге одна из частей массива оказывается уже на своем окончательном месте).
Это двойной переворот.
Можно сделать циклический сдвиг, получится O(N):
[0..k), [k..n)
Как-то так, но нужно проверять правильность offset:
function swap_k<T>(a: T[], k: number) {
const n = a.length;
if (k === 0 || k === n - 1) {
return;
}
const acc = a[k];
const offset = n / 2 + n % 2;
for (let i=0; i < offset; ++i) {
a[(k + i) % n] = a[(k + offset + i) % n];
}
a[k + off] = acc;
}
Здравствуйте, Pzz, Вы писали: Pzz>>>А ты сможешь решить такую задачу: есть массив, он разделен на две, возможно неравные, части (0...N, N+1...M), надо переставить эти две части местами? Pzz>>>[AAAA][BBBBB] -> [BBBBB][AAAA] Б>>Переворачиваем сначала весь массив, а потом переворачиваем каждую часть. Б>>Переворачиваем = переставляем в обратном порядке. Т.е. меняем первый элемент с последним, второй с предпоследним и т.д. Pzz>Мне когда в реальной жизни понадобилось, я сделал рекурсивно: выбираем ту "половину", которая поменьше, и меняем ее местами с соседней с ней частью такого же размера. Потом во второй половине рекурсивно меняем ту часть, которую мы только что туда записали, и оставшуюся. Pzz>[AAAA][BBBBB] -> [BBBB][AAAA][B] -> [BBBB][BAAAA] Pzz>Про тройной переворот я не знал/не догадался. Но рекурсивный вариант вроде как делает меньше обращений к памяти (на каждом шаге одна из частей массива оказывается уже на своем окончательном месте).
Двойной разворот -- это из "Потрескивания на интервью по написанию кода". А интересная оказалась задача, вот мой однопроходный вариант:
function swapArrayParts(arr, ind) {
if (!Array.isArray(arr))
return "Incorrect array.";
var len = arr.length;
if (!Number.isInteger(ind) || ind < 1 || ind >= len)
return "Incorrect index.";
var i, curPos = 0, oldPos, newPos, oldBuff = arr[curPos], newBuff;
for (var i = 0; i < len; i++) {
newPos = curPos < ind ? curPos + len - ind : curPos - ind; // New position to drop the previous buffered item.
newBuff = arr[newPos];
arr[newPos] = oldBuff;
if (oldPos === newPos) { // 2 elements have swapped, move to the next item in the 1st subset.
curPos = newPos + 1;
oldBuff = arr[curPos];
}
else { // Leap with the buffered value to the new position.
oldPos = curPos;
curPos = newPos;
oldBuff = newBuff;
}
}
return arr;
}
Тест
<html>
<body>
<form onsubmit="javascript:swapArr(); return false;" >
<p>
Array (chars w/o delimiters): <br/><input type="string" id="arr"> <p>
Pivot (0-based index of the first item in the 2nd subset): <br/><input type="number" id="ind" min="1"> <p>
<input type="submit" value="Swap">
</form>
Result:<p>
<p id="output"/>
<script>
function swapArrayParts(arr, ind) {
if (!Array.isArray(arr))
return "Incorrect array.";
var len = arr.length;
if (!Number.isInteger(ind) || ind < 1 || ind >= len)
return "Incorrect index.";
var i, curPos = 0, oldPos, newPos, oldBuff = arr[curPos], newBuff;
for (var i = 0; i < len; i++) {
newPos = curPos < ind ? curPos + len - ind : curPos - ind; // New position to drop the previous buffered item.
newBuff = arr[newPos];
arr[newPos] = oldBuff;
if (oldPos === newPos) { // 2 elements have swapped, move to the next item in the 1st subset.
curPos = newPos + 1;
oldBuff = arr[curPos];
}
else { // Leap with the buffered value to the new position.
oldPos = curPos;
curPos = newPos;
oldBuff = newBuff;
}
}
return arr;
}
function swapArr() {
var arr = document.getElementById("arr").value;
var ind = document.getElementById("ind").valueAsNumber;
var output = swapArrayParts(arr.split(""), ind);
document.getElementById("output").innerHTML = output;
}
</script>
</body>
</html>
Здравствуйте, AmSpb, Вы писали:
AS>Здравствуйте, SaZ, Вы писали:
SaZ>>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта? SaZ>>Как бы для своих решений я могу посчитать алгоритмическую сложность. Даже объяснял это с примерами. SaZ>>Убило то, что на этим вопросом меня мурыжили 45 минут не давая никаких наводящих вопросов, а на все мои рассуждения и попытки найти истину отвечали: это неправильно. SaZ>>Оказалось, что от меня хотели, чтобы я просто взял предел.
AS>А причем тут предел ? AS>Можно график начертить, и увидеть, что квадратичная фунция растет быстрее линейной, и при n стремящимся в бесконечность, значение C можно принять за 1, т.к. это константа, т.е. она не зависит от n
Рисовал график. От меня требовали именно теоретическое обоснование.
Здравствуйте, SaZ, Вы писали:
AS>>А причем тут предел ? AS>>Можно график начертить, и увидеть, что квадратичная фунция растет быстрее линейной, и при n стремящимся в бесконечность, значение C можно принять за 1, т.к. это константа, т.е. она не зависит от n
SaZ>Рисовал график. От меня требовали именно теоретическое обоснование.
Наверное аналитическое обоснование. Ту же производную можно обосновать геометрически, а можно аналитически, чисто через формулы.
Ну если хотели аналитическое обоснование, то тут тоже довольно просто:
1. O(С*n) < O(n^2)
2. O(С*n) / O(n^2) < 1
3. С/n < 1 для всех C < n
4. lim C/n -> 0 при n -> oo
Здравствуйте, AmSpb, Вы писали:
AS>Здравствуйте, Lexey, Вы писали:
S>>>и поиск цикла в list
L>>А вот это плохая задача для собеседований. Ибо, к ней нужен весьма специальный подход. И если его не знаешь, то не решишь, скорее всего.
AS>какой специальный подход ? два указателя "быстрый" и "медленный", догнал быстрый указатель медленный значит есть циклы.
AS>проще через хэш-таблицу решить, но обычно говорят, что нельзя её использовать.
Если в задаче есть требование найти узел где начинается цикл то задача выглядит гораздо более интереснее.
Здравствуйте, aik, Вы писали:
aik>пост же не про задачи сами по себе, а что одну и ту же пластинку ставят раз за разом. такое ощущение что это какие то hunger games заочные, ищут самого выносливого и/или мотиварованного что ли.
Это палка о двух концах. С одной стороны почти у всех компаний процесс собеседования отдаёт дибилизмом так или иначе. Исключений здесь нет по той лишь причине, что не существует критерия успешного найма. С другой стороны, взрослые люди понимают, что если они идут выполнять работу за деньги, то это право того, кто платит, решать, каким образом собеседовать. Поэтому новоиспечённые вайтишники приняли статью тепло, ведь там об их общей боле написано, а людям с опытом нытьё не поняли от слова совсем.
Что скрывать, я и сам лет 5-7 был Д'Артаньяном и имел на всё своё мнение, но опыт (в том числе и найма людей) научил соблюдать субординацию и относиться с пониманием к тому, что кажется странным на первый взгляд.
Здравствуйте, cppguard, Вы писали:
C>Что скрывать, я и сам лет 5-7 был Д'Артаньяном и имел на всё своё мнение, но опыт (в том числе и найма людей) научил соблюдать субординацию и относиться с пониманием к тому, что кажется странным на первый взгляд.
Ну и какой смысл спрашивать вот этот вот кодинг раз за разом? Он же точно не будет целыми днями только этим и заниматься, от него потребуют что то приземленное писать тоже, но это походу никого не интересует в данном кандидате.
SaZ>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта?
Задача некорректна. Константа должна быть в обоих выражениях. Иначе результат сравнения зависит от ее размера. При С бесконечно большом, условие не выполняется.
Возможно, именно такой ответ и ожидался.
Хотя, смысла в такой задаче на собеседовании я не вижу.
SaZ>>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта? N>Задача некорректна. Константа должна быть в обоих выражениях. Иначе результат сравнения зависит от ее размера. При С бесконечно большом, условие не выполняется.
Константа на то и константа, что ни от чего не зависит.
Как говорится, если бы у бабушки был член с яйцами, она была бы дедушкой.
Так и тут, константа от чего-то зависящая, называлась бы функцией
Здравствуйте, SaZ, Вы писали:
SaZ>В общем, меня завалили на вопросе: объясните почему сложность O(С*n) < O(n^2) где С — конастанта?
1) Графически: рисуем графики функций y = Cx и y = x^2, показываем что первый растёт медленнее.
2) Вычитаем функции друг из друга и получаем y = x^2 — Cx, показываем что на правой полуплоскости это возрастающая функция (если уж очень прикопались, через взятие производной y = 2x)
Здравствуйте, σ, Вы писали:
aik>>Ну и какой смысл спрашивать вот этот вот кодинг раз за разом? Он же точно не будет целыми днями только этим и заниматься σ>Поэтому нужно спрашивать архитектуру высоконагруженного приложения! Ведь программисты точно целыми днями только этим и занимаются. По 3 высоконагруженных приложения в час выпекают в среднем.
Мне доставило, что этот кадр пишет "высоконагруженные приложения" пузырьком.
Здравствуйте, kaa.python, Вы писали:
KP>Комменты вообще огонь я считаю и реально театр абсурда. Каждый второй сводится к тому, что "я хотел бы в Яндекс, но как только захожу на Литкод, корона нестерпимо давить начинает".
Здравствуйте, Тёмчик, Вы писали:
Тё>глотал все исключения в цикле
Во-первых, какое отношение проглатывание исключений имеет к пенисометрии на лучшее понимание big-O?
Во-вторых, что Тёмчик предложит делать в деструкторе класса, когда нужно вызвать close() для 100500 объектов connection, а этот close() бросающий? Есть какой-то другой рецепт?
Удивляет в 21-году эмоциональный отклик автора на continuous hiring в крупные компания, ... в очень крупные компании.
Друзья там так все устроенно, что процесс найма должен идти всегда, даже если вакансии закрыты. )
Поэтому оптимум процесса найма не важен, важено только наличие самого процесса. )
Качество тоже не важно, смогут работать любые дебылы, важен только процесс отбора текущих лучших (мгновенное состояние), поэтому в часности и не спрашивают ничего из предметного опыта )
Здравствуйте, Тёмчик, Вы писали:
Тё>Ходил я на митапы раньше, и что неприятно поразило именно на плюсниковых- 3/4 докладчиков было с позорной форточкой запускали в ней позорную студию. Это не говоря про сами доклады "смотрите, какая прогрессивная фича", а этой фичей уже 20 лет в питоне например пользуются. Сектанты, как они есть.
Ты серьезно?! Сравнить местечковые мииапы с ежегодной международной конференцией, где выступают люди первой величины в профессии? Причем не просто по видео, а лично приезжают. Видео может где-то может и лежит, я его воспринимать не могу, предпочитаю лично присутствовать.
Здравствуйте, Sharov, Вы писали:
S>А есть реальные примеры с объяснением почему?
Например потому что cache locality обеспечивает существенный прирост алгоритмов с линейным доступом.
S>Ибо суть O-нотации как раз в том, что мы предполагаем n очень большим, т.е. n -> inf, соотв. любой константой можно пренебречь.
Для теории этого более чем достаточно, но практика вносит свои коррективы. Стоимость выполнения инструкции на современных CPU зависит от кучи сторонних факторов, включая те инструкции, что были выполнены до неё или в параллель с ней.
Здравствуйте, CreatorCray, Вы писали:
S>>А есть реальные примеры с объяснением почему? CC>Например потому что cache locality обеспечивает существенный прирост алгоритмов с линейным доступом.
А как это влияет на O(log(n)) vs O(n)? Типа при O(n) locality будет лучше? Почему также нельзя сделать для O(log(n))?
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, Sharov, Вы писали:
S>>Почему также нельзя сделать для O(log(n))? CC>А где ты видел алгоритмы с log n и линейным доступом к данным?
М-да, справедливо. Но тогда по разнице доступы к L1 и RAM (вроде в 100 раз ?), соотв. если у нас будет
в 100(1000,10000 и т.д.) раз больше элементов, то мы точно сможем сказать, что log(n) быстрее.
А так да за счет spatila locality можно в отыграть разницу между n и log(n) до определенного предела.
Вот когда эта разница будет слишком велика, больше разницы между L1 и RAM, вот тогда можно быть точно уверенным.
В любом случае, если про это спрашивают на общих основаниях, то явно имеется в виду понимание сложности,
а не всяческих хаков железяк.
Здравствуйте, CreatorCray, Вы писали:
S>>если у нас будет в 100(1000,10000 и т.д.) раз больше элементов, то мы точно сможем сказать, что log(n) быстрее. CC>Точно можно сказать только померяв. Тем практика от теории и отличается, что на практике есть туча "движущихся частей" которые на первый взгляд не видны пока не посмотришь профайлером и не станешь разбираться что за фигня происходит.
Мне кажется теоретическую границу можно вывести каким-нибудь отношением "доступ RAM/L1", т.е.
пусть k="доступ RAM/L1", тогда если log n > k, то типа можно и нужно использовать log(n). Как-то так.
Здравствуйте, CreatorCray, Вы писали:
CC>С этим никто не спорит. Речь была про то, что мало просто знать теорию, надо ещё иметь понимание нюансов, отсутствующих в этой теории + практику применения,
Эти "нюансы" вследствие упрощения модели. Сначала теория, потом нюансы. Но ты же только сейчас признал, что одной теории мало, а до того по твоим сообщениям складывалось ощущение, что ты против этой самой теории. Как состим или хайлендер, — у них пригорает пои упоминании про алгоритмы на собеседовании.
Здравствуйте, Тёмчик, Вы писали:
Тё>Но ты же только сейчас признал, что одной теории мало C самого начала говорил.
Тё> а до того по твоим сообщениям складывалось ощущение
Как обычно у тебя угадайка работает просто отвратительно.
Здравствуйте, Тёмчик, Вы писали:
N>>Ты серьезно?! Сравнить местечковые мииапы с ежегодной международной конференцией, где выступают люди первой величины в профессии? Тё>Местечковые конференции в HFT-й конторе
Тема, извини, но HFT в Сиднее уже само по себе звучит смешно
Здравствуйте, landerhigh, Вы писали:
L>Тема, извини, но HFT в Сиднее уже само по себе звучит смешно
IMC и Optiver — всё ещё смешно?
На фоне околожелезячного шнайдер, возможно, смех истеричен при сравнении зп.
Здравствуйте, Тёмчик, Вы писали:
