Комментарии 347
Это справедливо для кодера (он же — "прикладной программист"), но не для разработчика (который с большой буквы).
Рано или поздно возникают задачи, которые не может адекватно решить не то что ни одна из boost'овских библиотек — в принципе ни одна из существующих. И тогда приходится делать свой алгоритм, свою библиотеку, еще лучше других. Так и происходит прогресс :)
Другое дело, что задач, не требующих computer science, гораздо больше — как в принципе и всего в реальном мире. Продавцов и менеджеров значительно больше, чем ученых. Тем не менее, в школах дают базовых курс физики и химии, поэтому понимание алгоритмов на базовом уровне (хотя бы для перспективы роста) — скорее необходимо.
Рано или поздно возникают задачи, которые не может адекватно решить не то что ни одна из boost'овских библиотек — в принципе ни одна из существующих. И тогда приходится делать свой алгоритм, свою библиотеку, еще лучше других. Так и происходит прогресс :)
Другое дело, что задач, не требующих computer science, гораздо больше — как в принципе и всего в реальном мире. Продавцов и менеджеров значительно больше, чем ученых. Тем не менее, в школах дают базовых курс физики и химии, поэтому понимание алгоритмов на базовом уровне (хотя бы для перспективы роста) — скорее необходимо.
я и не спорю. просто странно, почему так востребованы и действительно полезны прикладные знания
Потому что специалист, который знает библиотеки, но не понимает, как работает хеширование, сортировка, бинарный поиск, прохождение графов и т.д., может решать задачи, но до первой серьезной проблемы. Если где-то возникнет «бутылочное горлышко», понимающий алгоритмы разработчик его сможет разрешить, а кодер — не сможет.
Такие случаи в моей практике — крайне редки. Сортировки и поиски по деревьям давно написаны и в либах и в БД. Хэширование… ну там просто все, на пальцах, за полчаса можно дойти по linear-probing hashing с бубнами. А глубоко понять… изменение системы счислений, метод Горна… нужно ли для решения задачи?
Ну как редки? Практически в любом крупном проекте когда-никогда случаются. И в команде нужно иметь хотя бы одного специалиста, который способен их разрешать. Вы же поймите, что без этих знаний вы, конечно же, работу себе найдете и сможете вполне успешно заниматься разработкой. Но вы просто себе выставляете определённый потолок профессионального мастерства, за который (почему-то, непонятно почему) решили не заходить.
Не все проекты являются высоконагруженными. Вам может нравится писать собственную реализацию какой-нибудь операции с модным алгоритмом дающим 1% прироста скорости, но вот юзеров будут бесить баги, которые возникают из-за того что вы пишите свой велосипед, а не используете проверенное решение, где баги уже выловили.
Мы о разных вещах говорим. Я говорю, что знание и понимание алгоритмов — это полезное качество для профессионального разработчика. И может ему пригодиться в ряде случаев. Вы говорите, что плохо писать велосипеды и делать программы с багами. Конечно же, это плохо. Но к умению писать алгоритмы оно никакого отношения не имеет. Если человек вместо использования подходящего по критериям проекта готового решения пишет велосипед, это как раз непрофессионально.
С другой стороны, обратите внимание на «подходящего по критериям проекта». Наличие готового решения само по себе — это тоже далеко не всегда признак того, что не надо писать велосипед. Во-первых, его кастомизация может быть сложнее и «дырявее», чем создание некоторого нужного проекту подмножества функций. Во-вторых, оно может быть… плохо проверенным. Готовые библиотеки далеко не всегда хорошие. И так далее. В общем, не ищите себеряную пулю в стратегиях разработки, нет её. Но никакие профессиональные знания/умения лишними не бывают.
С другой стороны, обратите внимание на «подходящего по критериям проекта». Наличие готового решения само по себе — это тоже далеко не всегда признак того, что не надо писать велосипед. Во-первых, его кастомизация может быть сложнее и «дырявее», чем создание некоторого нужного проекту подмножества функций. Во-вторых, оно может быть… плохо проверенным. Готовые библиотеки далеко не всегда хорошие. И так далее. В общем, не ищите себеряную пулю в стратегиях разработки, нет её. Но никакие профессиональные знания/умения лишними не бывают.
Я скорее имел ввиду, что знание алгоритмов полезно но не является решающим навыком в квалификации программиста (за исключением особых случаев, типа поддержка критичного компонента в хай-лоад системе). Для сферического веб-программиста в вакууме будет полезнее знать SQL и особенности используемой БД, чем помнить как работает merge sort. И поэтому когда вы спрашиваете на интервью как инвертировать бинарное дерево, то потом не жалуйтесь что нету нормальных кандидатов.
А особенности используемой БД разве не выражаются в тех алгоритмах, которые там используются?
А кто нам даст время писать свою БД? :-)
В той БД, которую вы используете каждый день — какие-то другие вещи, а не алгоритмы?
Думаю, пора выпускать дистрибутивы БД с надписью «без алгоритмов».
Думаю, пора выпускать дистрибутивы БД с надписью «без алгоритмов».
знание и понимание алгоритмов — это полезное качество
На мой взгляд это полезные качествА, то есть это разные вещи. Я закончил универ не так давно и уже ужасаюсь тому, что все забыл. Поэтому я для себя решил, что универ учит скорее учиться и понимать алгоритмы, чем их знать и успокоился.Вполне естественно, что серое вещество забивается теми вещами, которые часто используешь. Ничто же не мешает найти в гугле нужный алгоритм и реализовать его так, как мне надо.
А еще по опыту работы, реализовать какой либо алгоритм эффективнее существующих решений сложно, но возможно это или нет — зависит скорее от IQ человека, чем от того знает он алгоритм наизусть или нет. Разница между тем, хранится знание в сером веществе или в электронном виде где нибудь на сервере — только в скорости доступа)
Разница между тем, хранится знание в сером веществе или в электронном виде где нибудь на сервере — только в скорости доступа
Соглашусь. Однако, скорость доступа порой имеет очень важное значение. Например, когда для решения сложной задачи надо комбинировать набор алгоритмов. Если алгоритмы в "быстром доступе" в мозге, то решение будет найдено, если алгоритмы на сервере, то решение может быть попросту не найдено, так как мозг не будет способен найти "хитрую" но полезную связь между двумя описаниями алгоритма на сервере, в то же время, он сможет найти и использовать эту связь, если алгоритмы есть в мозгу. Подобным свойством мышления оперируют, в частности, MindMap'ы для достижения "Аха!"-эффекта при решении сложных задач..
Другой пример: решая сложную задачу, можно внезапно обнаружить, что ты изобретаешь велосипед, исходя из прототипа/набросков нового алгоритма — осознав, что предложенное новое "наивное" решение задачи есть не что иное, как реализация алгоритма X, который уже давно изучен, и можно сразу найти все его преимущества и недостатки… Я таких велосипедов наизобретал в аспирантуре, когда волею судеб был брошен в новую (ок, хорошо забытую со 2-го курса) для меня область.
Вы уже сами ответили на свой вопрос:
Я лично считаю что программирование конечно ремесло, ремесло в той же степени как и например живопись. А чего там такого сложного? Здесь красным намазать, здесь зеленым, и погуще, двухнедельных курсов должно хватить на обучение.
ну там просто все, на пальцах, за полчаса можно дойти— я верю что вы дойдете, а вот кодер — нет. Неужели не встречали таких? С другой стороны, обратный случай тоже нередок — перекачанный в теории индивид начинает через губу всех учить, хотя его код очевидно никуда не годится.
Я лично считаю что программирование конечно ремесло, ремесло в той же степени как и например живопись. А чего там такого сложного? Здесь красным намазать, здесь зеленым, и погуще, двухнедельных курсов должно хватить на обучение.
Ну да, но без знания анатомии вы портрет хороший не нарисуете.
> Я лично считаю что программирование конечно ремесло, ремесло в той же степени как и например живопись
Ну не совсем так. Для программирования все-таки только знания нужны, а для любой живописи нужны как знания, так еще и «физические» навыки.
Ну не совсем так. Для программирования все-таки только знания нужны, а для любой живописи нужны как знания, так еще и «физические» навыки.
Ведь проблема не в том, что надо написать сортировки, хеширование и другое. Проблема в том, что человек, который не писал, не может отличить одно от другого! И потом если ошибка в библиотеки он в полном ступоре. В общем проблема не в том, чтобы взять готовое решение, проблема в том, чтобы понять, что это решение.
Человек, который не знает, что такое поиск в ширину и в интернете найдет полную фигню.
Человек, который не знает, что такое поиск в ширину и в интернете найдет полную фигню.
Кодер пойдет на stackoverflow и тоже сможет )
Один из моих преподавателей на эту тему высказывался примерно так.
Само по себе _программирование_, в смысле написания кода — это ремесло. Можно и не знать «как», «почему» и «зачем», но при этом писать действительно замечательный код. Более того, при этом можно даже учить других это делать :-) Но, без «как», «почему» и «зачем» кроме, собственно написания кода, в наше с вами области знаний ничего делать-то и нельзя. Хорошая «новость» для некоторых из вас, заключается в том, что в подавляющем большинстве случаев вы будете заниматься т.н. прикладными задачами, которые суть и есть «задачи по написанию кода». Т.к. они уже давно все решены, и все что будет требоваться от вас, это записать это решение на каком-то конкретном языке.
Это сложное ремесло. Огромное количество проектов — проваливается по причине "заговнокожения" чистых идей. Взлетают реально единицы.
Сложное оно или нет — не важно же на самом деле :-) Писать код — это ремесло, ровно в том же смысле, в котором ремеслом является написание любого текста. Например, чтобы написать свой комментарий, вам сильно вряд ли понадобились знания о "как", "зачем" и — главное — "почему" в плане, например, падежей русского языка :-) Т.е. это, грубо говоря, дело привычки… навык, если хотите. А это и есть ремесло. У кого-то этот "навык" развит лучше, у кого-то есть "чувство стиля", кто-то вообще "поэт-прозаик" — суть от этого не меняется :-)
Ни разу не видел проекта, который бы провалился по причине говнокода.
Зато знаю массу невероятно популярных проектов, представляющих из себя нечто невообразимое, но крайне востребованное десятилетиями.
простейший пример — WordPress. Или любой бесплатный движок интернет-магазина.
Талантливый алгоритмист — враг стартапа, пока он не называется Google. Всем остальным хватит говнокода, вопрос совсем не в этом.
первое, что определяет успех проекта — нужен ли он людям, или это фантазии авторов. Второе — сумеют ли авторы о себе рассказать. А как там оно написано — да плевать с пизанской башни, лишь бы работало. Будет затык — поправят. Наймут кого-то на месяц, и поправят. Или перепишут. Или свой компилятор нарисуют. Все это фигня, главное, чтоб был интерес...
Зато знаю массу невероятно популярных проектов, представляющих из себя нечто невообразимое, но крайне востребованное десятилетиями.
простейший пример — WordPress. Или любой бесплатный движок интернет-магазина.
Талантливый алгоритмист — враг стартапа, пока он не называется Google. Всем остальным хватит говнокода, вопрос совсем не в этом.
первое, что определяет успех проекта — нужен ли он людям, или это фантазии авторов. Второе — сумеют ли авторы о себе рассказать. А как там оно написано — да плевать с пизанской башни, лишь бы работало. Будет затык — поправят. Наймут кого-то на месяц, и поправят. Или перепишут. Или свой компилятор нарисуют. Все это фигня, главное, чтоб был интерес...
Я работал в стартапе, в котором было много говнокода. Конечно, нельзя сказать с уверенностью сказать, что он не взлетел из-за говнокода (были проблемы с монетизацией), но и из-за него было много проблем: на определенном этапе стало тяжело вносить изменения, начались тормоза, баги, хранение информации в облаках (фотографии) стало выливаться в большие шестизначные суммы в месяц (думаю, что это можно было бы оптимизировать и достаточно сильно сократить расходы). Толковый программист не пойдет работать в стартап с говнокодом (ну я бы сейчас точно не пошел ни за какие деньги). На мой взгляд и по моему опыту можно почти сразу писать хороший код (в начале допустим прототип с говнокодом, который потом без сожалений нужно выкинуть).
А какие бы вы назвали проекты, которые провалились по причине "заговнокожения" чистых идей? Я без сарказма.
В отличии от проектов, которые не провалились, такие мало известны. Я, например, видел, как написанный за приличные деньги в течении двух месяцев проект, начал валиться при 6(!) посетителях в минуту. Автор просто отказался что-то менять — "у меня не было задачи делать хайлоад". Все. Проект свернули, так-как переписывать его было уже не было времени и заказчик не хотел терять еще деньги.
А, ну такого навалом, да :) Но может там и нет "чистых идей", которые указал автор. Я, честно говоря, не понял, что это за "чистые идеи", поэтому решил уточнить.
Чистая идея… идея, которая должна быть 100% без рисков попадания метериотом по голове — завершиться.
Возьмем веб-сервер. Что там сложного и где там алгоритмы новые. Тупой кондовый текстовый протокол. Да, хайлоад может быть.
И что мы видим в мире? Треш!
На первом месте написанный на чистом C — nginx, который делает всех вчистую и по скорости, и по масштабируемости.
Дальше видим написанный умными с потоками apache, который конечно тормознутый монстр.
Я не говорю уже про Tomcat на java — перед которым нужно ставить nginx ;-)
Т.е. простая идея, реализуемая на бумаге, превращается в лужу крови с мозгами в реальности… и рынок выбирает лучшее — nginx ;-)
Возьмем веб-сервер. Что там сложного и где там алгоритмы новые. Тупой кондовый текстовый протокол. Да, хайлоад может быть.
И что мы видим в мире? Треш!
На первом месте написанный на чистом C — nginx, который делает всех вчистую и по скорости, и по масштабируемости.
Дальше видим написанный умными с потоками apache, который конечно тормознутый монстр.
Я не говорю уже про Tomcat на java — перед которым нужно ставить nginx ;-)
Т.е. простая идея, реализуемая на бумаге, превращается в лужу крови с мозгами в реальности… и рынок выбирает лучшее — nginx ;-)
Ну, тут вы причины со следствиями вывернули. Именно apache и был написан "втупую". Создать по потоку на соединение — это вообще самое простое решение, которому учат в любом учебнике.
А вот автору nginx пришлось постараться — асинхронные конечные автоматы, хитрое управление памятью, свои структуры данных...
А вот автору nginx пришлось постараться — асинхронные конечные автоматы, хитрое управление памятью, свои структуры данных...
Сорри. Но я к тому, что человек просто знал хорошо FreeBSD, добавил немного структур данных (видели исходники наверно подробно), написал аккуратно и со вкусом и без выпендрежа. И на этом живет хайлоад всего мира. Победила проста и здравый смысл.
Ну еще из интересного там — обработка сокетов через select/pool. Это старая техника, но эффективная и сложная в реализации. Никаких алгоритмов новых.
Мне кажется, вы делите алгоритмы на "это я знаю, это не ново (для меня)" и "этого я не знаю, это что-то новое неизвестное, да и зачем это учить".
Это вы знаете про select/poll. А для кого-то неблокируемые сокеты — это "вау, ничего себе!". Почему? Потому что он последовал вашему совету и не изучал алгоритмы :)
Кстати, у nginx ещё и sendfile, async io, хеш таблицы с использованием строки кэша процессора и много других алгоритимческих вкусностей.
nginx — это вообще отличный пример, когда просто хорошее знание и применение алгоритмов дало пользу всему человечеству.
Это вы знаете про select/poll. А для кого-то неблокируемые сокеты — это "вау, ничего себе!". Почему? Потому что он последовал вашему совету и не изучал алгоритмы :)
Кстати, у nginx ещё и sendfile, async io, хеш таблицы с использованием строки кэша процессора и много других алгоритимческих вкусностей.
nginx — это вообще отличный пример, когда просто хорошее знание и применение алгоритмов дало пользу всему человечеству.
Нет, это новая техника. Многопоточный вариант появился раньше.
Еще пример чисто идеи — микроядро ОС, о котором спорят Торвальдс с Таненбаумом. :-) И что использую люди — тупо, кондово, монотитно написанный linux. FreeBSD, OpeenBSD,… — писались более умно, правильно, секьюрно — и где они?
Названия я не могу сказать, но много лет назад еще до Битрикс часто наблюдал такие кейсы:
1) Ставится очевидно достижимая задача, без новых алгоритмов
2) Ее делает один человек и видно четко, что скоро все закончится
3) Набираются люди
4) Появляются "умники", втыкающие неадекватно сложные-дорогие-ненужные вещи. Ну например вместо записи байтов в сокет ставим либу, которая делает тоже самое через задницу и ООП.
5) Проект никак не может завершится. Сроки сорваны. Люди увольняются. Умники делают черточку в резюме :-)
1) Ставится очевидно достижимая задача, без новых алгоритмов
2) Ее делает один человек и видно четко, что скоро все закончится
3) Набираются люди
4) Появляются "умники", втыкающие неадекватно сложные-дорогие-ненужные вещи. Ну например вместо записи байтов в сокет ставим либу, которая делает тоже самое через задницу и ООП.
5) Проект никак не может завершится. Сроки сорваны. Люди увольняются. Умники делают черточку в резюме :-)
Понятно. Вы знаете, так получилось, что вы только что сами ответили на вопрос, зачем программисту знать алгоритмы. Просто для того, чтобы понимать, какой алгоритм лучше применить в каждом случае и не тащить вместо этого гору библиотек.
В вашей логике есть один момент, который вы упустили — вы уже знаете алгоритмы и применяете эти знания, не задумываясь об этом. И, пописывая код с этими знаниями, думаете "а надо ли мне было учить вот это все?". У вас есть понимание, когда что можно воткнуть. Это вам помогает больше, чем вы думаете.
А кто-то просто не знает и втыкает либу, где это уже реализовано. Минус тут только в том, что человек не понимает что происходит внутри.
Если ему дать две либы сортировки, как ему понять, какую применять, если он не понимает, что там происходит?
Или есть два алгоритма хеширования, и у одного проблемы с коллизиями, если его применять к длинным строкам (например, там берутся первые 32 символа). Если вы про это знаете, вы выберете правильный алгоритм. А кто-то столкнется с "неожиданными" проблемами на продакшене через пару месяцев. Вы этому человеку скажете "да ты че, это ж известная фигня", а он только разведет руками "ну, откуда ж я знал...".
Поэтому, отвечая на ваш вопрос, "нужно ли знать", ответ "ДА". Необязательно, чтобы их применять, или разрабатывать новые. Но хотя бы для того, чтобы понимать, что происходит.
В вашей логике есть один момент, который вы упустили — вы уже знаете алгоритмы и применяете эти знания, не задумываясь об этом. И, пописывая код с этими знаниями, думаете "а надо ли мне было учить вот это все?". У вас есть понимание, когда что можно воткнуть. Это вам помогает больше, чем вы думаете.
А кто-то просто не знает и втыкает либу, где это уже реализовано. Минус тут только в том, что человек не понимает что происходит внутри.
Если ему дать две либы сортировки, как ему понять, какую применять, если он не понимает, что там происходит?
Или есть два алгоритма хеширования, и у одного проблемы с коллизиями, если его применять к длинным строкам (например, там берутся первые 32 символа). Если вы про это знаете, вы выберете правильный алгоритм. А кто-то столкнется с "неожиданными" проблемами на продакшене через пару месяцев. Вы этому человеку скажете "да ты че, это ж известная фигня", а он только разведет руками "ну, откуда ж я знал...".
Поэтому, отвечая на ваш вопрос, "нужно ли знать", ответ "ДА". Необязательно, чтобы их применять, или разрабатывать новые. Но хотя бы для того, чтобы понимать, что происходит.
А когда ты в проектах, они запускаются, приходят клиенты довольные — вот и появляется время почитать "а как оно работает"? :-)
Просто есть разница между прогрессом, развитием области, инструментами и прикладным программированием при разработке конечных продуктов для конкретных заказчиков и асбтрактных домохозяек. «Кодеры» в основном решают последние задачи. А вот когда появляются вопросы про реализацю чего-то кардинально нового, то тут другое дело. Приимерами могут служить различные графические движки, игровые платформы. Да даже масштабирование какой-то интернет-платформы. Качественный продукт может потребовать различных знаний.
А вот вопрос развития области требует, определённо, не простого знания библиотек. откуда появились эти удобные и производительные инструменты? Их кто-то создал.
А изучение базовых дисциплин и принципов, особенно в вузе, позволяет понять область, определить свою степень вовлечённости и интереса, а также отделяет те 0,001%, которые потом создадут что-то кардинально новое. Понятное дело, что немало кто пробился сам, но накапливать знания и узучать суть лучше с теми кто в теме. К.О.
А вот вопрос развития области требует, определённо, не простого знания библиотек. откуда появились эти удобные и производительные инструменты? Их кто-то создал.
А изучение базовых дисциплин и принципов, особенно в вузе, позволяет понять область, определить свою степень вовлечённости и интереса, а также отделяет те 0,001%, которые потом создадут что-то кардинально новое. Понятное дело, что немало кто пробился сам, но накапливать знания и узучать суть лучше с теми кто в теме. К.О.
Ты не успеешь скорее всего придумать свой алгоритм, если не занимаешься целенаправленно научной работой. Будешь искать в паперах, в материалах конференций…
зависит от места и темпа работы, дедлайна и общей склонности к научной деятельности.
проще, конечно, брать уже готовые (и я чаще так делаю), но рано или поздно приходит момент, когда ни один из готовых не обладает нужной производительностью, в таком случае приходится придумывать что-то кардинально новое или как минимум дополнять/оптимизировать существующие решения.
проще, конечно, брать уже готовые (и я чаще так делаю), но рано или поздно приходит момент, когда ни один из готовых не обладает нужной производительностью, в таком случае приходится придумывать что-то кардинально новое или как минимум дополнять/оптимизировать существующие решения.
А нужно ли знать программисту алгоритмы?
Нужно знать теорию анализа и проектирования алгоритмов — чтобы хотя бы понимать, как оценивается сложность вычисления.
там вся теория — две строки по сути
Даже нотацию большого O сложно запихнуть в две строки.
Ад, квадрат (тоже ад, но иногда нельзя), линейно-логарифмическая зависимость, линейная. Понимать что значит, что задача просто не решается и требуется перебор (NP, криптография с открытым ключом, разложение на множители и т.п.).
Недостаточно перечислить, надо знать, как это определяется.
И откуда это понимание возьмется?
… эээ, а почему перебор — это обязательно NP? Есть задачи, которые можно решить перебором за линейное время.
Понимать что значит, что задача просто не решается и требуется перебор
И откуда это понимание возьмется?
требуется перебор (NP,
… эээ, а почему перебор — это обязательно NP? Есть задачи, которые можно решить перебором за линейное время.
Как научиться понимать — посмотреть в таблицу известных алгоритмов с указанной стоимостью. Возьмем задачку дискретного логарифмирования и попробуем ускорить процесс :-)
Как научиться понимать — посмотреть в таблицу известных алгоритмов с указанной стоимостью
Вот и закончились (давно уже) ваши две строчки. Собственно, получается, что знать-то — надо.
Да вот поэтому и написал пост. С одной стороны быть компетентным — правильно. Учиться и постигать науку — нужно. Но из практики получается, что требуются знания другого рода, как не парадоксально.
Требуются знания обоих родов. И ничего парадоксального в этом нет.
По сути, да, нужно просто выучить список того, что уже открыто — 3 страницы. Чтобы пузырьком не сортировать :-)
По сути, да, нужно просто выучить список того, что уже открыто
Мало выучить список, неплохо бы еще понимать, что там зачем.
Мало выучить список, неплохо бы еще понимать, что там зачем.
Понимать — до уровня электронов?
Нет, зачем, там есть формальное описание.
Разве формальное описание не обязательно понимать? На эту тему есть замечательный отрывок из интервью с Фейнманом — Почему так сложны вопросы "почему"?. Кому-то достаточно знать "формального описания" и принимать его за основу, кому-то недостаточно. Кому-то даже формального описания знать не нужно, достаточно знать что
и уметь угадать сложность с точностью примерно плюс-минус пару-тройку звеньев. А кому-то покласть на эту сложность, потому что у него по жизни N=3.
O(1) < O(log(N)) < O(N) < O(N*log(N)) < O(N^2) < O(N^3)… < O(a^N) < O(N!)
и уметь угадать сложность с точностью примерно плюс-минус пару-тройку звеньев. А кому-то покласть на эту сложность, потому что у него по жизни N=3.
Разве формальное описание не обязательно понимать?
Обязательно. Но на этом уровне абстракции (псевдоязык и матаппарат) можно остановиться.
Если по жизни N=3, то алгоритмы не нужны, все задачи решаются перебором.
Вот только у любой базы данных N не имеет верхней границы, и O-нотация внезапно становится важна.
Вот только у любой базы данных N не имеет верхней границы, и O-нотация внезапно становится важна.
НЛО прилетело и опубликовало эту надпись здесь
да!
Осталось понять, в какую категорию относится конкретный только что написанный код.
НЛО прилетело и опубликовало эту надпись здесь
Да это тоже просто, каждый цикл обычно дает множитель N.
Каждый вложенный цикл. Но представьте себе, что у вас классический рекурсивный алгоритм "разделяй и властвуй" — в нем, конечно, вложенные циклы, но какой множитель они дают?
Поиск по упородоченным структурам (дереву, куче, отсортированному массиву) дает множитель log(N).
Ох. Поиск по упорядоченному дереву дает O(h), а не O(log n). Я не знаю, что такое "поиск в куче", но получение верхушки в куче (а это та операция, под которую куча "заточена") — O(1) (удаление верхушки — действительно O(log n)).
Все остальное можно узнать в описании либы.
Ах если бы.
НЛО прилетело и опубликовало эту надпись здесь
Ахаха, лол, может тогда и вспомните какая функция связывает h и n?
В общем случае, h <= n. И все.
O-нотация это смежные знания, они не делают программиста лучше или хуже.
А какие же знания для программиста в общем случае "чистые"?
Самого беглого знакомства достаточно.
Достаточно для чего?
Поиск по дереву — O(log n)
Поиск по дереву — O(log n)
По любому, серьезно?
Да нет, первый раз услышал про сбалансированные деревья :-)
Вы откровенно умничаете, неконструктивно жирно троллите и цепляетесь к несущественным мелочам, которые очевидны.
Вы откровенно умничаете, неконструктивно жирно троллите и цепляетесь к несущественным мелочам, которые очевидны.
НЛО прилетело и опубликовало эту надпись здесь
O(h) = O(log n) для почти всех упорядоченных деревьев.Только для сбалансированных. Для обычных упорядоченных ничего больше O(h) = O(n) гарантировать нельзя.
НЛО прилетело и опубликовало эту надпись здесь
Извините, что вклиниваюсь, но сама фараза "смотря что подразумевать под O" просто требует комментария из-за ее абсурдности и противоречивости. Есть конкретное определение O() и не с потолка оно взято. Конкретные свойства делают это определение полезным на практике. И подразумевать под O() что-то другое никак нельзя.
НЛО прилетело и опубликовало эту надпись здесь
Оговорки все равно нужны. В данном случае — про способ и порядок построения дерева. Есть задачи, в который построение дерева без балансировок будет стабильно выдавать длинные "сосиски" со средней высотой O(n).
Кстати, одна из таких задач очень распространена. Я говорю про индекс в базах данных, построенный по автоинкрементному полю.
Кстати, одна из таких задач очень распространена. Я говорю про индекс в базах данных, построенный по автоинкрементному полю.
Опять же, не придираясь к фразе, средняя оценка — это если входные данные случайны. А как вам уже ответили — это далеко не всегда так. Кроме того, если сервер можно подвесить каким-то запросом, который является худшим случаем, то это совсем не хорошо.
Извините что вклиниваюсь во вклинивание, но программисты-практики часто под O подразумевают Θ или даже Ω
O(h) = O(log n) для почти всех упорядоченных деревьев.
Только для сбалансированных. Впрочем, вам это уже написали.
Все что касается умения анализировать и формализировать задачи из реального мира
Ха, а ничего, что вы только что влезли в область работы аналитика?
И все, человек уже может работать программистом.
Есть некоторая разница между "может работать" и "хороший специалист".
Получить работу программистом, работать программистом, получать за это деньги, двигаться по карьерной лестнице
А, ну если в таких терминах, то да, сколько угодно.
Да все понятно, что тут спорить. Вопрос — в адекватности :-)
Ха, а ничего, что вы только что влезли в область работы аналитика?Если не влезать в область работы аналитика — то аналитики такого напридумывают…
> Ха, а ничего, что вы только что влезли в область работы аналитика?
Область работы аналитика является подмножеством области работы программиста. Это просто следующий уровень специализации в крупной команде.
Область работы аналитика является подмножеством области работы программиста. Это просто следующий уровень специализации в крупной команде.
Область работы аналитика является подмножеством области работы программиста.
Серьезно? Собирать со стейкхолдеров и писать хорошие, полные, непротиворечивые требования — это подмножество области работы программиста? Ну-ну, удачи этому программисту в том, чтобы найти время на программирование.
Серьезно. Фразу «следующий уровень специализации» вы недочитали, или намеренно проигнорировали?
Если вы делаете проект (хорошо, назовем его «проектик», а то некоторые начинают воротить нос, если слышат слово «проект» в отношении работы, которая делается командой меньше десяти человек и стоит меньше пары миллионов денег) в одиночку, вы будете собирать полные и непротиворечивые требования, и никуда от этого не денетесь, потом будете разрабатывать архитектуру, потом будете непосредственно программировать, потом тестировать, потом деплоить на продакшен. И всё это будет вашей работой программиста, и у вас будет время и на первое, и на второе, и на десятое. Когда-то в былые времена только так мы и работали, и ничего, выжили, не помер никто.
Если ваш проектик будет расти, ваша команда тоже, то у вас сначала появится другой программист, который всё это будет делать вместе с вами. Потом вы еще одного наймете, сами при этом сконцентрируетесь на архитектуре, управлении командой и всё еще на сборе требований, и всё еще будете программистом. А через какое-то время уже и девочку в очках с блокнотиком наймете. Как раз на сбор требований.
Специализация, она вот такая. Девочка эта не будет вам писать код, но она будет собирать требования, писать техзадания и формализовать алгоритмы. Вы её будете называть аналитиком, но по сути, она просто будет выполнять коммуникационную/бюрократическую часть работы программиста. Потому что забрать её у разработчиков и сфокусировать их только на написании кода — это таки да, здорово повышает их производительность.
Если вы делаете проект (хорошо, назовем его «проектик», а то некоторые начинают воротить нос, если слышат слово «проект» в отношении работы, которая делается командой меньше десяти человек и стоит меньше пары миллионов денег) в одиночку, вы будете собирать полные и непротиворечивые требования, и никуда от этого не денетесь, потом будете разрабатывать архитектуру, потом будете непосредственно программировать, потом тестировать, потом деплоить на продакшен. И всё это будет вашей работой программиста, и у вас будет время и на первое, и на второе, и на десятое. Когда-то в былые времена только так мы и работали, и ничего, выжили, не помер никто.
Если ваш проектик будет расти, ваша команда тоже, то у вас сначала появится другой программист, который всё это будет делать вместе с вами. Потом вы еще одного наймете, сами при этом сконцентрируетесь на архитектуре, управлении командой и всё еще на сборе требований, и всё еще будете программистом. А через какое-то время уже и девочку в очках с блокнотиком наймете. Как раз на сбор требований.
Специализация, она вот такая. Девочка эта не будет вам писать код, но она будет собирать требования, писать техзадания и формализовать алгоритмы. Вы её будете называть аналитиком, но по сути, она просто будет выполнять коммуникационную/бюрократическую часть работы программиста. Потому что забрать её у разработчиков и сфокусировать их только на написании кода — это таки да, здорово повышает их производительность.
Если вы делаете проект (хорошо, назовем его «проектик», а то некоторые начинают воротить нос, если слышат слово «проект» в отношении работы, которая делается командой меньше десяти человек и стоит меньше пары миллионов денег) в одиночку
… то то, что я делаю, не называется работой аналитика. А называется "сделаю проектик в одиночку".
вы будете собирать полные и непротиворечивые требования
Нет, не буду. Зачем?
(btw, нельзя собрать полные и непротиворечивые требования, можно только создать документ с такими требованиями)
Когда-то в былые времена только так мы и работали
Я не знаю, какие "вы" только так и работали, а я вот никогда так не работал. И судя по тому, что литература по работе с требованиями как отдельной дисциплине существует дольше, чем я работаю в отрасли, это не вчера началось.
Ну и да, если в каких-то командах роли совмещаются, это не значит, что все эти роли являются подмножеством одной области работы. Если я на том же проектике завел себе ИП, беру с людей деньги и веду финансовую отчетность — это никак не значит, что работа бухгалтера тоже является частью области работы программиста.
> … то то, что я делаю, не называется работой аналитика.
Почему это не называется? Именно так и называется. Проводя анализ, вы делаете работу аналитика. Если вы вздумаете пойти и подоить корову на ферме в качестве полезной подработки, вы будете делать работу доярки. А если поведете школьный автобус, то будете делать работу водителя школьного автобуса.
> Нет, не буду. Зачем?
Будете. Потому что без этого вы проект не выполните. Я сейчас не про качество вашей работы (удастся вам собрать всё непротиворечивое или не удастся — дело тридесятое), и не про объем (будет там документ на полгода работы или бумажка с тезисами по итогам одного совещания), а про сам факт выполнения такой работы.
> Я не знаю, какие «вы» только так и работали, а я вот никогда так не работал.
Значит, конкретно «вы» или пришли в эту профессию уже в 21 веке, или изначально попали в какой-то центр космических технологий. Поздравляю. А у нас в _этой стране_ в 1990-е годы такое только-только зарождалось, и было редким исключением, а не правилом профессиональной разработки.
> это никак не значит, что работа бухгалтера тоже является частью области работы программиста.
Это несравнимые вещи. Работа бухгалтера, как и доярки, для написания программы не требуется. А вот системный анализ требуется. И человек на должности системного аналитика по своей профессии, в отличии от бухгалтера, тоже программист.
Почему это не называется? Именно так и называется. Проводя анализ, вы делаете работу аналитика. Если вы вздумаете пойти и подоить корову на ферме в качестве полезной подработки, вы будете делать работу доярки. А если поведете школьный автобус, то будете делать работу водителя школьного автобуса.
> Нет, не буду. Зачем?
Будете. Потому что без этого вы проект не выполните. Я сейчас не про качество вашей работы (удастся вам собрать всё непротиворечивое или не удастся — дело тридесятое), и не про объем (будет там документ на полгода работы или бумажка с тезисами по итогам одного совещания), а про сам факт выполнения такой работы.
> Я не знаю, какие «вы» только так и работали, а я вот никогда так не работал.
Значит, конкретно «вы» или пришли в эту профессию уже в 21 веке, или изначально попали в какой-то центр космических технологий. Поздравляю. А у нас в _этой стране_ в 1990-е годы такое только-только зарождалось, и было редким исключением, а не правилом профессиональной разработки.
> это никак не значит, что работа бухгалтера тоже является частью области работы программиста.
Это несравнимые вещи. Работа бухгалтера, как и доярки, для написания программы не требуется. А вот системный анализ требуется. И человек на должности системного аналитика по своей профессии, в отличии от бухгалтера, тоже программист.
Почему это не называется?
Потому что далеко не факт, что я не скипну этот этап полностью, как и любой из остальных.
Проводя анализ, вы делаете работу аналитика.
… но вообще, конечно, эта фраза очень показательна. "Делаете работу аналитика". Не работу программиста, а работу аналитика.
Потому что без этого вы проект не выполните.
Почему?
Значит, конкретно «вы» или пришли в эту профессию уже в 21 веке, или изначально попали в какой-то центр космических технологий.
Нет и нет.
А у нас в _этой стране_ в 1990-е годы такое только-только зарождалось, и было редким исключением, а не правилом профессиональной разработки.
"Этой страной" жизнь не ограничивается, если что. И выработанными здесь правилами (впрочем, уже устаревшими) — тоже.
Работа бухгалтера, как и доярки, для написания программы не требуется. А вот системный анализ требуется.
Нет, системный анализ для написания программы не требуется. Для написания программы нужны требования на входе.
Но представьте себе на минуту, что вы делаете игру. Для нее — иногда — нужен сценарий. Является ли работа сценариста частью работы программиста?
И человек на должности системного аналитика по своей профессии, в отличии от бухгалтера, тоже программист.
А человек на должности художника, рисующего картинки для игры?
Я повторюсь, то, что люди иногда совмещают разные роли, никак не означает, что все эти роли, на самом деле — часть работы программиста.
>> Потому что без этого вы проект не выполните.
> Почему?
Потому что нельзя писать для заказчика программы, не собрав его требований и не вникнув в них. Если вы это не сделаете, заказчик её у вас не купит.
> Нет и нет.
А у вас в профиле написан 1981-й год рождения. Вам было 19 лет, когда начался 21 век. Так что где-то вы врёте. Подозреваю, врёте сейчас, ибо вы-то ввязались в спор, ну а как же человек с тегом «Архитектор» в профиле может согласиться с чужим мнением, будь оно хоть трижды аргументированным? ;)
> «Этой страной» жизнь не ограничивается, если что
Полагаю, ни мне, ни кому-либо из других читателей форума факт вашей эмиграции не интересен. Тем более раз если вас отсюда увезли папа с мамой в юности, и вы не в курсе, как тут велась разработка ПО, то хотя бы на слово поверьте, а не спорьте.
> Нет, системный анализ для написания программы не требуется. Для написания программы нужны требования на входе.
Требуется. Как только вы садитесь, и думаете, как написать программу, чтобы она соответствовала требованиям на входе, вы уже проводите системный анализ.
> Я повторюсь, то, что люди иногда совмещают разные роли, никак не означает, что
> все эти роли, на самом деле — часть работы программиста.
Конечно же, не означает. Часть работы программиста — анализ, разработка архитектуры, написание кода, тестирование, т.е. все те работы, которые выполняют сотрудники с квалификацией программиста. Рисование картинок и продажа софта, это не часть работы программиста.
> Почему?
Потому что нельзя писать для заказчика программы, не собрав его требований и не вникнув в них. Если вы это не сделаете, заказчик её у вас не купит.
> Нет и нет.
А у вас в профиле написан 1981-й год рождения. Вам было 19 лет, когда начался 21 век. Так что где-то вы врёте. Подозреваю, врёте сейчас, ибо вы-то ввязались в спор, ну а как же человек с тегом «Архитектор» в профиле может согласиться с чужим мнением, будь оно хоть трижды аргументированным? ;)
> «Этой страной» жизнь не ограничивается, если что
Полагаю, ни мне, ни кому-либо из других читателей форума факт вашей эмиграции не интересен. Тем более раз если вас отсюда увезли папа с мамой в юности, и вы не в курсе, как тут велась разработка ПО, то хотя бы на слово поверьте, а не спорьте.
> Нет, системный анализ для написания программы не требуется. Для написания программы нужны требования на входе.
Требуется. Как только вы садитесь, и думаете, как написать программу, чтобы она соответствовала требованиям на входе, вы уже проводите системный анализ.
> Я повторюсь, то, что люди иногда совмещают разные роли, никак не означает, что
> все эти роли, на самом деле — часть работы программиста.
Конечно же, не означает. Часть работы программиста — анализ, разработка архитектуры, написание кода, тестирование, т.е. все те работы, которые выполняют сотрудники с квалификацией программиста. Рисование картинок и продажа софта, это не часть работы программиста.
Потому что нельзя писать для заказчика программы, не собрав его требований и не вникнув в них. Если вы это не сделаете, заказчик её у вас не купит.
Вы не поверите, но можно. Вопрос агрессивности продажи. А еще можно писать не для заказчика, а свой собственный проект.
А у вас в профиле написан 1981-й год рождения. Вам было 19 лет, когда начался 21 век. Так что где-то вы врёте.
Вы считаете, что люди до 19 лет не работают?
Полагаю, ни мне, ни кому-либо из других читателей форума факт вашей эмиграции не интересен.
А при чем тут эмиграция? Я говорю о том, что практики индустрии формируются не в одной стране.
Как только вы садитесь, и думаете, как написать программу, чтобы она соответствовала требованиям на входе, вы уже проводите системный анализ.
Почему вы считаете, что это системный анализ, а не проектирование?
Часть работы программиста — анализ, разработка архитектуры, написание кода, тестирование, т.е. все те работы, которые выполняют сотрудники с квалификацией программиста.
Если сотрудник с квалификацией программиста рисует картинки, является ли рисование картинок частью работы программиста?
> Вы не поверите, но можно. Вопрос агрессивности продажи
Скорее вопрос чистоты «на руку» как контрагента. Если вы не планируете решить задачу заказчика, а просто убедить его, получить предоплату, а дальше — хоть трава не расти, то да, можно. И свой собственный проект можно. Только свой собственный — это не для заказчика. Только какое отношение это имеет к вопросу? Конечно же, из сотни задач вы можете найти одну, которую вы напишете сразу, без анализа. Например, потому что вы это решали.
> Вы считаете, что люди до 19 лет не работают?
Не, я читал в детстве книжку «Сын полка». Бывают исключения. Вас сразу после школы куда взяли сыном полка, в Oracle или Microsoft?
> Я говорю о том, что практики индустрии формируются не в одной стране.
Ну так вы не в эмиграции были, а где-то в СНГ? И в 90-е годы? И в 19 лет? И у вас на предприятии использовалась полноценная современная методика разработки? Ну пусть не совсем современная, пусть не эджайл, но хотя бы водопадец?
Я же говорю, врёте. :)
>Почему вы считаете, что это системный анализ, а не проектирование?
О, коллега, вы сейчас вообще удивитесь, наверное. Конечно, если этот разговор завели ради какого-то смысла, а не чтобы переспорить оппонента ради самого «переспорить», что, судя по вашей манере отвечать, вполне вероятно. Так вот, системный анализ это еще и часть процесса проектирования ;)
> Если сотрудник с квалификацией программиста рисует картинки,
> является ли рисование картинок частью работы программиста?
Ему нужна квалификация программиста для рисования картинок?
Скорее вопрос чистоты «на руку» как контрагента. Если вы не планируете решить задачу заказчика, а просто убедить его, получить предоплату, а дальше — хоть трава не расти, то да, можно. И свой собственный проект можно. Только свой собственный — это не для заказчика. Только какое отношение это имеет к вопросу? Конечно же, из сотни задач вы можете найти одну, которую вы напишете сразу, без анализа. Например, потому что вы это решали.
> Вы считаете, что люди до 19 лет не работают?
Не, я читал в детстве книжку «Сын полка». Бывают исключения. Вас сразу после школы куда взяли сыном полка, в Oracle или Microsoft?
> Я говорю о том, что практики индустрии формируются не в одной стране.
Ну так вы не в эмиграции были, а где-то в СНГ? И в 90-е годы? И в 19 лет? И у вас на предприятии использовалась полноценная современная методика разработки? Ну пусть не совсем современная, пусть не эджайл, но хотя бы водопадец?
Я же говорю, врёте. :)
>Почему вы считаете, что это системный анализ, а не проектирование?
О, коллега, вы сейчас вообще удивитесь, наверное. Конечно, если этот разговор завели ради какого-то смысла, а не чтобы переспорить оппонента ради самого «переспорить», что, судя по вашей манере отвечать, вполне вероятно. Так вот, системный анализ это еще и часть процесса проектирования ;)
> Если сотрудник с квалификацией программиста рисует картинки,
> является ли рисование картинок частью работы программиста?
Ему нужна квалификация программиста для рисования картинок?
Только какое отношение это имеет к вопросу?
Да прямое, в общем-то. Речь же шла о том, без чего нельзя выполнить проект.
Вас сразу после школы куда взяли сыном полка, в Oracle или Microsoft?
Ни то, ни другое (заодно и ни третье, ни четвертое, потому что не сразу после школы и не сыном полка). Но вообще, в резюме все написано.
Ну так вы не в эмиграции были, а где-то в СНГ? И в 90-е годы? И в 19 лет? И у вас на предприятии использовалась полноценная современная методика разработки? Ну пусть не совсем современная, пусть не эджайл, но хотя бы водопадец?
Москва, 90-ые годы, 17-18 и далее лет, "водопадец", ага. Учитывая, что водопаду к этому моменту никак не меньше 30 лет (окей, термину — не меньше 20) — ничего удивительного, правда же?
Я же говорю, врёте
Если вы чего-то не видели, это еще не значит, что описывающий врет.
Так вот, системный анализ это еще и часть процесса проектирования
Ага, выстраивается иерархия. Проектирование — часть разработки, анализ — часть проектирования. И все это — обязанности программиста.
Ему нужна квалификация программиста для рисования картинок?
А для сбора и формализации требований с заказчика нужна квалификация программиста?
> Да прямое, в общем-то. Речь же шла о том, без чего нельзя выполнить проект.
Я прошу прощения, но мы же с вами не юридические условия договора обсуждаем. Мне грешным делом подумалось, что вы в состоянии без лишних уточнений с моей стороны понять, что если говорится «нельзя выполнить проект», то речь идет об общем правиле, а не об абсолютном законе. И что, естественно, найти какие-то единичные исключения из любого правила при желании можно. По крайней мере, этот момент очевиден.
> ничего удивительного, правда же?
Ну кроме того вопроса, кому и зачем мог в профессиональной разработке софта понадобиться 17-летний подросток.
> Если вы чего-то не видели, это еще не значит, что описывающий врет.
Если я не видел, не значит. Если оно противоречит общему тренду, то значит, пока не получены подтверждения обратного.
> А для сбора и формализации требований с заказчика нужна квалификация программиста?
Нужна, естественно, хотя бы на базовом уровне. Иначе формализация будет такой, что программист там мозг взорвет.
Я прошу прощения, но мы же с вами не юридические условия договора обсуждаем. Мне грешным делом подумалось, что вы в состоянии без лишних уточнений с моей стороны понять, что если говорится «нельзя выполнить проект», то речь идет об общем правиле, а не об абсолютном законе. И что, естественно, найти какие-то единичные исключения из любого правила при желании можно. По крайней мере, этот момент очевиден.
> ничего удивительного, правда же?
Ну кроме того вопроса, кому и зачем мог в профессиональной разработке софта понадобиться 17-летний подросток.
> Если вы чего-то не видели, это еще не значит, что описывающий врет.
Если я не видел, не значит. Если оно противоречит общему тренду, то значит, пока не получены подтверждения обратного.
> А для сбора и формализации требований с заказчика нужна квалификация программиста?
Нужна, естественно, хотя бы на базовом уровне. Иначе формализация будет такой, что программист там мозг взорвет.
Нужна, естественно, хотя бы на базовом уровне.
Странно, почему в Вигерсовских Software Requirements (я смотрю на второе издание, 2003 год) в списке скилов Requirement Analyst (с. 68-70) есть listening, interviewing/questioning, analytical, facilitation, observational, writing, organizational, modeling, interpersonal и creativity, но нет ничего, связанного с программированием?
Ну и оттуда же хорошая цитата: "Project managers who lack a dedicated requirements analyst often expect a developer to do the job. Unfortunately, the skills and personality needed for requirements development aren’t the same as those needed for software development." (с. 72)
Здесь нет противоречий тому, что я говорю. Абсолютно верно, для сбора требований нужны скиллы коммуникаций, и не нужны скиллы знания Java. Моделирование, аналитика — это та самая смежная часть, где требования превращаются в спецификацию, понятную ИТ-разработчку.
> Unfortunately, the skills and personality needed for requirements development
> aren’t the same as those needed for software development
Здесь речь идет о том, что не стоит пересаживать на сбор требований человека из разработки. Это тоже верно и не противоречит вышесказанному.
А теперь вы лучше скажите, если вам в команду понадобится молодой аналитик с целью «выучить и получить отдачу», где вы его будете брать? Какого он будет профессионального профиля, из какого учебного заведения?
> Unfortunately, the skills and personality needed for requirements development
> aren’t the same as those needed for software development
Здесь речь идет о том, что не стоит пересаживать на сбор требований человека из разработки. Это тоже верно и не противоречит вышесказанному.
А теперь вы лучше скажите, если вам в команду понадобится молодой аналитик с целью «выучить и получить отдачу», где вы его будете брать? Какого он будет профессионального профиля, из какого учебного заведения?
Абсолютно верно, для сбора требований нужны скиллы коммуникаций, и не нужны скиллы знания Java
Так где же квалификация программиста-то в этих скиллах?
Моделирование, аналитика — это та самая смежная часть
Аналитические навыки, в терминах Вигерса, совсем не об этом:
An effective analyst can think at multiple levels of abstraction. Sometimes you must drill down from high-level information into details. In other situations, you’ll need to generalize from a specific need that one user described to a set of requirements that will satisfy many members of a user class. Critically evaluate the information gathered from multiple sources to reconcile conflicts, separate user “wants” from the underlying true needs, and distinguish solution ideas from requirements.
Это обобщенный навык, не специфически программный. С моделированием, в принципе, аналогично:
Tools ranging from the venerable flowchart through structured analysis models (data flow diagram, entity-relationship diagram, and the like) to contemporary Unified Modeling Language (UML) notations should be
part of every analyst’s repertoire. Some will be useful when communicating with users, others when communicating with developers. The analyst will need to educate other stakeholders on the value of using these techniques and how to read them.
Здесь речь идет о том, что не стоит пересаживать на сбор требований человека из разработки.
Вам это не кажется нелогичным? "Область работы аналитика является подмножеством области работы программиста", но при этом человека из разработки — программиста — не надо пересаживать на сбор требований, потому что, если верить Вигерсу, у нео другой скилсет. Как же одно может быть подмножеством другого, если скилсет разный?
А теперь вы лучше скажите, если вам в команду понадобится молодой аналитик с целью «выучить и получить отдачу», где вы его будете брать? Какого он будет профессионального профиля, из какого учебного заведения?
В идеале, его образование и/или профессиональный опыт должны коррелировать с предметной областью. Если это сложно — а это чаще всего сложно — то любое высшее (я в этой области, к сожалению, сноб) или высшее-в-процессе. CS100 в анамнезе помогает, но не обязателен.
> Вам это не кажется нелогичным? «Область работы аналитика является
> подмножеством области работы программиста»
Нет. Вы каждый раз в упор игнорируете слово «специализация». Вернитесь в начало разговора, и еще раз прочтите тезисы. Разработчик-кодер — это также дальнейшая специализация программиста. После специализации, абсолютно верно, взаимозаменяемость пропадает.
> подмножеством области работы программиста»
Нет. Вы каждый раз в упор игнорируете слово «специализация». Вернитесь в начало разговора, и еще раз прочтите тезисы. Разработчик-кодер — это также дальнейшая специализация программиста. После специализации, абсолютно верно, взаимозаменяемость пропадает.
Разработчик-кодер — это также дальнейшая специализация программиста.
А почему вы считаете, что Вигерс в приведенной выше цитате под developer понимаете "разработчика-кодера", а не "программиста"?
И почему, тогда уж, вы считаете, что в треде, в котором вы участвуете (или в заголовке статьи, for that reason) слово "программист" употребляется в том смысле, который вы в него вкладываете, а не в каком-то другом?
И где и кем определен тот всемогущий программист, способный выполнить любую фазу водопада, на которого вы ссылаетесь?
Не всегда так. Есть такое понятие "Амортизационный анализ".
Добавлю: и еще есть убывающие геометрические прогрессии, которые запросто могут множитель в оценке времени "скушать".
НЛО прилетело и опубликовало эту надпись здесь
А пришло в программирование это все от того, что большинство computer science-ученых довольно посредственные математики, адекватного инструмента придумано не было, взяли то что учили в университете на первом курсе без особого понимания.
Это вы сейчас Кнута записали в посредственные математики?
НЛО прилетело и опубликовало эту надпись здесь
А вы знаете какие-то известные теоремы доказанные Кнутом?
А это обязательное требование для того, чтобы быть не-посредственным математиком? Вы же говорите о понимании, а не об изобретении нового.
Но вообще, так, на минуточку: "a Fellow (first class of Fellows) of the Society for Industrial and Applied Mathematics in 2009 for his outstanding contributions to mathematics [...] a fellow of the American Mathematical Society."
А ты думаешь, что придумывание алгоритмов и их анализ и доказательство теорем чем-то отличаются?
Попробуй формально докажи, что хеш-таблица имеет время поиска амортизированное O(1). Доказательство не проще центральной предельной теоремы. Кнут доказал теорему о хеш-таблицах.
Ты пользуешься знаниями о вычислительной сложности алгоритмов как будто это само собой разумеющееся. Ты забыл что математики вроде кнута долго доказывали свойства алгоритмов, чтобы ты мог гордо а собеседовании сказать, что сложность быстрой сортировки — NlogN.
Попробуй формально докажи, что хеш-таблица имеет время поиска амортизированное O(1). Доказательство не проще центральной предельной теоремы. Кнут доказал теорему о хеш-таблицах.
Ты пользуешься знаниями о вычислительной сложности алгоритмов как будто это само собой разумеющееся. Ты забыл что математики вроде кнута долго доказывали свойства алгоритмов, чтобы ты мог гордо а собеседовании сказать, что сложность быстрой сортировки — NlogN.
НЛО прилетело и опубликовало эту надпись здесь
Не совсем формальное доказательство асимптотики быстрой сортировки по твоему не сложнее взвешивания монет? Тогда наверное и теорема ферма для тебя — элементарщина.
Да, сейчас многие хотят эту дыру заткнуть какими-то комбинаторными понятиями, амортизационный анализ из той же оперы, но там где начинается комбинаторика, там заканчивается наука.
Т.е. по вашему комбинаторика не является разделом математики? Боюсь что википедия с вами не согласна. Или что вы хотели сказать этой фразой?
Кажется, я нашел закономерность в этой формуле: если убрать O(..) она по прежнему верная.
НЛО прилетело и опубликовало эту надпись здесь
Для практики же полезен бенчмарк, где учитываются статистика данных, реальное количество данных и т.д. Асимптотика вообще может не отражать реальное положение дел.
Может не отражать. А может и отражать.
Рядом со мной сидят веб-программеры, которые одну функцию в одном внутрифирменном сервисе реализовали с квадратичной сложностью, когда данных в базе было мало и всё летало и так. Через год, когда база выросла вдесятеро, а время обработки данных, соответственно, в сто раз, — на этот их сервис чертыхался весь отдел. А уже поздно: на ту структуру данных, которую они выбрали, всё в сервисе завязано, переписывать можно только всё целиком.
Естественно, что "реальное количество данных и их статистику" на этапе разработки сервиса предсказать было невозможно: мы и сами тогда не знали, сколько и чего мы в их базу будем пихать.
Так-то если там убрать O(...), то придется все домножать на константу, которая может быть сколь угодно большой…
Простой пример: можно отсортировать массив из 3-х элементов за честных 1 n^2 операций (т.е. за 9 операций сравнения), а можно линейно за 100 n операций (т.е. за 300 операций сравнения)...
Простой пример: можно отсортировать массив из 3-х элементов за честных 1 n^2 операций (т.е. за 9 операций сравнения), а можно линейно за 100 n операций (т.е. за 300 операций сравнения)...
А ничего, что это асимптотические оценки и алгоритм со сложностью O(N) может быть хуже, чем O(N*logN) на характерной для задачи размерности данных? А если у двух алгоритмов одинаковая O-сложность, то какой из них предпочтительней? Если программист — программист, то он знает, как алгоритмы грамотно сравнивать. Если программист — дилетант от программирования, то он берет решение наугад, как привык или как посоветовали.
Думаю, разработчику очень полезно хорошо представлять как пишутся алгоритмы, какие бывают структуры, как они работают, наверное даже без нюансов реализации, т.е. ему не нужно уметь написать реализацию на листочке, но иметь представление важно для абстрактного представления как работает то, чем он пользуется. Для 80% (цифра взята из закона Парето) случаев вообще нечего такого не понадобится (по ощущению же это цифра еще больше, может быть 95% для рядовой разработки), но зато оставшиеся случаи потребуют от разработчика хорошего понимания как работают его инструменты, чтобы сделать правильно/быстро/разобраться с проблемой. Вот здесь-то непонимающий разработчик и потратит 80% своего времени (опять смотрим на Парето) — на что будет потрачено это время? 1) Разработчик всё-таки разберется как что устроено 2) будет пытаться обойти проблему в поисках на стековерфлоу рабочего решения. Как можно догадаться, первый вариант быстро перейдет из непонимающего в понимающего, второй же скорее всего всегда будет пользоваться вторым способом. Отсюда можно сделать вывод, что важно не столько понимать все инструменты, которыми ты пользуешься (а все знать невозможно), но быть мотивированным на их исследование.
Вы (автор статьи), возможно, имеете ввиду то, что в большинстве отраслей и для большинства задач они не нужны.
Однако, они нужны в отраслях бизнеса, связанных с математикой и вычислениями. Например, разработка микропроцессоров или google cars (кейс моего приятеля JAVA-программиста). В случае, когда необходимо разрабатывать именно новые математические алгоритмы на основе существующих.
А так, согласен с Вами. С точки зрения практики — зачем досконально знать алгоритмы в прикладных задачах? Это вдоль и поперек изученная теория, прекрасно (хотелось бы верить) реализованная в готовых библиотеках. Например, у JAVA таких библиотек огромное количество.
Однако, они нужны в отраслях бизнеса, связанных с математикой и вычислениями. Например, разработка микропроцессоров или google cars (кейс моего приятеля JAVA-программиста). В случае, когда необходимо разрабатывать именно новые математические алгоритмы на основе существующих.
А так, согласен с Вами. С точки зрения практики — зачем досконально знать алгоритмы в прикладных задачах? Это вдоль и поперек изученная теория, прекрасно (хотелось бы верить) реализованная в готовых библиотеках. Например, у JAVA таких библиотек огромное количество.
Вот да. Теорию и я люблю и трачу на это все свободное время. Но практика и рынок диктую другие правила.
Вы просто находитесь в части рынка, в которой умение писать алгоритмы, которые лазят по графам и деревьям — это неважно.
Я более 20 лет находился в части рынка, где без этого невозможно работать (сначала компиляторы, потом средства проектирования электроники). Вы не можете разрабатывать программы типа Synopsys VCS (я работал в этой группе) без таких навыков. Заработные платы в таких местах существенно выше, чем в среднем по индустрии.
Так что "практика и рынок", если вам нравятся работы такого типа, диктует противоположное.
Я более 20 лет находился в части рынка, где без этого невозможно работать (сначала компиляторы, потом средства проектирования электроники). Вы не можете разрабатывать программы типа Synopsys VCS (я работал в этой группе) без таких навыков. Заработные платы в таких местах существенно выше, чем в среднем по индустрии.
Так что "практика и рынок", если вам нравятся работы такого типа, диктует противоположное.
Нужно ли кому-то что-то знать больше в его профессии?
1) Если подумать, почему бы и нет, любые знания всегда хорошо, особенно близкие — буду расти как специалист.
2) Но с другой стороны, если я 1С ник, нафига мне машины Больцамана… учиться ловить драконов можно всю жизнь но нафига.
3) Получается, нужно плясать от смысла, какую задачу я хочу решить, что я планирую?
4) А откуда я знаю что я буду делать завтра? Метеорит упадет и все. Кому нужен этот 1С. Но так как это маловероятно, я буду предполагать что вероятно.
5) А вероятно, может быть много чего, жизней не хватит. Все равно цель то не познание вероятности, а максимальный результат от моей деятельности рассчитанный вероятностно. Я же не рассчитываю всю жизнь за учебниками просидеть.
6) Похоже цель — деньги, семья, самореализация, отдых и т.п ну да да вот оно и чтобы стабильно и уверенность в завтрашнем дне.
7) Так, получается меня толкает на все это экзистенциальный страх неизвестного.
8) Если это так то мне просто нужно убрать страх и мне будет хорошо. Можно попробовать химически с помощью там всяких веществ.
9) Не ну, вещества это все равно не то, это просто бегство. Вот хочу как у Васи. Я считаю Васю успешным — личностью.
Чем отличается личность от индивидуальности? Тем что первая нашла свои машины больцмана или свои рецепты для борьбы со страхом, который никогда не пропадает заставляя нас копаться глубже, так как будущее все равно неизвестно, но благодаря которым, мы не цепенеем как пенсионеры перед смарфоном
1) Если подумать, почему бы и нет, любые знания всегда хорошо, особенно близкие — буду расти как специалист.
2) Но с другой стороны, если я 1С ник, нафига мне машины Больцамана… учиться ловить драконов можно всю жизнь но нафига.
3) Получается, нужно плясать от смысла, какую задачу я хочу решить, что я планирую?
4) А откуда я знаю что я буду делать завтра? Метеорит упадет и все. Кому нужен этот 1С. Но так как это маловероятно, я буду предполагать что вероятно.
5) А вероятно, может быть много чего, жизней не хватит. Все равно цель то не познание вероятности, а максимальный результат от моей деятельности рассчитанный вероятностно. Я же не рассчитываю всю жизнь за учебниками просидеть.
6) Похоже цель — деньги, семья, самореализация, отдых и т.п ну да да вот оно и чтобы стабильно и уверенность в завтрашнем дне.
7) Так, получается меня толкает на все это экзистенциальный страх неизвестного.
8) Если это так то мне просто нужно убрать страх и мне будет хорошо. Можно попробовать химически с помощью там всяких веществ.
9) Не ну, вещества это все равно не то, это просто бегство. Вот хочу как у Васи. Я считаю Васю успешным — личностью.
Чем отличается личность от индивидуальности? Тем что первая нашла свои машины больцмана или свои рецепты для борьбы со страхом, который никогда не пропадает заставляя нас копаться глубже, так как будущее все равно неизвестно, но благодаря которым, мы не цепенеем как пенсионеры перед смарфоном
Согласен. Себя нужно научиться уважать и понять, что важное в жизни — устроено просто :-)
От невозможности определить реальность математически абстракциями и вероятностями (только потому что они не знают че так тоже можно :-) ), многие прибегают к гадалкам и шоу эксрасенсов. Тоже борются с экзистенциальным страхом. Однако, если мы задумаемся, то все важные вещи в нашей жизни были совершенны иррационально.
Случайные встречи, случайные связи. Математика это не устраивает — потому что рандом ненадежно, он он все равно вынужденно руководствуется внутренним чутьем. Это в нас как то заложено — магия эта.
Касаемо этого, для меня неожиданно, в другом ключе открылся смысл магического мышления,, — определенного дедушкой Фрейдом в "татеме и табу".
Монтировал вчера эту лекцию, и мне понравились несогласия с дедушкой Ф.)
Случайные встречи, случайные связи. Математика это не устраивает — потому что рандом ненадежно, он он все равно вынужденно руководствуется внутренним чутьем. Это в нас как то заложено — магия эта.
Касаемо этого, для меня неожиданно, в другом ключе открылся смысл магического мышления,, — определенного дедушкой Фрейдом в "татеме и табу".
Монтировал вчера эту лекцию, и мне понравились несогласия с дедушкой Ф.)
Уважаемые читатели!
Было бы обалденно, если бы кто-нибудь рассказал о своих кейсах из рабочей практики. Речь не о том, что они "развивают мышление". Это бесспорно. Расскажите случаи, когда вам действительно очень помогло знание алгоритмов — насколько удалось поднять производительность/сэкономить ресурсов и т.п.
У меня таких кейсов, к сожалению нет. Зато есть кейсы успешного применения прикладных знаний, наподобие оптимизации баз данных. И до сих пор есть задачи, требующие углубления именно практических знаний, а вовсе не теорий алгоритмов.
В условиях хронического недостатка времени приходится делать выбор в пользу развития прикладных знаний.
Было бы обалденно, если бы кто-нибудь рассказал о своих кейсах из рабочей практики. Речь не о том, что они "развивают мышление". Это бесспорно. Расскажите случаи, когда вам действительно очень помогло знание алгоритмов — насколько удалось поднять производительность/сэкономить ресурсов и т.п.
У меня таких кейсов, к сожалению нет. Зато есть кейсы успешного применения прикладных знаний, наподобие оптимизации баз данных. И до сих пор есть задачи, требующие углубления именно практических знаний, а вовсе не теорий алгоритмов.
В условиях хронического недостатка времени приходится делать выбор в пользу развития прикладных знаний.
у меня был кейс, один за 15 лет :-)
А в какой области Вы работаете и какие задачи обычно решаете/решали?
Мы делали рекомендательную систему и кластеризовали каталог товаров. Много математики, чуть меньше алгоритмов — но классические не работали на больших данных, пришлось копать глубже и переделывать на MapReduce :-) Вот ссылочка.
Кейс — замаскировать url. Впрочем, я фронт-эндер, задача была не моя, но я помогал решать. Пока бэк-энд пытались придумать супер-убер архитектуру хранения с очисткой старых данных из бд и id, я просто предложил воспользоваться обратимыми алгоритмами хеширования.
Еще один кейс был — хранить большое количество чисел (посещал-не посещал). Покуда это нужно было хранить для каждого пользователя по-отдельности, хранить влоб отвратительная идея (мало того, что только и успевай жесткие диски подсовывать, так еще это нужно как-то искать).
Вообще часто замечаю, что последнее время простенькие задачи пытаются решить сотней-другой гемов (gem), парой БД и диким оверхедом, вместо того, чтобы немного подумать и сделать простое, быстрое и изящное решение. Не то, чтобы не знали алгоритмов, просто забыли и отвыкли их использовать. Слишком уж редко нужно применять в реальности, что невольно первыми в голову лезут идеи найти библиотеку.
Еще один кейс был — хранить большое количество чисел (посещал-не посещал). Покуда это нужно было хранить для каждого пользователя по-отдельности, хранить влоб отвратительная идея (мало того, что только и успевай жесткие диски подсовывать, так еще это нужно как-то искать).
Вообще часто замечаю, что последнее время простенькие задачи пытаются решить сотней-другой гемов (gem), парой БД и диким оверхедом, вместо того, чтобы немного подумать и сделать простое, быстрое и изящное решение. Не то, чтобы не знали алгоритмов, просто забыли и отвыкли их использовать. Слишком уж редко нужно применять в реальности, что невольно первыми в голову лезут идеи найти библиотеку.
Думаю, здесь нельзя разделить на такой/нетакой кейс. Конечно, если говорить о кандово-математическом процессе создания алгоритмов, то думаю разработчик который не занимается этим непосредственно может и обойтись без таких знаний и умений. Однако, если говорить о представлении того как работают те алгоритмы и структуры, которыми ты пользуешься, то тут совсем другая ситуация. Потому что каждый раз используя что-то из стандартной библиотеки ты можешь сделать это осознанно, выбирая этот способ и понимая, что за собой это может повлечь, или просто потому что обычно делают так.
Года три назад, делал систему автоматического определения оптимального передвижения техники по корпусу во время технического обслуживания электролизеров на алюминиевом заводе. По большому счету это NP задача, но она была сведена к достаточно приемлемому алгоритму на базе алгоритма Дейкстры — поиска кратчайшего пути в графе. Работает очень быстро. Так получилось, что из всей команды опыт в алгоритмах был только у меня и делал эту задачу соответсвенно один.
Там же занимался базами данных и понимание сложности очень помогало при профилировании запросов к базе / переписывании меделенных sql-запросов.
Сейчас на текущей работе участвую в разработке WebGL-приложения. Не сказать, что каждый день используются какие-то хитрые алгоритмы, в основном математика, но буквально вчера коллега реализовал дельта-кодирование вершин, что позволило сэкономить объем передаваемых данных на 30%. Алгоритм простой, но не зная его не получилось бы экономии трафика.
Еще друг показывал тестовое задание, которое он решал — по сути это быстрый саггестер для заданного набора строк. Прямолинейное решение O(n) с использованием сбалансированного дерева O(log n).
В общем, мое капитанское мнение такое. Не зная алгоритмы можно кодить и кодить довольно хорошо. Но зная алгоритмическую базу, математику, открывается абсолютно новый класс задач, которые программист без профильных знаний решить, увы, не сможет.
Там же занимался базами данных и понимание сложности очень помогало при профилировании запросов к базе / переписывании меделенных sql-запросов.
Сейчас на текущей работе участвую в разработке WebGL-приложения. Не сказать, что каждый день используются какие-то хитрые алгоритмы, в основном математика, но буквально вчера коллега реализовал дельта-кодирование вершин, что позволило сэкономить объем передаваемых данных на 30%. Алгоритм простой, но не зная его не получилось бы экономии трафика.
Еще друг показывал тестовое задание, которое он решал — по сути это быстрый саггестер для заданного набора строк. Прямолинейное решение O(n) с использованием сбалансированного дерева O(log n).
В общем, мое капитанское мнение такое. Не зная алгоритмы можно кодить и кодить довольно хорошо. Но зная алгоритмическую базу, математику, открывается абсолютно новый класс задач, которые программист без профильных знаний решить, увы, не сможет.
Спасибо за кейс!
По поводу нового класса задач идея такая. Время у всех катастрофически ограничено. И ежедневно (а то и чаще) возникает вопрос "что учить, куда развиваться?" И выбор — либо углубиться наконец-то в алгоритмы, либо изучить что-то новое в прикладном плане.
Новый класс задач открывается и при изучении алгоритмов, и при изучении новых прикладных методов (например, новых языков программирования или баз данных).
То есть незнание алгоритмов могут сильно тормозить программиста в областях, которые Вы описали.
Но другого программиста в другой области может тормозить незнание прикладных решений. Которые он не знает, потому что потратил время на изучение алгоритмов.
Наверное, так.
По поводу нового класса задач идея такая. Время у всех катастрофически ограничено. И ежедневно (а то и чаще) возникает вопрос "что учить, куда развиваться?" И выбор — либо углубиться наконец-то в алгоритмы, либо изучить что-то новое в прикладном плане.
Новый класс задач открывается и при изучении алгоритмов, и при изучении новых прикладных методов (например, новых языков программирования или баз данных).
То есть незнание алгоритмов могут сильно тормозить программиста в областях, которые Вы описали.
Но другого программиста в другой области может тормозить незнание прикладных решений. Которые он не знает, потому что потратил время на изучение алгоритмов.
Наверное, так.
Похоже что знание алгоритмов вероятнее всего пригодится при написании специализированного софта. И мало вероятно в задачах "запилите мне сайтик/магазин" (если конечно не грезить хайлоадом)
я сейчас переписываю систему, которая ищет объекты в базе в заданном радиусе от пользователя.
Старая версия: сходить в базу, ограничить зону поиска квадратом, отсортировать по радиусу, и затем полученные данные фильтруются в приложении по еще нескольким критериям. Вся эта подготовка занимает примерно 250мс
Новая версия: выгрузить все гео-объекты в память, положить в RTree, искать в нем. Время сократилось до 0.5мс
не всегда нужно знать, как все работает внутри, но было бы неплохо знать о существовании альтернативных алгоритмов
Старая версия: сходить в базу, ограничить зону поиска квадратом, отсортировать по радиусу, и затем полученные данные фильтруются в приложении по еще нескольким критериям. Вся эта подготовка занимает примерно 250мс
Новая версия: выгрузить все гео-объекты в память, положить в RTree, искать в нем. Время сократилось до 0.5мс
не всегда нужно знать, как все работает внутри, но было бы неплохо знать о существовании альтернативных алгоритмов
1) В базе использовались индексы?
2) Количество объектов какое?
3) Как часто меняются объекты?
2) Количество объектов какое?
3) Как часто меняются объекты?
конечно, индексы использовались, но все в индекс не запихнешь
~250к
почти не меняются, иногда добавляются новые, сразу после добавления вероятность изменения больше
~250к
почти не меняются, иногда добавляются новые, сразу после добавления вероятность изменения больше
А что за база?
С таким временем ответа не уверен, что индексы были задействованы ил были эффективны.
В SQL Server есть geospatial indexes, те же самые RTree.
Если встроенных в базу нет, то имеет смысл свой аналог сделать, дописав в каждой вершине индекс "области" и сделать обычный индекс по областям.
С таким временем ответа не уверен, что индексы были задействованы ил были эффективны.
В SQL Server есть geospatial indexes, те же самые RTree.
Если встроенных в базу нет, то имеет смысл свой аналог сделать, дописав в каждой вершине индекс "области" и сделать обычный индекс по областям.
postgres, скорее индексы были не эффективны
http://postgis.net/ не использовали?
где-то использовали, но точно не в этом месте)
создал постгисовский идекс на тестовой базе, простой запрос типа
выполняется 12мс, с десятком джойнов будет значительно медленнее
select count(*) from geo_table where ST_DWithin(geo_point, ST_Point(user_lng, user_lat)::GEOGRAPHY, 25000)выполняется 12мс, с десятком джойнов будет значительно медленнее
"Значительно" это сколько? Еще 10мс? Все равно лучше, чем 250.
И зачем вам десяток джоинов?
И зачем вам десяток джоинов?
лучше, конечно, чем 250, но все равно в памяти быстрее, да и rtree-либой пользоваться намного проще
зачем — потому что база большая, нужно кучу инфы собрать
зачем — потому что база большая, нужно кучу инфы собрать
А это уже неважно. Все что меньше 100мс для пользователя моментально. При этом база масштабируется получше.
База может и большая, но для вывода списка ближайших объектов нет необходимости делать 10 джоинов, даже два джоина для такой задачи — перебор.
Проще, чем дописать запрос к базе? Простите, но не верю.
База может и большая, но для вывода списка ближайших объектов нет необходимости делать 10 джоинов, даже два джоина для такой задачи — перебор.
rtree-либой пользоваться намного проще
Проще, чем дописать запрос к базе? Простите, но не верю.
Как-то раз возникла задача попарного сравнения некоторых объектов и поиска определенных пар, сложности, соответственно, О(n^2). Т.к. количество объектов было неприлично большим, то решение в лоб работало слишком медленно. Пораскинув мозгами, сделали вывод, что объекты можно не сравнивать после их получения, а построить нужные пары сразу. Казалось бы, задача свелась аж к NP-полной, но на многих кейсах ускорение было с десятков минут до нескольких секунд. Само решение опирается на Boolean SAT. Где б мы были без теоретической подготовки...
Классный кейс. А мы прикрутили в этом случае LSH.
У нас пары могут состоять из разных объектов. К примеру, как элементы паззла — чтобы проверить, подходят ли друг другу кусочки, нужно вот прям взять их и попробовать соединить. Если все сошлось — сохраняем, если нет — идем дальше. Вот только в нашем контексте в итоге оказалось, что можно сгенерировать не отдельные элементы, а сразу все пары, без дальнейших проверок.
Из может смежной области мне очень нравится подзабытый алгоритм Блюм-фильтрации.
У меня был прикольный случай. Я в 1996-2001 сделал стартап по написанию транслятора из C в Verilog ( https://en.wikipedia.org/wiki/C_Level_Design ), в нем бОльшая часть кода — это всякие алгоритмические преобразования деревьев и графов, все на С++. В некоторый момент я нанял одного товарища, начинающего Java-программиста, писать GUI. К коду транслятора как такового товарищ не прикасался, и когда я через пару лет как-то стал говорить с ним на абстрактные темы, я столкнулся с тем, что он был свято уверен, что я просто использую какой-то "компиляторный API" написанный другими. Конечно, есть всякие вспомогательные тулы от других вендоров (Yacc, Lex, лицензируемые фронт-энды), но они в таких проектах — это типа 5% кода, а самые интересные алгоритмы по работе с структурами данных нужно самому придумывать.
Или например — в 1991-1993 работал в компании в области Optical Character Recognition (распознавание текстов). Там тоже куча алгоритмов самого разного типа — анализ топологии (topological feature extraction) например.
[Сейчас из софтверного инженера стал хардверным инженером по верификации микропроцессора — тут другие проблемы]
Или например — в 1991-1993 работал в компании в области Optical Character Recognition (распознавание текстов). Там тоже куча алгоритмов самого разного типа — анализ топологии (topological feature extraction) например.
[Сейчас из софтверного инженера стал хардверным инженером по верификации микропроцессора — тут другие проблемы]
Был довольно простой кейс (C#, WinForms). Дерево с фильтром. Если пользователь что-то вводит в фильтре, то остаются только элементы, в названии которых есть такой текст. Остальные скрываются (кроме родительских групп — чтобы было видно структуру дерева). Элементы хранятся в виде обычного списка, у элемента есть его ID и ID его родителя (если не корневой).
Потребовалось вручную просчитывать состояния чекбоксов (3 состояния), т.к. нужно было, чтобы когда пользователь отмечал чекбокс, то отмечались только видимые элементы, а когда пользователь снимал чекбокс, то снимать со всех элементов в том числе со скрытых фильтром.
Делалось это очень просто — в цикле/рекурсии, бегая по списку в поисках родителей/детей для вычисления состояния чекбокса.
Всё работало замечательно пока в дереве были тестовые данные (100-200 элементов). Но когда стали отображаться реальные данные (6000-7000 элементов), то пересчёт чекбоксов стал занимать 300-400 мс, что непростительно долго для простого нажатия на чекбокс.
Переделал пересчёт с использованием хэш-таблицы (HashSet в .NET) — перед рассчётом состояний чекбоксов сначала делался один проход по списку элементов и составлялись хэш-таблицы кто чей родитель и дочерний элемент, кто показывается а кто скрыт фильтром и т.д.
В результате без изменения остального алгоритма время сократилось с 300-400 мс до 1-3 мс.
Кейс не совсем конечно на знание алгоритмов, и даже наверное не на структуру данных, а скорее просто на понимание как это устроено. Но тем не менее.
Потребовалось вручную просчитывать состояния чекбоксов (3 состояния), т.к. нужно было, чтобы когда пользователь отмечал чекбокс, то отмечались только видимые элементы, а когда пользователь снимал чекбокс, то снимать со всех элементов в том числе со скрытых фильтром.
Делалось это очень просто — в цикле/рекурсии, бегая по списку в поисках родителей/детей для вычисления состояния чекбокса.
Всё работало замечательно пока в дереве были тестовые данные (100-200 элементов). Но когда стали отображаться реальные данные (6000-7000 элементов), то пересчёт чекбоксов стал занимать 300-400 мс, что непростительно долго для простого нажатия на чекбокс.
Переделал пересчёт с использованием хэш-таблицы (HashSet в .NET) — перед рассчётом состояний чекбоксов сначала делался один проход по списку элементов и составлялись хэш-таблицы кто чей родитель и дочерний элемент, кто показывается а кто скрыт фильтром и т.д.
В результате без изменения остального алгоритма время сократилось с 300-400 мс до 1-3 мс.
Кейс не совсем конечно на знание алгоритмов, и даже наверное не на структуру данных, а скорее просто на понимание как это устроено. Но тем не менее.
Расскажите случаи, когда вам действительно очень помогло знание алгоритмов
Определение квантилей по потоку данных (например, 95-й персентиль). Нельзя просто хранить все данные, потом сортировать — слишком много данных по сравнению с памятью. Недостаточно хранить среднее и стандартное отклонение — данные не следуют нормальному распределению. Персентили не обязаны быть идеально точными.
Определение стартового сигнала (писк примерно известной частоты и длительности) в оцифрованном звуке с микрофона.
Система рекомендаций. Есть длинный список товаров с разными признаками, длинный список пользователей с историей (кто какие товары покупал) и функция похожести одного товара на другой (по признакам товара). Реализация в лоб (сравнивать всех со всеми) дохнет при росте размера списков, потому что O(N^2).
Автодополнение текста поискового запроса. Есть словарь возможных слов и словосочетаний с весами и некоторыми правилами, разбитый по категориям, искать по которому надо быстро и даже при наличии опечаток в запросе.
Кажется, что это стандартные задачи и для них есть готовые решения, но на практике получалось что ни одно из них не подходит (не тот язык, слишком тяжёлое — много зависимостей, не хватает гибкости, слишком сложное — долго разбираться, лицензионная чистота и так далее).
Например, буквально в пятницу писал мутную структуру данных, что-то вроде бинарной кучи, но и еще с протуханием верхнего элемента. То есть один поток пихает постоянно данные в эту кучу, а другой ожидает готового элемента из этой кучи, то есть по ключу меньшего и еще и протухшего. В стандартой библиотеке Java такого не нашел, была только DelayQueue, но это сильно проще, чем мне нужно было.
Еще на прошлой работе писал прикольный планировщик некоторых долгих задач для потоков. Есть набор задач их нужно раздавать потокам, после какогото времени потоки эти задачи возвращают с некоторым прогрессом и задачи опять кладуться в очередь. Первая реализация планировщика это была очередь. Но она плохо работала с задачами для которых еще пока нет данных по каким то причинам и было много пустых итераций на таких задачах, вместо того чтобы выполнять другие задачи для которых данные уже были. Потом я почитал код CFS в ядре линукса(это такой планировщик процессов) и запилил похожую планировку основанную на времени потраченном процессором на каждую задачу. А сами задачи, упорядоченные по этому времени хранились в бинарной куче. Соответственно планировщик вынимает задачу которая потратила меньше всего ресурсов отдает потоку на выполнение, после выполнения время обновляется и задача кладется назад в кучу.
Например, в том году понимание, что определенные regex-ы в перле не работают за полиноминальное время помогало быстро понимать, где могут быть проблемы в производительности.
Так же я абсолютно всегда смотрю в код реализации сктруктур/алгоритмов перед их использованием. И знание и понимание каких то базовых вещей мне крайне помогает.
Это то, что я сейчас так быстро припомнил, но алгоритмы вообще абсолютно везде. От чем ConcurrentHashMap отличается от HashMap внетри в Java до того как работает Paxos.
Еще на прошлой работе писал прикольный планировщик некоторых долгих задач для потоков. Есть набор задач их нужно раздавать потокам, после какогото времени потоки эти задачи возвращают с некоторым прогрессом и задачи опять кладуться в очередь. Первая реализация планировщика это была очередь. Но она плохо работала с задачами для которых еще пока нет данных по каким то причинам и было много пустых итераций на таких задачах, вместо того чтобы выполнять другие задачи для которых данные уже были. Потом я почитал код CFS в ядре линукса(это такой планировщик процессов) и запилил похожую планировку основанную на времени потраченном процессором на каждую задачу. А сами задачи, упорядоченные по этому времени хранились в бинарной куче. Соответственно планировщик вынимает задачу которая потратила меньше всего ресурсов отдает потоку на выполнение, после выполнения время обновляется и задача кладется назад в кучу.
Например, в том году понимание, что определенные regex-ы в перле не работают за полиноминальное время помогало быстро понимать, где могут быть проблемы в производительности.
Так же я абсолютно всегда смотрю в код реализации сктруктур/алгоритмов перед их использованием. И знание и понимание каких то базовых вещей мне крайне помогает.
Это то, что я сейчас так быстро припомнил, но алгоритмы вообще абсолютно везде. От чем ConcurrentHashMap отличается от HashMap внетри в Java до того как работает Paxos.
Знать — конечно нужно. Но дальше все зависит от языка. На бейсике (это я так называю похапе и прочие скрипты) — глупо не использовать стандартные функции, выполняющие стандартные алгоритмические действия, типа сортировки или работы со строками и тд, так как если выбран бейсик изначально и осознанно — то выбран скорее всего не из-за скорости выполнения программы, а из-за быстроты разработки и широким кругом вхождения (меньше ЗП на программистов). А если скажем речь идет про написание прошивки для микроконтроллера — то тут уже стоит тысячу раз подумать — юзать готовые функции или же написать свой велосипед, который учтет некоторые программно-аппаратные особенности реализации девайса в целом.
Вух [Глубокий выдох], спасибо тебе автор за такие слова, успокоение-то какое.
А потом получается, что простейшая задача решается с помощью трех десятков слабо совместимых между собой библиотек в соответствии с принципом чайника, из-за чего умудряются тормозить даже на ферме из 20 блейдов не самых чахлых конфигураций. Зато с реактом, редисом и монетизацией через микротранзакции, все как у больших мальчиков.
До сих пор ситуация в мире разработки напоминала мне *вырезано ибо политика* — любую мало-мальски сложную проблему пытались залить процессорными мощностями, памятью и каналами данных. Они росли и было круто. Теперь они расти перестали и снова пора начинать думать, отсюда все больше требований к математике среди девелоперов.
Да, конечно, можно и за отпуск собрать мапредьюс в облаке из грязи и веток, однако как же удивляется разработчик, когда понимает, что накладываемый такими решениями оверхед настолько велик, что очищенная от него задача спокойно выполняется на втором пентиуме.
До сих пор ситуация в мире разработки напоминала мне *вырезано ибо политика* — любую мало-мальски сложную проблему пытались залить процессорными мощностями, памятью и каналами данных. Они росли и было круто. Теперь они расти перестали и снова пора начинать думать, отсюда все больше требований к математике среди девелоперов.
Да, конечно, можно и за отпуск собрать мапредьюс в облаке из грязи и веток, однако как же удивляется разработчик, когда понимает, что накладываемый такими решениями оверхед настолько велик, что очищенная от него задача спокойно выполняется на втором пентиуме.
Не, я как раз писал акцентируя на поиск простых решений!
Простое решение — собрать мапредьюс из грязи и веток и залить процессорами. Развернуть все абстракции, вытащив наружу только то, что реально нужно — решение сложное.
Положительнейший эффект российского образования — это получение навыка думать. Казалось бы, зачем кодерам все эти матаны, поверхностные интегралы и критерий Рауса-Гурвица. Очевидно, эти знания будут не нужны в 99% случаев. Дело не в знаниях, а в получении навыка поиска, понимания, отождествления связанных вещей и системного анализа. Знания оставлены в университете, навык сохранён и уже дальше развивается в ваших других областях. Люди, которые развивались в университетские годы по какой-то причине узко — будут такими же узко(лобыми) и на работе. На первой же нестандартной ситуации — пык-мык, не знаю, пойду домой. Или, например, нежелание понимать область коллеги по работе — "не, я узкий специалист". Университет (ну или то что вы причисляете к науке) от этого отучивает. Нисколько не ученых готовят университеты, а закаляют к дальнейшей эффективной жизни.
Изучение матана и "навык думать" в общем случае не связаны.
Или, например, нежелание понимать область коллеги по работе — «не, я узкий специалист». Университет (ну или то что вы причисляете к науке) от этого отучивает.Проводил собеседование десятков вчерашних студентов ведущих вузов. К сожалению универ не отучивает от такой модели. Непонятно за счет чего он должен отучивать.
А они как вообще, выпустились, с какими результатами, легко ли? Как экзамены сдавали, быстро или медленно готовились? Надо оценить, как человек проходил этот квест. Если это для него не квест, а каторга — ну что ж. Универ — отличный фильтр. Те, кто застревает в такой вот узкой модели — это (на моей памяти, сам собеседовал десятки) обычно такие ребята, которые ходят на все лекции и повторяют за профессором, а потом ещё и сдают на 4. Смышленые, скоростные — они иногда и профессора-то не видели до экзамена, но сдают с блеском, т.к. к вопросу подошли не зубрежкой и повторением, а собственным пониманием.
А вот вопрос. Возьмем врачей. Одни изучают ухо, вторые — анус. На западе это разделение четкое и тебе просто не дадут лезть в ухо, если ты посвятил себя проктологии. И это правильно. А у нас как-то наоборот. Тебя учат всему, а потом сидит человек и тупит неделю в консоли юникс.
Вообще это одна из самых популярных баек. "На Западе" по некоторым параметрам ширина охвата покруче, чем у нас. Конкретно в сфере IT можно почитать рекомендации ACM/IEEE по содержанию вузовского образования. И надо иметь в виду, что ни в одном приличном вузе нельзя получить диплом, набирая курсы только в рамках major subject, всегда будут предметы общего характера или по дополнительной (minor subject) специализации.
Троллинг зачётный, но, судя по оценкам, не менее половины принимают вбросы (тезисы автора) всерьёз (которые поставили минусы). Нужна ещё шкала оценок качества троллинга, и тут — однозначный плюс.
Непонятно, в чем суть такого троллинга. Автор понаписал глупостей, замусорил пространство хабра, на котором и так качественного контента не хватает, подтвердил стереотипы о программистах 1С и битрикса, которые и так интеллектуалами не слывут.
Ну, может, немножко повеселился, да. А может, все-таки веселиться лучше идти на пикабу?
Ну, может, немножко повеселился, да. А может, все-таки веселиться лучше идти на пикабу?
Спасибо! Если честно, задумка была просто поделиться опытом, плохим-хорошим, какой есть. Знание алгоритмов, истоков, отцов основателей, C, математики — безусловно, БЕЗУСЛОВНО нужно!!! Но не всем. Либо знай это хорошо, либо просто не лезь и не страдай комплексом неполноценности, пей пиво и используй готовое — и будешь полезен человечеству.
Когда не пишешь нифига, знания не нужны. У меня друг (не программист вообще и не математик) сказал "зачем программировать, если все программы можно в интернете скачать?". Он просто не понимает, что такое программа, которой нет в мире и в которой всё есть.
Я видел, как люди, знающие только регулярки, не могли исправить баги в своих собственных веб-приложениях, потому что там надо было знать грамматики и конечные автоматы, а у них мозгов хватило только на регулярки (уровень средней школы), которыми ничего не сделаешь.
Я видел, как люди, знающие только регулярки, не могли исправить баги в своих собственных веб-приложениях, потому что там надо было знать грамматики и конечные автоматы, а у них мозгов хватило только на регулярки (уровень средней школы), которыми ничего не сделаешь.
Думаю, очевидно, что есть задачи в области программирования, связанные со знанием алгоритмов и оценкой их сложности и не связанные.
Также очевидно, что есть задачи, для которых информацию о возможных алгоритмах можно узнать в процессе решения.
Если задачи не связаны с алгоритмами, алгоритмы знать не надо. Тем не менее, это тоже программирование.
Если задачи, связанные с алгоритмами, появляются в работе редко, и есть возможность разобраться с алгоритмом в процессе решения, то общее понимание — нужно, знание вот этого конкретного алгоритма — нет. Использование готового алгоритма из библиотеки относится сюда же.
Если задачи, связанные с алгоритмами, появляются в работе постоянно, алгоритмы знать надо.
Также бывают задачи на нестандартные алгоритмы либо на нестандартное применение стандартных алгоритмов. Для таких задач алгоритмы знать надо, причем очень хорошо.
Также очевидно, что есть задачи, для которых информацию о возможных алгоритмах можно узнать в процессе решения.
Если задачи не связаны с алгоритмами, алгоритмы знать не надо. Тем не менее, это тоже программирование.
Если задачи, связанные с алгоритмами, появляются в работе редко, и есть возможность разобраться с алгоритмом в процессе решения, то общее понимание — нужно, знание вот этого конкретного алгоритма — нет. Использование готового алгоритма из библиотеки относится сюда же.
Если задачи, связанные с алгоритмами, появляются в работе постоянно, алгоритмы знать надо.
Также бывают задачи на нестандартные алгоритмы либо на нестандартное применение стандартных алгоритмов. Для таких задач алгоритмы знать надо, причем очень хорошо.
НЛО прилетело и опубликовало эту надпись здесь
В чем-то согласен… есть такое. Я хотел в посте лишь поднять важность прикладных знаний, дающих нередко 95% отдачи.
На период работы, предшествующий переезду (время оформления документов для переезда в США) зарплата — 80,000-120,000 рублей в месяц. Начальная зарплата после переезда в США — $85,000 в год
Это оттуда же. Что-то мне подсказывает, что средненький фулстэк, который путает бинарное дерево с большим О в нотации второго закона Ньютона, может рассчитывать на большее. И в Москве, и в штатах. Это если речь о деньгах.
Иногда полезнее быть узкоспециализированным, но глубоким в своей специфике специалистом, иногда полезнее быть специалистом широкого профиля без особых требований к глубине познаний. И на всё это нужно время. И ответственность за выбор своей судьбы (ну, или какого-то отрезка карьеры) лежит на каждом человеке, не получится написать статью, которая позволит программистам сделать себе лоботомию и жить не напрягаясь по инструкции. Полезная статья в этой теме — это статья, предлагавшая бы критерии оценки «широты» и «глубины» специализации и ориентирования на текущем рынке по этим параметрам. А сферически в вакууме рассуждать о том, кем лучше быть — пекарем или трактористом, — бессмысленно.
Ну мы не в сферическом вакууме рассуждаем же. Каждый где-то работает, что-то кодит, что-то изучает, что-то зарабатывает. В посте хотелось поднять важность с одной стороны прикладных знаний, а с другой — подчеркнуть ограниченность времени и сил. Когда-то я для себя решил так: разберись с основами, с принципами — дальше будет проще:
А дальше — практика, практика...
- Таненбаум: железо, ОС
- Стивенс, Вахалия: юникс изнутри
- Стивенс, сетевые протоколы
- С
- java, с++ чтобы быстро что-то поднять из готового
- php,python — чтобы в вебе развернуться
- математика, базовое машиное обучение, матстат, тервер — ну чтобы было лучше понятно что происходит
- горстка придуманных человечеством алгоритмов, ну чтобы не придумывать заново
А дальше — практика, практика...
Саш, недавно была статья в тему — Чем плохо быть fullstack-ом. Я думаю, что ты примерно про то же самое пишешь. Хорошо или плохо — очень зависит от контекста, условий, окружения, требований.
Ну у меня детское желание — найти серебряную пулю :-)
По мне там самый лучший коммент от MTonly https://habrahabr.ru/post/278467/#comment_8793335
Про Full StackOverflow developer. Хохотали час, не уточняйте детали, пожалуйста :-))
Про Full StackOverflow developer. Хохотали час, не уточняйте детали, пожалуйста :-))
Сама постановка вопроса, какая-то странная. Конечно надо алгоритмы знать.
У нас в чисто финансовой(!) компании используются следующие алгоритмы:
У нас в чисто финансовой(!) компании используются следующие алгоритмы:
- Имитация отжига;
- Монте-Карло;
- Стеганография в частотной и пространственной области;
- SIFT-дескрипторы;
- Перцептивные хеши;
- Триангуляция Делоне;
- Поиск остовных деревьев;
- Баесовские классификаторы;
- Метод k-средних
И это только то, к чему я имел непосредственное отношение. Короче надо программисту алгоритмы знать.
Я программист. И не знаю. Что значит "надо"? Не надо. Или не программист?
Если тебя интересует конкретное моё личное мнение, то ты не программист.
Если же подходить к вопросу более формально и смотреть профессиональные стандарты, то в России программист тоже должен знать алгоритмы.
Если же подходить к вопросу более формально и смотреть профессиональные стандарты, то в России программист тоже должен знать алгоритмы.
К сожалению, или к счастью, меня больше интересует мнение работодателей и их бизнеса, а также полезности, которую люди моей профессии (которую для простоты называют "программист") этому бизнесу приносят. Интересно знать, кому (или для чего) должен знать алгоритмы человек, который называет себя программистом? Моё мнение несколько иное. Программист не должен знать алгоритмы.
Попробую ответить на твой комментарий по частям.
К сожалению, или к счастью, меня больше интересует мнение работодателей и их бизнеса
Никогда не понимал зачем задавать вопрос, если ответ тебя всё равно не интересует.
которую для простоты называют «программист»
Здесь наверное и скрыта вся проблема. Программист и тот, кого для простоты называют "программистом" это зачастую очень разные люди. Не знаю, что у вас там за профессия такая, но немного утрируя, могу рассмотреть гипотетическую ситуацию, где некий эникейщик Вася, которого для простоты называют программистом, занимается тем, что меняет картриджи в принтерах. Такому "программисту" алгоритмы действительно не нужны.
кому (или для чего) должен знать алгоритмы человек, который называет себя программистом
Человек, который сам себя называет программистом никому и ничего не должен. Но проблема в том, что назвать себя программистом недостаточно. Если ты и правда считаешь себя программистом, то должен любить строгость и формализмы (надеюсь на это). Повторюсь, в России для того, чтобы быть программистом, надо удовлетворять требованиям профессионального стандарта. А там как раз перечислены требования.
Вот это конструктивно. Но есть несколько нюансов. Если я правильно понял, вы решили свести обсуждение в русло "может или не может считаться программистом в определении неких стандартов России человек, который не знает неких алгоритмов". Что ж, здесь спорить сложно, если действительно есть какой-то стандарт, в котором прописано, что человек только тогда может называться программистом, если знает следующие алгоритмы: Имитация отжига; Монте-Карло; Стеганография в частотной и пространственной области; SIFT-дескрипторы; Перцептивные хеши; Триангуляция Делоне; Поиск остовных деревьев; Баесовские классификаторы; Метод k-средних. Если человек не знает каждый из этих алгоритмов, то, согласно этому стандарту, программистом он считаться не может. Так вот нюанс заключается в том, что потребители этого стандарта не 100% населения России и некоторые люди (особенно те, которые связаны с реальным бизнесом), руководствуются своими соображениями (намеренно не употребляю слова "стандарт") относительно того, что должен и чего не должен знать программист. К примеру, область, в которой я работаю (крупные веб-проекты, особенно в начальной стадии их развития), программистами принято называть людей, которые могут программировать (набирать код) на языке программирования (обычно скриптовом). Вся дальнейшая классификация содержит слово "программист" в сочетании с каким-то другим. Например, "хороший программист", "говно-программист", "программист-архитектор", "бэкенд-программист", "фронтенд-программист" и т.д. Как правило, слово "программист" в моей области является синонимом слова "разработчик".
При этом я убеждён, что есть области, в которых программистами не могут считаться люди, которые не смогут написать некий алгоритм, который ежедневно используется в их работе.
Итог (я уже говорил его, повторюсь): всё сильно зависит от окружения, области, требований. И заявлять о том, что программист должен или не должен — значит забить на контекст и обсуждать сферическую хрень в вакууме. Что, на мой взгляд, лишено всякого смысла, кроме эмоционального.
При этом я убеждён, что есть области, в которых программистами не могут считаться люди, которые не смогут написать некий алгоритм, который ежедневно используется в их работе.
Итог (я уже говорил его, повторюсь): всё сильно зависит от окружения, области, требований. И заявлять о том, что программист должен или не должен — значит забить на контекст и обсуждать сферическую хрень в вакууме. Что, на мой взгляд, лишено всякого смысла, кроме эмоционального.
Интересно знать, кому (или для чего) должен знать алгоритмы человек, который называет себя программистом?И как же должен называться специалист, от которого требуется имитация отжига; Монте-Карло… далее по списку? Вы уже установили, что это не программист. Тогда кто же?
Ок, подсказываю: если я утверждаю, что программист не должен знать алгоритмов, то это не означает, что если он знает алгоритмы, то он не программист.
Я понял что вас сбило с толку. Фразу "не должен знать" я употреблял в смысле "не обязан знать", а не в смысле "должен не знать". Мой косяк, допустил двусмысленность.
Никогда не понимал зачем задавать вопрос, если ответ тебя всё равно не интересует.
А он не спрашивал твое мнение. Ты же безапелляционно заявлял что надо алгоритмы знать.
Повторюсь, в России для того, чтобы быть программистом, надо удовлетворять требованиям профессионального стандарта. А там как раз перечислены требования.
Я не поленился и скачал стандарт. Там есть две строки про алгоритмы:
Умения: Применять стандартные алгоритмы в соответствующих областях
Знания: Алгоритмы решения типовых задач, области и способы их применения
Вряд ли "Триангуляция Делоне" может быть отнесена к алгоритмам для решения типовых задач.
Если внимательно почитать стандарт, то становится понятно, что используется широкое понятие алгоритма, как набора инструкций для достижения результата, а не зубодробительных вещей вроде криптографии.
Поэтому под определение алгоритма равно подходят использование готовых библиотек и рукопашная реализация симплекс-метода.
Вроде знание и умение оценивать алгоритмы и является базовым требованием для прохождения собеседования на программиста. Я был на куче собеседований в совершенно разные фирмы и абсолютно всегда была половина или больше собеседования посвещена решению различных задач и оценке сложности алгоритма. Возможно, часть из этих задач высоана из пальца, но если работодатель требует это при приеме на работу, соответственно это и есть его требования для квалификации программистов. Собеседований за последние лет пять было с десятка полтора, наверное. Скажу даже больше, всего лишь в одном или двух местах были требования про знание конкретного языка, но на собеседовании такого никто не спрашивал, тем более про какие то библиотеки и фреймворки тоже никто не спрашивал. Может это, конечно, требования к средним программистам, а не к senior, но тем не менее у меня такой опыт.
Чтобы понять эти алгоритмы, лично мне потребовалось полтора года свободного времени по дороге на работы и домой. Вы желаете этот ад повторить нормальным инженерам, умеющим писать хороший код:?
Опять 25. Кто-то просто должен взять и сделать статистический анализ появления статей "Нужны ли программисту алгоритмы?". Было бы очень интересно узнать, как это связано с временем года, возрастом автора, весенним обострением и т.д. ...
По существу. Заметил, что в обсуждении этой, какзалось бы, чисто технической темы очень-очень редко приводят формальные доказательства. Пусть в этот раз будет мой черёд. Кто дочитает до конца узнает лёгкий способ прогнать попоболь и прочую хворь и начать жить счастливо.
Итак, когда мы спрашиваем у сферического воина клавиатуры, нужны ли ему теоретические знания, то возможны следующие варианты ответа:
И тут, вероятно, вы повчувствуете легкий запах горелого и со сверхсветовой скоростью начнёте писать о том, что не попадаете ни в одну из категорий, попутно раздавая минусы налево и направо. Хочу вас немного притормозить. Дело в том, что чёткая логика работает только в теории. На практике как бы вы ни пытались классифицировать то или иное явление или объект, рано или позжно вы столкнётесь с тем, что два разных объекта по одному из измерений будут принадлежать одному и тому же классу. Простой пример — удерживающие сиденье для ребёнка. Куда бы вы отнесли: к автомобильным товарам или товарам для детей? Ах, да — "удерживающие устройства"… для ребёнка или автомобильные? "Очевидно — автомобильные для ребёнка", скажете вы. Вот тут мы и подошли к сути — наш опыт это линейная комбинация каких-то факторов. Сначало человек говнокодит напропалую и знать не знает о каких-то алгоритмах. Но в душе он понимает, что с кодом, который он пишет, что-то не так — он попахивает. Он начинает читать теорию, углубляться, понимать суть, и код его преображается на глазах. На его в глазах, а в глазах Фабриса Беларда это всё ещё… врочем, Фабрис скорее всего слишком занят, чтобы участвовать в холиворах подобно этому или тратить время на рассуждения о качестве кода. Таким образом получается, что выше приведённые варианты являются базисом, т.е. попарно независимы и образуют целое пространство, элементы которого участники подставляют в свою функцию оценки — нужно или ненужно знать алгоритмы. И как-то так выходит, что мы спорим о разных вещах.
Вывод. Можно тешить ЧСВ сколько угодно долго, и ситуация, когда сначала "молодец среди овец", а потом "а среди молодцов сам овца" абсолютно нормальная. Это называется рост. Просто не стоит задерживать надолго в каждой из фаз, и не стоит забывать, что остальные тоже находятся, каждый в своей фазе, только уровни у всех разные. Если вы не знаете алгоритмы — живите счастливо дальше или идите учить их, а если знаете — вы большой молодец. Только получается, что Геннадий и Петр большие молодцы, чем вы? Ой, нет — то программироваие не имеет ничего общего с реальным. oh, shi...
По существу. Заметил, что в обсуждении этой, какзалось бы, чисто технической темы очень-очень редко приводят формальные доказательства. Пусть в этот раз будет мой черёд. Кто дочитает до конца узнает лёгкий способ прогнать попоболь и прочую хворь и начать жить счастливо.
Итак, когда мы спрашиваем у сферического воина клавиатуры, нужны ли ему теоретические знания, то возможны следующие варианты ответа:
- «Да, на основе них я разрабатываю новые теории»
- «Да. С помощью них я могу объяснить, как работает программа»
- «Вообщем-то нет, но я учу, чтобы понтануться или загнобить собеседуемого»
- «Нет, я просто пишу код, как знаю, а если не знаю, то лезу в интернет»
- «Что такое алгоритмы?»
И тут, вероятно, вы повчувствуете легкий запах горелого и со сверхсветовой скоростью начнёте писать о том, что не попадаете ни в одну из категорий, попутно раздавая минусы налево и направо. Хочу вас немного притормозить. Дело в том, что чёткая логика работает только в теории. На практике как бы вы ни пытались классифицировать то или иное явление или объект, рано или позжно вы столкнётесь с тем, что два разных объекта по одному из измерений будут принадлежать одному и тому же классу. Простой пример — удерживающие сиденье для ребёнка. Куда бы вы отнесли: к автомобильным товарам или товарам для детей? Ах, да — "удерживающие устройства"… для ребёнка или автомобильные? "Очевидно — автомобильные для ребёнка", скажете вы. Вот тут мы и подошли к сути — наш опыт это линейная комбинация каких-то факторов. Сначало человек говнокодит напропалую и знать не знает о каких-то алгоритмах. Но в душе он понимает, что с кодом, который он пишет, что-то не так — он попахивает. Он начинает читать теорию, углубляться, понимать суть, и код его преображается на глазах. На его в глазах, а в глазах Фабриса Беларда это всё ещё… врочем, Фабрис скорее всего слишком занят, чтобы участвовать в холиворах подобно этому или тратить время на рассуждения о качестве кода. Таким образом получается, что выше приведённые варианты являются базисом, т.е. попарно независимы и образуют целое пространство, элементы которого участники подставляют в свою функцию оценки — нужно или ненужно знать алгоритмы. И как-то так выходит, что мы спорим о разных вещах.
Вывод. Можно тешить ЧСВ сколько угодно долго, и ситуация, когда сначала "молодец среди овец", а потом "а среди молодцов сам овца" абсолютно нормальная. Это называется рост. Просто не стоит задерживать надолго в каждой из фаз, и не стоит забывать, что остальные тоже находятся, каждый в своей фазе, только уровни у всех разные. Если вы не знаете алгоритмы — живите счастливо дальше или идите учить их, а если знаете — вы большой молодец. Только получается, что Геннадий и Петр большие молодцы, чем вы? Ой, нет — то программироваие не имеет ничего общего с реальным. oh, shi...
Секретный метод
Представьте, что всё, что вы хотите сказать про программирование будет сказано про… акробатику. Верите или нет, но сходства тут очень много. В акробатике есть такой элемент — заднее сальто. По сути — это куворк назад в вертикальной плоскости. Это самый естесвенный по природе элемент — дикие обезьяны выполняют его без труда. Вы ведь умнее дикой обезьяны? Тогда отложите клавиатуру, встаньте и сделайте заднее сальто. Если не получислось, то попробуйте научиться. Вы узнаете много нового о том, сколько труда может потребовать простое на первый взгляд действие. Если у вас получилось поздравляю — вы или уникальный, или до этого занимались. А теперь выучите пару-тройку других элементов и попробуте: заработать на этом, выиграть олимпиаду по гимнастике, восхитить своих друзей, восхитить друзей-гимнастов, получить грант, устроиться на работу в Cirque Du Soleil или House of Dancing Waters (аналоги гугло-амазано-микрософта). Когда вы закончите, поймёте бессмысленность всего, что говорили про программирование, и обретёте просветление.
Ну я связал пост с проблемой, когда хороший программист лезет в математику и рождает чудо-бред, и наоборот, когда математик, желая заработать, начинает кодить и рождает бредо-код. Это актуально в контексте активизации машинного обучения, бигдаты, дипленинга. Кратко — видится четкое разделение и специализация.
Нужно ли знать программисту математику?
Нужно ли знать программисту алгоритмы?
Боюсь, что скоро возникнет вопрос:
Нужно ли знать программисту языки программирования?
Нужно ли знать программисту алгоритмы?
Боюсь, что скоро возникнет вопрос:
Нужно ли знать программисту языки программирования?
Нужно ли программисту уметь программировать?
Ведь все уже написано, надо только уметь запускать IDE и копипастить код со StackOverflow.
Ведь все уже написано, надо только уметь запускать IDE и копипастить код со StackOverflow.
Шутки шутками, но критика разработчиков на symfony 1 часто содержала аргумент типа "Программисты на симфони — это не программисты, это писатели конфигов".
У нас препод по теории компиляторов, рассказывая классификацию языков программирования, говорил, что идеальный язык программирования — это когда программист, закинув ноги на стол, объясняет компу что ему надо, и тот сам все пишет :-)
Этого я и боюсь. Сам хотел задать подобный вопрос, но вы опередили. Ну а что — запустил редактор, нажал котогенератор, и всё написано.
котогенератор — не опечатка? :)
Уважаемый istui, конечно же опечатка, но она получилась такой милой, что я не стал её исправлять. :3
Нужны ли алгоритмам программисты?
Слово пропущено. Должно было быть "А нужно ли знать CRUD программисту алгоритмы". Тогда ответ действительно "нет, не нужно". Но не все делают CRUD.
Реализовать систему для учета печати и продажи билетов в отдельно взятом кинотеатре. Правильная декомпозиция модели данных, CRUD, UI, работа с принтером, использование джойнов для построения отчетов, двойная бухгалтерская запись, исправление ошибок при сбоях печати, обработка различных ситуаций при продаже билетов — возврат, повреждение или брак бланка. Связано с программированием? Да. Делает ее программист? Да. Нужно знание алгоритмов? Нет.
Написать драйвер для конкретных грузовых весов на заводе. Весы передают данные по малопонятому протоколу, надо сделать драйвер, который будет передавать данные в программу, в которой работает оператор, в том формате, который эта программа понимает. Никакого CRUD-а нет, нужно знание ассемблера и умение разбираться в непонятных протоколах. Связано с программированием? Да. Делает ее программист? Да. Нужно знание алгоритмов? Нет.
Написать драйвер для конкретных грузовых весов на заводе. Весы передают данные по малопонятому протоколу, надо сделать драйвер, который будет передавать данные в программу, в которой работает оператор, в том формате, который эта программа понимает. Никакого CRUD-а нет, нужно знание ассемблера и умение разбираться в непонятных протоколах. Связано с программированием? Да. Делает ее программист? Да. Нужно знание алгоритмов? Нет.
Вот не буду показывать пальцем относительно той же системы учета печати и продажи билетов, один товарищ как-то спросил "а как посчитать растояние между точками". Даааа какие нафиг алгоритмы в самом деле. Математику бы знать на уровне школьного курса.
Приведённый контрпример таковым не является. Понятно, что не в любом не-CRUD проекте нужно знание алгоритомов. Тем не менее такие проекты существуют, я выше в этой ветке даже примеры приводил.
Товарищи, ну что вы скопом накинулись на автора!? Ведь высказанная мысль отнюдь не нова, а с основным посылом конструктивно спорить сложно: никто же не будет отрицать, что большая масса "рыночных" задач даже мартышка сведет к нескольким типовым и соберет из имеющегося конструктора что-то похожее на правду? А часть рынка, в которой требует использования передовых достижений CS и математики, охватывает относительно небольшое количество имеющего отношение к программированию населения. Эта "вершина" у всех на слуху, они зарабатывают миллиарды, попасть к ним — мечта миллионов, они являются локомотивом индустрии. Туда и нужны образованные специалисты, способные решать нетиповые задачи оригинальными способами. А остальным куда податься? А различные "калькуляторы" кто будет писать?
Автор всего лишь сказал, что ему хорошо в его нише, он доволен своей карьерой и профессиональными успехами — чего и другим желает. Можно только пожелать удачи.
Мне только одно непонятно: откуда (и на кой черт) такое количество дипломированных программистов, если алгоритмы — то есть то, чему и учат на программистских факультетах — не приносят практической пользы, а пресловутые "практические навыки" — которым там по большому счету не учат — приводят к профессиональной успешности? Уверен, что автор что-то да заканчивал. Судя по посту, потерял время впустую.
Автор всего лишь сказал, что ему хорошо в его нише, он доволен своей карьерой и профессиональными успехами — чего и другим желает. Можно только пожелать удачи.
Мне только одно непонятно: откуда (и на кой черт) такое количество дипломированных программистов, если алгоритмы — то есть то, чему и учат на программистских факультетах — не приносят практической пользы, а пресловутые "практические навыки" — которым там по большому счету не учат — приводят к профессиональной успешности? Уверен, что автор что-то да заканчивал. Судя по посту, потерял время впустую.
Я вас разочарую.
Миллиарды зарабатывают не алгоритмами.
Миллиарды зарабатывают не алгоритмами.
Вы правы. Миллиарды зарабатывают технологиями. Те компании, которые достаточно умны для того, чтобы вкладывать миллионы в тех, кто способен разрабатывать алгоритмы, на которых эти технологии строятся
И снова разочарую. Миллиарды зарабатывают маркетингом (в смысле впариванием ненужного), продажей рекламы, продажей задорого китайских поделок и откатами.
Маску это скажите. Еще можете попробовать ребятам из гугла рассказать. IBM и Intel не забудьте порадовать своей мудростью. Вот дяденьки удивятся, они то были уверены, что их основной капитал — технологии.
Капитал и зарабатывание денег — разные вещи.
Вот представь что у тебя появился капитал в виде всех технологий Intel. Но у тебя нет бренда, маркетинга, сбыта и денег.
Как будешь зарабатывать миллиарды?
Вот представь что у тебя появился капитал в виде всех технологий Intel. Но у тебя нет бренда, маркетинга, сбыта и денег.
Как будешь зарабатывать миллиарды?
Давайте представим обратное. Ну так, в форме бреда. У Вас есть бренд, маркетинг и даже каналы сбыта. А за ними — ни шиша. Что случится с Вашими миллиардами? Наверное, по Вашим представлениям Яндекс, SpaceX, Adobe и прочие были всегда, вот так раз — и у них есть и бренд, и маркетинг, и всё-всё-всё. Но давайте я по наивности своей предположу, что они начинали с наработки интеллектуального капитала, в том числе — алгоритмов, на основании чего и стали успешными.
Если у меня есть бренд, маркетинг, каналы сбыта, то я легко стану реселлером продуктов. А с прибыли буду инвестировать разработку своих продуктов. А ты что будешь делать со всеми технологиями intel?
Про яндекс достаточно почитать исторю:
https://yandex.ru/company/history/1990 люди делали поиск и ПРОДАВАЛИ его
https://yandex.ru/company/history/1993 на вырученные с поиска деньги основали интернет-компанию
https://yandex.ru/company/history/1998 яндекс начал сам зарабатывать деньги
То есть 5 лет кто-то кормил разработку.
Были там новые алгоритмы? Вряд ли, TF-IDF известен много лет.
Мог бы яндекс взлететь без денег инвесторов? Однозначно нет. Мог бы яндекс взлететь без опыта продаж — тоже нет.
Технологии важны, но на одних технологиях не уедешь. Нужны деньги, продажи, маркетинг.
Про яндекс достаточно почитать исторю:
https://yandex.ru/company/history/1990 люди делали поиск и ПРОДАВАЛИ его
https://yandex.ru/company/history/1993 на вырученные с поиска деньги основали интернет-компанию
https://yandex.ru/company/history/1998 яндекс начал сам зарабатывать деньги
То есть 5 лет кто-то кормил разработку.
Были там новые алгоритмы? Вряд ли, TF-IDF известен много лет.
Мог бы яндекс взлететь без денег инвесторов? Однозначно нет. Мог бы яндекс взлететь без опыта продаж — тоже нет.
Технологии важны, но на одних технологиях не уедешь. Нужны деньги, продажи, маркетинг.
Ну стали Вы реселлером. Молодец, заработали на чужих достижениях, стали частью рынка. Нет претензий. Здесь, вообще-то, говорится о секторах, в которых производятся программные продукты, а не перепродается или адаптируется готовое.
https://yandex.ru/company/history/1990 люди ДЕЛАЛИ ПОИСК и продавали его.
Поисковики существовали до гугла и яндекса. Почему выстрелили именно эти, тоже маркетинг? Или денег у них было больше? Наверное, лучше сработали маркетологи… А может их решения были стандартными, но другие почему-то не додумались их использовать? Или всё-таки используемые технологии качественно отличались от технологий конкурентов?
Если у меня будут технологии Intel — инвесторы в очередь выстроятся, чтобы хоть немного приобщиться к подобной бизнес-бомбе. Деньги идут туда, где есть возможность прибыли, а она есть там, где новые технологии открывают новые рынки.
https://yandex.ru/company/history/1990 люди ДЕЛАЛИ ПОИСК и продавали его.
Поисковики существовали до гугла и яндекса. Почему выстрелили именно эти, тоже маркетинг? Или денег у них было больше? Наверное, лучше сработали маркетологи… А может их решения были стандартными, но другие почему-то не додумались их использовать? Или всё-таки используемые технологии качественно отличались от технологий конкурентов?
Если у меня будут технологии Intel — инвесторы в очередь выстроятся, чтобы хоть немного приобщиться к подобной бизнес-бомбе. Деньги идут туда, где есть возможность прибыли, а она есть там, где новые технологии открывают новые рынки.
В любой гонке кто-то приходит первым. И не обязательно тот, у кого технологии лучше.
Если у меня будут технологии Intel — инвесторы в очередь выстроятся, чтобы хоть немного приобщиться к подобной бизнес-бомбе.бугага. Прости, реально смешно. Нахапать деньги инвестора и зарабатывать — разные вещи. От слова вообще.
Компьютер — машина. Программист управляет работой машины, то есть просто водила. От квалификации, степени владения и уровня знаний зависит качество управления. Всё.
Вопрос: нужен ли водителю навык торможения ручником? Ответ рядового автомобилиста: наверное можно без него и обойтись, но было бы здорово это уметь. Но обязательно придет человек, который скажет, что если водитель не умеет в торможение с разворотом, то допускать до баранки его нельзя — имея ввиду дрифт, а другой человек, который всю жизнь на трамвае ездит пассажиром, вообще не поймет, зачем такое может понадобиться. К чему весь этот разговор, если в коментах каждый говорит о чем-то своем, а сам пост ни о чем и не дает никакой конкретики? Просто посраться на вечнохоливарную тему?
НЛО прилетело и опубликовало эту надпись здесь
Помню препод в универе, когда погружался в глубины науки, говорил нам "А если вы окажетесь на необитаемом острове? Вы должны это уметь" из говна и палок собрать ракету. Убеждён, что если и окажусь на необитаемом острове, то главной для меня задачей будет побыстрее с него свалить в цивилизацию. Так что да, голосую, что пусть алгоритмами занимаются учёные и математики. Знаний и информации стало слишком много, надо уметь настраивать персональный фильтр, как бы всё "нужным" и "полезным" не казалось.
Знаете, буквально вчера я задавал вопрос насчет самой крутой и самой распиаренной библиотеки .NET: как расшифровать RSA, не имя открытого ключа. Из трех комментаторов никто не понял вопроса. (https://toster.ru/q/300377)
А потом я покурил мануалы, разобрался что куда и зачем, попутно поймал еще и баг с разным направлением байт в экспорте/импорте двух разных классов(RSAParam и BigInteger), и решил задачу за пять часов. Да, признаю, это долго, но, во-первых, я новичок в C#, во-вторых, двое программеров до меня не смогли ее решить. Один просто не собирался лезть в дебри, второй, так же как и комментаторы к моему вопросу, советовал сменить подход.
Так что, пока вы находитесь в зоне комфорта и вас все устраивает — все хорошо. Как только у вас возникнет задача держать вместо 150 клиентов 10 000(посмотрите, была такая оптимизация на хабре), уже станет сложнее. Ну а когда внезапно окажется, что для вашей задачи есть две библиотеки, которые внезапно валятся с ошибками стоит сделать шаг влево, шаг вправо от написанных тестовых примеров — дело будет просто ахтунг.
А потом я покурил мануалы, разобрался что куда и зачем, попутно поймал еще и баг с разным направлением байт в экспорте/импорте двух разных классов(RSAParam и BigInteger), и решил задачу за пять часов. Да, признаю, это долго, но, во-первых, я новичок в C#, во-вторых, двое программеров до меня не смогли ее решить. Один просто не собирался лезть в дебри, второй, так же как и комментаторы к моему вопросу, советовал сменить подход.
Так что, пока вы находитесь в зоне комфорта и вас все устраивает — все хорошо. Как только у вас возникнет задача держать вместо 150 клиентов 10 000(посмотрите, была такая оптимизация на хабре), уже станет сложнее. Ну а когда внезапно окажется, что для вашей задачи есть две библиотеки, которые внезапно валятся с ошибками стоит сделать шаг влево, шаг вправо от написанных тестовых примеров — дело будет просто ахтунг.
Знаете, но подход вам все равно надо сменить, не смотря на то что задача решена. Точнее, именно потому что задача решена. Фактически, вы получили открытый ключ из закрытого. А значит, кто угодно сможет сделать то же самое, воспользовавшись вашим же кодом.
Насколько я понимаю, вам надо чтобы никто кроме сервера не мог отправить вашей программе данные. Это — обычная задача на цифровую подпись, делается при помощи пары методов SignData / VerifyData (ну или SignHash / VerifyHash). Первый требует обоих ключей, второй — только открытого.
Если требуется еще и чтобы данные никто не обладающий вашей программой не смог прочитать — тут можно использовать любое другое шифрование. Да хоть то же самое, что делали вы — но теперь с него задача верификации снята, а значит можно спокойно оба ключа прописать в программе. Но я бы советовал тут использовать AES или другой симметричный алгоритм — быстрее работать будет.
Насколько я понимаю, вам надо чтобы никто кроме сервера не мог отправить вашей программе данные. Это — обычная задача на цифровую подпись, делается при помощи пары методов SignData / VerifyData (ну или SignHash / VerifyHash). Первый требует обоих ключей, второй — только открытого.
Если требуется еще и чтобы данные никто не обладающий вашей программой не смог прочитать — тут можно использовать любое другое шифрование. Да хоть то же самое, что делали вы — но теперь с него задача верификации снята, а значит можно спокойно оба ключа прописать в программе. Но я бы советовал тут использовать AES или другой симметричный алгоритм — быстрее работать будет.
Хм… общая ситуация такова:
Во-первых, заказчик не желает ничего слышать о том, чтобы хоть какие-нибудь данные лежали в открытом виде. В смысле, в файле лицензии. Попытки его убедить в том, что расшифровать данные в любом случае труда не составит, наткнулись на его: "это сложнее, чем просто открыть текстовый файл". И не могу с ним не согласиться.
Во-вторых, RSA .net для расшифровки требует наличия открытого и закрытого ключа.
Ну а дальше — пять часов геммороя и BigInteger меня спас :-)
В-третьих, у меня нет доступа к серверу лицензии и заказчик не хочет его давать. Значит, изменения возможны только внутри программы.
Ну а так, да, я совершаю типичную операцию цифровой подписи. Абсолютно типичную, о чем и шла речь в посте. Просто, криво реализованную Майкрософтом.
П.с. до меня там было два ключа — для расшифровки все тем же .Net RSACryptoProvider
Во-первых, заказчик не желает ничего слышать о том, чтобы хоть какие-нибудь данные лежали в открытом виде. В смысле, в файле лицензии. Попытки его убедить в том, что расшифровать данные в любом случае труда не составит, наткнулись на его: "это сложнее, чем просто открыть текстовый файл". И не могу с ним не согласиться.
Во-вторых, RSA .net для расшифровки требует наличия открытого и закрытого ключа.
Ну а дальше — пять часов геммороя и BigInteger меня спас :-)
В-третьих, у меня нет доступа к серверу лицензии и заказчик не хочет его давать. Значит, изменения возможны только внутри программы.
Ну а так, да, я совершаю типичную операцию цифровой подписи. Абсолютно типичную, о чем и шла речь в посте. Просто, криво реализованную Майкрософтом.
П.с. до меня там было два ключа — для расшифровки все тем же .Net RSACryptoProvider
Но вы лучше не сделали. Вы оставили все так же.
Просто прибавили 3 часа геммороя потенциальному злоумышленнику.
И да — это никакая не операция цифровой подписи. Подписывают закрытым ключом, а не открытым.
Просто прибавили 3 часа геммороя потенциальному злоумышленнику.
И да — это никакая не операция цифровой подписи. Подписывают закрытым ключом, а не открытым.
Эээээ… Не подскажите, как злоумышленник может ЗАШИФРОВАТЬ данные моим ключом? Если его у него нет.
Вставить свой ключ в код программы — не вариант, сама программа так же подписывается и проверяет свои подписи при старте.
Вставить свой ключ в код программы — не вариант, сама программа так же подписывается и проверяет свои подписи при старте.
(del, ошибся)
Не подскажите, как злоумышленник может ЗАШИФРОВАТЬ данные моим ключом? Если его у него нет.
Ээээ… В каком формате вы передаете закрытый ключ? (p, q, d), или (n, d)?
Он берет ваш алгоритм, и получает открытый ключ из закрытого. Теперь у него есть ОБА ключа, и он может делать что угодно.
Вот у вас на руках есть секретная экспонента(d) и модуль(n). Как получить из этого открытую экспоненту?
Вот так: https://toster.ru/q/300377
Там эта задача не решается.
Я вообще выдернул с сайта MSDN кусок кода и изгалялся над ним как только мог.
Повторяю вопрос:
В rsa есть два стартовых больших натуральных числа: p и q, от них вычисляются три других числа: e, d и модуль — n
Как, имея на руках только d и n, вычислить е?
Я вообще выдернул с сайта MSDN кусок кода и изгалялся над ним как только мог.
Повторяю вопрос:
В rsa есть два стартовых больших натуральных числа: p и q, от них вычисляются три других числа: e, d и модуль — n
Как, имея на руках только d и n, вычислить е?
Тогда я не понимаю что вы вообще там сделали.
У вас в вопросе написан формат закрытого ключа:
Modulus, Exponent, P, Q, DP, DQ, InverseQ, D
Из них элементы Modulus и D образуют открытый ключ. То есть открытый ключ содержится в закрытом.
Modulus, Exponent, P, Q, DP, DQ, InverseQ, D
Из них элементы Modulus и D образуют открытый ключ. То есть открытый ключ содержится в закрытом.
Хм… в экспорте RSA в открытом ключе содержатся только Modulus и Exponent.
При этом, значение Exponent нельзя поменять на D — при импорте RSA пишет, что плохое значение.
По итоговому результату, я полностью избавился от расшифрования с помощью RSA, передаю Modulus and D, превращаю их в числа BigInteger, а дальше идет расшифрование с помощью BigInteger.ModPow
При этом, изначально я напутал с терминологией, считая открытый ключ шифрующим. этой ночью с ней разобрался.
Полностью, итоговый метод таков:
При этом, значение Exponent нельзя поменять на D — при импорте RSA пишет, что плохое значение.
По итоговому результату, я полностью избавился от расшифрования с помощью RSA, передаю Modulus and D, превращаю их в числа BigInteger, а дальше идет расшифрование с помощью BigInteger.ModPow
При этом, изначально я напутал с терминологией, считая открытый ключ шифрующим. этой ночью с ней разобрался.
Полностью, итоговый метод таков:
private static License Decrypt(byte[] array)
{
License lic;
if (sExponent == 0)
{
GetKeys();
}
try
{
//расшифровка
BigInteger encrLic = new BigInteger(array);
BigInteger decrLic = BigInteger.ModPow(encrLic, sExponent, sModulus);
byte[] decr = decrLic.ToByteArray();
//десериализация
MemoryStream config = new MemoryStream(decr);
BinaryFormatter serial = new BinaryFormatter();
lic = (License)serial.Deserialize(config);
} catch(Exception e)
{
Log.AddLog(e.ToString());
return null;
}
return lic;
}
Я проверил на ваших строках из вопроса — там Exponent в открытом ключе равна D в закрытом.
Ну, если вы отказались от библиотеки вообще — да, такое будет работать. Из вашего исходного ответа было не понятно что именно вы сделали.
Ну, если вы отказались от библиотеки вообще — да, такое будет работать. Из вашего исходного ответа было не понятно что именно вы сделали.
>Я проверил на ваших строках из вопроса — там Exponent в открытом ключе равна D в закрытом.
Ой, чего я только не делал с ключами в тестовом проекте… В частности, в задании есть и такая строка: «Почитал про RSA, попробовал вместо экспоненты подсунуть секретную экспоненту, пишет плохие данные...»
>Ну, если вы отказались от библиотеки вообще — да, такое будет работать. Из вашего исходного ответа было не понятно что именно вы сделали.
Ок. спасибо за общение и анализ.
Ой, чего я только не делал с ключами в тестовом проекте… В частности, в задании есть и такая строка: «Почитал про RSA, попробовал вместо экспоненты подсунуть секретную экспоненту, пишет плохие данные...»
>Ну, если вы отказались от библиотеки вообще — да, такое будет работать. Из вашего исходного ответа было не понятно что именно вы сделали.
Ок. спасибо за общение и анализ.
В принципе, PKCS #1 (RFC 3447) вполне допускает редуцированный вариант закрытого ключа (d, n), но реально его мало кто использует.
В данном случае, всё выглядит как самодельный алгоритм на базе RSA, т. к. в
Disclaimer: я не специалист в криптографии и реальное использование описанного ниже кроме как для экспериментов крайне не рекомендуется.
Использовать
В данном случае, всё выглядит как самодельный алгоритм на базе RSA, т. к. в
RSAEncrKey в качестве открытой экспоненты лежит то, что в закрытом ключе лежит в поле D (закрытой экспоненты), а экспонента используется стандартная (0x010001, в base64 — AQAB). Т. е. всё вывернуто.Disclaimer: я не специалист в криптографии и реальное использование описанного ниже кроме как для экспериментов крайне не рекомендуется.
Использовать
e вместо d и наоборот в теории можно, но e не должно быть легкоугадываемым (или тем более известным, как в данном случае). Ну и dP, dQ, invQ должны строится против нового d, а не оставаться построенными на основе старого d.Вы не правы, это все-таки операция цифровой подписи, просто без хэша.
http://life-prog.ru/view_teorinfo.php?id=10
почему обычно шифруют хэш? потому что он короче ключа. Но у меня сами данные короче ключа, и потому их можно использовать в качестве хэша.
П.с. и да, вы-таки заставили меня усомниться в том материале, что я слушал четыре года назад.
http://life-prog.ru/view_teorinfo.php?id=10
почему обычно шифруют хэш? потому что он короче ключа. Но у меня сами данные короче ключа, и потому их можно использовать в качестве хэша.
П.с. и да, вы-таки заставили меня усомниться в том материале, что я слушал четыре года назад.
В-третьих, у меня нет доступа к серверу лицензии и заказчик не хочет его давать. [...] Ну а так, да, я совершаю типичную операцию цифровой подписи
Эти два тезиса противоречат друг другу. Вы не можете совершать операцию цифровой подписи, ее — или не ее — совершает сервер.
Просто, криво реализованную Майкрософтом.
У MS есть прекрасный класс CmsSigner, который не менее прекрасно реализует цифровую подпись.
Эти два тезиса противоречат друг другу. Вы не можете совершать операцию цифровой подписи, ее — или не ее — совершает сервер.
Сервер умеет шифровать данные. Если в запросе есть ключ, то к этой шифровке прикрепляются открытые данные.
Так как я научил клиент расшифровывать данные без открытого ключа(на самом деле, я изначально напутал с терминологией, назвав открытым ключом шифрующий, а открытый — это не шифрующий, это тот, который можно передать открыто), то я гордо сказал, что совершаю операцию цифровой подписи… Извините, если ввел в заблуждение.
Так как я научил клиент расшифровывать данные без открытого ключа(на самом деле, я изначально напутал с терминологией, назвав открытым ключом шифрующий, а открытый — это не шифрующий, это тот, который можно передать открыто), то я гордо сказал, что совершаю операцию цифровой подписи…
Извините, а какая — в вашем случае — связь между расшифровкой данных и цифровой подписью?
Операция цифровой подписи — это операция, когда для расшифровки данных нужен открытый(доступный для всех) ключ.
Так как обычно данные превышают размер ключа, то, для увеличения быстродействия алгоритма проверки цифровой подписи, сами данные передаются открыто, а шифруется только хэш этих данных. Соответственно, операция шифрования называется подписыванием, а дешифрования( и если есть хэш, то сверка хэшей) — проверкой подписи.
Так как обычно данные превышают размер ключа, то, для увеличения быстродействия алгоритма проверки цифровой подписи, сами данные передаются открыто, а шифруется только хэш этих данных. Соответственно, операция шифрования называется подписыванием, а дешифрования( и если есть хэш, то сверка хэшей) — проверкой подписи.
Так как обычно данные превышают размер ключа, то, для увеличения быстродействия алгоритма проверки цифровой подписи, сами данные передаются открыто, а шифруется только хэш этих данных.
В цифровой подписи всегда есть два экземпляра данных — те, которые подписаны, и сама подпись (подпись считается от хэша, а не от данных, потому что так эффективнее с точки зрения вычислений). У вас так же?
подпись считается от хэша, а не от данных, потому что так эффективнее с точки зрения вычислений
С точки зрения каких вычислений? ЗАЧЕМ мне считать ЕЩЕ и хэш, если у меня сами данные меньше ключа?
В цифровой подписи всегда есть два экземпляра данных — те, которые подписаны, и сама подпись. У вас так же?
Нет, у меня только данные. Данных там, на самом деле, очень мало — 32 байта, а ключ почему-то используется на 4096бит.
Нет, у меня только данные.
Тогда у вас нет цифровой подписи. Вы получили криптотекст, вы расшифровали его с помощью открытого ключа, вы получили нечто. Откуда вы знаете, что криптотекст не был сгенерен без использования закрытого ключа?
Потому что, если он не был сгенерен без использования закрытого ключа, я не смогу его расшифровать в 32 байта, один из которых — контрольный.
Ключ зашит в программу, злоумышленник не может его подменить.
Ключ зашит в программу, злоумышленник не может его подменить.
Потому что, если он не был сгенерен без использования закрытого ключа, я не смогу его расшифровать в 32 байта, один из которых — контрольный.
Как минимум, replay attack в полный рост.
Эээ… вы можете рассказать как проводить эту атаку, имея на руках ключ на 4096 и 32 байта конечного результата?
Replay attack проводится на канал обмена данными. Перехватили сообщение, потом подсунули его вашей программе.
Это отдельная задача И я не знаю как ее решить, учитывая что данные сохраняются в файл и лежат на жестком диске. Т.е. любой их может взять себе и спокойно размножить.
Если подскажите куда копать — буду сильно благодарен.
Если подскажите куда копать — буду сильно благодарен.
Копать в сторону подписей от изменяющихся данных, очевидно. Детальнее подсказать, не зная условий, я не могу.
Условия… Есть сервер лицензий, у каждого получателя своя пара ключей открытый-закрытый.
При этом, открытый жестко вшивается в сам экзешник.
Соответственно, в зависимости от клиента, ему выдается файл лицензии.
Надо гарантировать, что клиент не будет и размножать и передавать в третьи руки, при условии, что программа может работать в отрыве от интернета.
У меня есть только одна идея — привязывать программу к железу… или софту в процессе получения лицензии.
Тогда клиент всегда сможет получить еще один ключ(в разумных пределах), но не сможет передать никому другому.
Вопрос в том как это сделать...
При этом, открытый жестко вшивается в сам экзешник.
Соответственно, в зависимости от клиента, ему выдается файл лицензии.
Надо гарантировать, что клиент не будет и размножать и передавать в третьи руки, при условии, что программа может работать в отрыве от интернета.
У меня есть только одна идея — привязывать программу к железу… или софту в процессе получения лицензии.
Тогда клиент всегда сможет получить еще один ключ(в разумных пределах), но не сможет передать никому другому.
Вопрос в том как это сделать...
Но вообще, все, что надо сделать — это решить уравнение вида xd ≡ m modulo n, где d и n известны, а m задается атакующим. При этом x — мал (вы что-то говорили о 32 байтах, да?), и поэтому мы можем просто решить ее перебором.
Блин. Только зашифрованные данные(ака подпись). Извините, уже почти сплю. Но интересно.
Я думаю, правильного ответа на вопрос, поставленный в заголовке, не существует. Есть аргументы в пользу обеих точек зрения, потому скажу, как вижу я. Я не являюсь программистом и разработчиком в полном смысле этого слова — я регулярно пишу небольшие приложения (в основном, server-side JS) и даже получаю за это деньги, но для меня это скорее хобби — поэтому, вероятно, моё мнение не совсем релевантно. Тем не менее…
Я считаю, что алгоритмы и вообще глобальные основы знать надо. Это не только может серьёзно помочь в работе, но и даёт возможность развиваться дальше. Лично мне базовых знаний часто не хватает, потому что фундаментального образования в области точных наук и программирования я не имею. В итоге переход от «говнокодить» и писать лапшу из решений, вычитанных на SO или в чужом коде, который мне достался в наследство, к нормальной разработке мне давался (и даётся) тяжело. Я иногда открываю для себя элементарные вещи, которые, по-хорошему, люди узнают, когда начинают учиться. Я не всегда вижу очевидные решения, потому что не знаю инструментов или идеи, которые помогли бы мне на них выйти.
В целом проблема касается не только программирования, но и других областей знания — чтобы делать что-то стабильно хорошо, надо понимать, что именно ты делаешь и почему. Можно, конечно, раз за разом ходить проторенной ранее кем-то тропкой и быть довольным уже тем, что идёшь, но настоящим специалистом так не станешь.
Я считаю, что алгоритмы и вообще глобальные основы знать надо. Это не только может серьёзно помочь в работе, но и даёт возможность развиваться дальше. Лично мне базовых знаний часто не хватает, потому что фундаментального образования в области точных наук и программирования я не имею. В итоге переход от «говнокодить» и писать лапшу из решений, вычитанных на SO или в чужом коде, который мне достался в наследство, к нормальной разработке мне давался (и даётся) тяжело. Я иногда открываю для себя элементарные вещи, которые, по-хорошему, люди узнают, когда начинают учиться. Я не всегда вижу очевидные решения, потому что не знаю инструментов или идеи, которые помогли бы мне на них выйти.
В целом проблема касается не только программирования, но и других областей знания — чтобы делать что-то стабильно хорошо, надо понимать, что именно ты делаешь и почему. Можно, конечно, раз за разом ходить проторенной ранее кем-то тропкой и быть довольным уже тем, что идёшь, но настоящим специалистом так не станешь.
Это кстати частый кейс. Я сам — электромеханик и всю жизнь наверстываю академические знания из "смежной" области, перечитав десятки толстых книжек. Зато со временем фильтруешь теоретическую воду и выбираешь зерна.
Хорошо, когда область смежная, а я по образованию историк (ха-ха), а по основной профессии редактор и переводчик. Несмотря на то, что я с программированием в той или иной степени имею дело уже почти двадцать лет, до сих пор иногда оказывается, что какие-то «азы» мне оказываются неизвестны. Бывает очень обломно.
Зато вы практик и скорее всего знаете столько тонкостей и граблей, что сможете вывести проект к цели не затопив :-) Если мы программируем, значит это видимо наше хобби, страсть. А страсть развивает в человеке все что нужно и даже больше — чем образование из под палки родителей.
У меня есть хороший знакомый — техдир. По образованию — египтолог. Но умнейший человек, как архитектор — принимает оптимальные решения, проекты идут, успешен :-)
Для работы знать не нужно. Достаточно просто иметь минимальное предствавление о алгоритмах. Нормальный инженер при необходимости (что в обычной прикладной разработке бывает не часто) поднимет нужные материалы, выберет оптимальные алгоритмы и реализует задачу. В прикладной разработке чем проще код тем лучше, лучше использовать библиотечные реализации.
Знать нужно только для собеседований в большие компании. Так как там берут с расчетом что без проблем смогут тебея кидать на любые проекты так как "академическая база" хорошая.
Знать нужно только для собеседований в большие компании. Так как там берут с расчетом что без проблем смогут тебея кидать на любые проекты так как "академическая база" хорошая.
О Господи, опять началось! Я ещё понимаю вопрос, 'а нужно ли программисту знать математику?', но вопрос 'нужно программисту знать алгоритмы?' уже за гранью добра и зла. Что же с нами стало?
Проблема в том, что программисты лезут в область хардкорной математики и чудят. И наоборот, сильно умные ребята лезут кодить и рождают говнокод.
Я даже не буду комментировать Вашу фразу, ибо у Вас какое-то очень необычное представление о промышленном программировании. Впрочем, всего несколько слов. Я не знаю, где Вы нашли программистов, любящих лезть в математику, насколько я знаю, обычно они боятся её, как черти ладана. То, к чему Вы призвали, называется разделением труда и существует уже очень много лет (как минимум несколько тысяч), но в последнее время фирмы по причине кажущейся экономии или из злого умысла — я не знаю, нанимают, скажем, трёх программистов средней или низкой квалификации, которые как кодеры ещё ничего, но инженеры из них никакие. Вместо того, чтобы нанять одного архитектора, одного программиста и одного тестировщика, ну и нескольких временных консультантов из предметной обасти — видимо, наивно полагая, что три девушки сироты выносят и родят ребёнка быстрее, чем одна из хорошей обеспеченной семьи с папой, мамой и бабушкой в Израиле. В общем, такие дела.
Не, это действительно годный троллинг-наброс.
Мне кажется, что подойти можно с другой стороны. Нужно ли программисту знать, как решается квадратное уравнение? Может, и не нужно, но как же вы можете этого не знать, если тему проходят в средней школе?
Курс алгоритмов — неизбежный этап в обучении программированию от Австралии до Норвегии. Предположим, я только начинаю учиться программировать. ОК, написали сначала "Hello, world", потом "Hello, %username%", а дальше-то что? Что можно делать с этими буковками? Выучили понятие массива — отлично, а давайте мы теперь найдём в нём требующееся значение. Нашли? А давайте теперь отсортируем по возрастанию, чтобы данные были как в телефонном справочнике. Замечательно. А давайте теперь поищем значение в отсортированном массиве. Ага! Совсем иначе всё выглядит, да?..
Выше вон писали: зачем программировать, если любую программу можно скачать в интернете? Штука в том, что начинающий программист за первый год (если не больше) обучения в принципе не напишет ничего такого, чего нельзя скачать в интернете. Но учиться же на чём-то надо. Аналогично: студент-химик переливает реактивы в пробирках, хотя на производстве никто ничего переливать не будет; студент-токарь вытачивает детали на станке, которые никогда в жизни больше вытачивать не будет; пианист играет гаммы и этюды, которые никогда больше не сыграет, и так везде.
Если человек ухитрился пройти мимо вот этого этапа обучения, я бы в принципе поостерёгся иметь с ним дело. Пёс его знает, что у него в голове. Это по моим понятиям что-то вроде чатбота: да, наверно, он может умело отвечать на разные вопросы в течение десяти минут, но рано или поздно где-то обнаружится фантастическая дыра, которая сделает дальнейшую работу решительно невозможной.
Другой вопрос состоит в том, насколько важно иметь библиотеку алогоритмов в голове. Ведь ясно, что в университете даже за годовалый курс можно едва-едва освоить книгу Кормена (и то, вероятно, не целиком), а уж всякие специализированные вещи явно остаются за бортом. Не знаю. Наверно, не очень важно. Для меня скорее важно на книге Кормена и аналогичных вырастить в голове некую "чуйку", которая поможет найти в литературе готовый алгоритм по описанию задачи.
Ну то есть возникает на практике какая-то задача, и надо сразу понять: это что-то совсем узкое, и надо думать самому, или достаточно широкое, чтобы готовый алгоритм можно было найти? Если можно найти, то как переформулировать задачу, чтобы найти? А как и где искать?.. Ну и так далее.
А какие-то совсем базовые вещи вроде списков, деревьев, хэш-таблиц, алгоритмов сортировки и поиска, обхода графов и т.п., конечно, надо знать. Но это довольно скромный объём знаний, и опять-таки, пройти мимо них в реальной жизни довольно трудно.
Мне кажется, что подойти можно с другой стороны. Нужно ли программисту знать, как решается квадратное уравнение? Может, и не нужно, но как же вы можете этого не знать, если тему проходят в средней школе?
Курс алгоритмов — неизбежный этап в обучении программированию от Австралии до Норвегии. Предположим, я только начинаю учиться программировать. ОК, написали сначала "Hello, world", потом "Hello, %username%", а дальше-то что? Что можно делать с этими буковками? Выучили понятие массива — отлично, а давайте мы теперь найдём в нём требующееся значение. Нашли? А давайте теперь отсортируем по возрастанию, чтобы данные были как в телефонном справочнике. Замечательно. А давайте теперь поищем значение в отсортированном массиве. Ага! Совсем иначе всё выглядит, да?..
Выше вон писали: зачем программировать, если любую программу можно скачать в интернете? Штука в том, что начинающий программист за первый год (если не больше) обучения в принципе не напишет ничего такого, чего нельзя скачать в интернете. Но учиться же на чём-то надо. Аналогично: студент-химик переливает реактивы в пробирках, хотя на производстве никто ничего переливать не будет; студент-токарь вытачивает детали на станке, которые никогда в жизни больше вытачивать не будет; пианист играет гаммы и этюды, которые никогда больше не сыграет, и так везде.
Если человек ухитрился пройти мимо вот этого этапа обучения, я бы в принципе поостерёгся иметь с ним дело. Пёс его знает, что у него в голове. Это по моим понятиям что-то вроде чатбота: да, наверно, он может умело отвечать на разные вопросы в течение десяти минут, но рано или поздно где-то обнаружится фантастическая дыра, которая сделает дальнейшую работу решительно невозможной.
Другой вопрос состоит в том, насколько важно иметь библиотеку алогоритмов в голове. Ведь ясно, что в университете даже за годовалый курс можно едва-едва освоить книгу Кормена (и то, вероятно, не целиком), а уж всякие специализированные вещи явно остаются за бортом. Не знаю. Наверно, не очень важно. Для меня скорее важно на книге Кормена и аналогичных вырастить в голове некую "чуйку", которая поможет найти в литературе готовый алгоритм по описанию задачи.
Ну то есть возникает на практике какая-то задача, и надо сразу понять: это что-то совсем узкое, и надо думать самому, или достаточно широкое, чтобы готовый алгоритм можно было найти? Если можно найти, то как переформулировать задачу, чтобы найти? А как и где искать?.. Ну и так далее.
А какие-то совсем базовые вещи вроде списков, деревьев, хэш-таблиц, алгоритмов сортировки и поиска, обхода графов и т.п., конечно, надо знать. Но это довольно скромный объём знаний, и опять-таки, пройти мимо них в реальной жизни довольно трудно.
Аналогично: студент-химик переливает реактивы в пробирках, хотя на производстве никто ничего переливать не будет; студент-токарь вытачивает детали на станке, которые никогда в жизни больше вытачивать не будет; пианист играет гаммы и этюды, которые никогда больше не сыграет, и так везде.
Химики _напроизводстве, которые занимаются разработкой новых техпроцессов — будут, переливают. Постоянно. Если на производстве такого подходящего химика и лаборатории нет или ресурсов недостаточно, производство идёт в университет и заказывает разработку или анализ им. То есть, я это постоянно наблюдаю на примере, например, ЭФКО и химфака ВГУ. Правда, сейчас пробирками и при обучении-то не особо пользуются. Пользуются колбами, часто с отводами (Клайзена, Арбузова — т. е. для перегонки); нагревателями, холодильниками, дефлегматорами, вакуум-насосами и манометрами, и всё это в лаборатории, как при обучении, студентами, так и при работе, инженерами.
И про пианистов неправда ваша Как-то был на мастер-классе Жаки Терассона, это такой джазовый пианист, довольно известный и очень хороший музыкант. Там у него прямо спросили — вы гаммы часто играете? Он ответил: каждый день так разминаюсь.
И вполне понятно, это действительно разминка мышц, которые двигают пальцами. Если программисту в общем-то пофигу как быстро он будет нажимать на клавиши и сможет ли надёжно регулировать усилие, то для пианиста это вопрос первостпенной важности, поэтому и он разминается каждый раз.
Мне кажется, подобная ситуация присутствует во всём. Нужно постоянно тренировать все органы, в том числе — мозг, для чего обязательно необходимо нагружать его сложными задачами, которые раньше не попадались и для которых решения он не знает (ну или забыл). Другими словами, научился дёргать струны на гитаре — пойди, поучись рисовать.
Хорошо, пианист разминается гаммами, но не играет их на концертах. Чем разминается программист (или музыкант) — его личное дело. Можно разминаться как раз реализацией алгоритмов. Мы же сейчас говорим о том, что люди делают не ради разминки, а конкретно на работе. Про химиков рассуждать не берусь, но подозреваю, что те, кто занимается разработкой новых техпроцессов — это аналог тех программистов, которые на работе разрабатывают алгоритмы :) То есть явно не средне-стандартный уровень.
Да ну? Не играет? Вы наверное на концертах не бываете.
Возьмите любую популярную мелодию. Давайте, Yesterday. Соль-фа-фа, ля-си-до-диез-ре-ми-фа-ми-ре-ре, ре-ре-до-си-бемоль-ля-соль-си-до-до… Всё ещё не видите гаммы? Хорошо, почитайте ноты Баха, хотя бы знаменитую токкату и фугу ре-минор.
А у джазовых гамм и того больше, там поди половина импровизаций — гамма на соответствующем текущей гармонии звукоряде. Там просто гаммы сложнее, не простые диатонические, как в примере выше.
Гаммы — это основа мелодий, а не разминка для рук.
А любому кодеру время от времени нужно реализовывать алгоритмы уже хотя бы затем, чтобы не появлялись перлы вида if len(str(bool))==4. Я не говорю про проекты, но разминаться нужно обязательно.
Возьмите любую популярную мелодию. Давайте, Yesterday. Соль-фа-фа, ля-си-до-диез-ре-ми-фа-ми-ре-ре, ре-ре-до-си-бемоль-ля-соль-си-до-до… Всё ещё не видите гаммы? Хорошо, почитайте ноты Баха, хотя бы знаменитую токкату и фугу ре-минор.
А у джазовых гамм и того больше, там поди половина импровизаций — гамма на соответствующем текущей гармонии звукоряде. Там просто гаммы сложнее, не простые диатонические, как в примере выше.
Гаммы — это основа мелодий, а не разминка для рук.
А любому кодеру время от времени нужно реализовывать алгоритмы уже хотя бы затем, чтобы не появлялись перлы вида if len(str(bool))==4. Я не говорю про проекты, но разминаться нужно обязательно.
пианист играет гаммы и этюды, которые никогда больше не сыграет,
Это не так. Гаммы (и арпеджио) состоят из технических элементов (в первую очередь — аппликатурных решений), которые есть во всем, что играет пианист. Поэтому игра гамм напрямую влияет на то, как человек играет произведения. Более того, гаммы прекрасны тем, что их, как и любое упражнение, можно просто повторять каждый день, не имея необходимости что-то изобретать.
Что характерно, то же самое относится и к программистам. С одной стороны, в повседневных задачах регулярно встречается что-то, что унаследовано из классических алгоритмов (в первую очередь, конечно, разные варианты рекурсивных решений, либо D&C, либо динамические). А с другой стороны, тот же Мартин пишет, что программисту полезна ежедневная отвлеченная практика (те же гаммы и этюды, просто программные).
А я иногда сортирую методом пузырька...
Уиии! Побольше бы таких статей. Побольше бы! Почему?
Ну, люди ж соглашаются с этими постулатами. Что не надо знать алгоритмы, как работает база, как устроен компилятор ЯП, на котором работаете. Это ж проще, действительно! Зачем напрягаться?
Таких кодеров (вы уж извините), становится всё больше. И я этому очень рад. Почему?
Потому что чем больше кодеров, тем выше моя востребованность на рынке труда.
Ну, люди ж соглашаются с этими постулатами. Что не надо знать алгоритмы, как работает база, как устроен компилятор ЯП, на котором работаете. Это ж проще, действительно! Зачем напрягаться?
Таких кодеров (вы уж извините), становится всё больше. И я этому очень рад. Почему?
Потому что чем больше кодеров, тем выше моя востребованность на рынке труда.
Правильно, больше обезьянок тупых и уверенных в своей непогрешимости =) И никогда мы без работы не останемся.
Однако тем выше вероятность, что на новом месте работы вам придётся разгребать авгиевы или чьи-то ещё конюшни кода.
Согласен. Только вот разгребать их всегда. Даже за собой. Знаете какой я ужасный код писал 4-5 лет назад? Бррр.
Но это надо принять. Это неотъемлемая часть прикладного программиста.
Я разбирался в коде на ерланге, c, c++ и php.
Да, это больно. Иногда противно. Иногда ты поворачиваешься к окну и закуриваешь сигарету (это потом ты вспоминаешь, что много лет уже не куришь) и смотришь вдаль.
Но, в том числе, в этом состоит моя работа.
Но это надо принять. Это неотъемлемая часть прикладного программиста.
Я разбирался в коде на ерланге, c, c++ и php.
Да, это больно. Иногда противно. Иногда ты поворачиваешься к окну и закуриваешь сигарету (это потом ты вспоминаешь, что много лет уже не куришь) и смотришь вдаль.
Но, в том числе, в этом состоит моя работа.
Приглашаю автора на любое соревнование на kaggle.com
Пусть докажет нам, что зная только названия функций, он займет, ну не первое место, ну хотя бы в топ-10% попадет (да, да, там процент конце).
Пусть докажет нам, что зная только названия функций, он займет, ну не первое место, ну хотя бы в топ-10% попадет (да, да, там процент конце).
Я вам другую задачку поставлю, не абстрактную. Есть клиент с требованиями. Выбираете язык и реализуете, можно не быстро. Затем клиент меняет требования. Задача — внести минимум изменений в код. Вперед! 99% олимпиадников — сдохнут, выживут самые опытные и разумные.
"прикладное" программирование и "системное" — две разные вещи.
от прикладника нужно умение грамотно и качественно, в срок делать стабильный и поддерживаемый код, без особых сложностей.
сложные моменты как раз реализует условно "системный" программист — с более глубоким знанием алгоритмов, возможно, изобретая что-то новое (новый проект/либу как минимум).
Где сидят эти личности — в одном человеке, в одной фирме или на разных полушариях — не существенно. Главное, чтобы между ними был контакт.
от прикладника нужно умение грамотно и качественно, в срок делать стабильный и поддерживаемый код, без особых сложностей.
сложные моменты как раз реализует условно "системный" программист — с более глубоким знанием алгоритмов, возможно, изобретая что-то новое (новый проект/либу как минимум).
Где сидят эти личности — в одном человеке, в одной фирме или на разных полушариях — не существенно. Главное, чтобы между ними был контакт.
на kaggle вполне реальные задачи. По крайней мере, строя модели классификации в своей работе, я именно с такими же сталкивался. Так что велком.
Выживут те, кто имеет опыт работы с переделыванием кода, и особенно — чужого.
Интересно, как автор себе представляет отбор программистов, которые будут разрабатывать не светофор на ассемблере, где нет ни одного алгоритма, а технологии типа поиска и распознавания голоса. У меня есть несколько предположений, но позволю сначала высказаться.
Технологии классического поиска (IR), на мой взгляд, относительно просты и примитивны, иногда с небольшой порцией математики (чуток кластеризации, чуток машинного обучения). К ним бы я допустил программистов на java или другом языке со сборкой мусора () под чутким контролем аналитика.
Технологии посложнее, типа NLP и распознавания речи — неизмеримо сложнее, там много математики и машинного обучения. Поэтому к ним бы программистов напрямую не подпустил. Поручил бы математикам разобрать последние паперы, сделать прототип модельки, в которой нужно соединить правильно алгоритмы, поиграться с ней в R и только когда она покажет хороший Recal/Precision и/или другие подходящие к проблематике метрики — спустить задачку инженерам. Давать инженерам возможность выбирать алогоритм обучения нейронки, моделей маркова, дип-ленинга — я бы не в коем случае не рекомендовал! Пусть программисты отвечают за код расширяемый без багов и копипаста, и не лезут в научные области без подготовки :-)
Технологии посложнее, типа NLP и распознавания речи — неизмеримо сложнее, там много математики и машинного обучения. Поэтому к ним бы программистов напрямую не подпустил. Поручил бы математикам разобрать последние паперы, сделать прототип модельки, в которой нужно соединить правильно алгоритмы, поиграться с ней в R и только когда она покажет хороший Recal/Precision и/или другие подходящие к проблематике метрики — спустить задачку инженерам. Давать инженерам возможность выбирать алогоритм обучения нейронки, моделей маркова, дип-ленинга — я бы не в коем случае не рекомендовал! Пусть программисты отвечают за код расширяемый без багов и копипаста, и не лезут в научные области без подготовки :-)
Это, конечно, не более чем идеологические детали, но интересно вы как-то упорядочили по сложности: IR < NLP. Вообще, IR область более широкая, а NLP — более узкая. Как раз на примере поисковых систем. в NLP, к тому же кроме математики есть еще и лингвистика, которая подтягивает свой набор специфических сложностей, поэтому, одной математики маловато даже будет, на самом деле. Короче, вашу идею понял. Однако, вот в чем вопрос: вот возьмем Deep learning к примеру. Кто должен разрабатывать и поддерживать библиотеки для deep learning'а — первые или вторые? Если чистые девелоперы — то им нужно четкое ТЗ с точностью до формулы. Ну окей разработали, а потом фиксы и улучшения — через оформление документа "Change request specification" аля аутсорс разработка на каждый чих? Если условные "математики" — то высокопроизводительную либу они не сделают, без знания низкоуравневой специфик и работы С++, GPU, итд. В общем, я к тому, что спрос на людей, которые знают, алгоритмы и технологии программирования все еще есть и будет.
Хех, я как раз на днях запостил патч для Python, заменяющий 2400 строк кода (валидация синтаксического дерева, написанная кем-то вручную — по отдельной функции для каждого типа узлов) тридцатью (ДКА).
Подозреваю, что автор исходного кода думал так же, как автор этого поста: "а зачем тут алгоритмы? и так же всё работает!"
Подозреваю, что автор исходного кода думал так же, как автор этого поста: "а зачем тут алгоритмы? и так же всё работает!"
Крутой кейс. Но если человек в проекте с дедлайном через неделю и вместо регулярки начинает умничать и писать модуль на С c конечным автоматом, не успевает и потом этот модуль глючит еще год, засыпая сервер корками — согласитесь, что-то тут не то :-)
Вот именно для этого и нужно знать алгоритмы — чтобы понимать, когда лучше не умничать и влепить лобовое решение, а когда лучше убрать руки с клавиатуры и пару часов порисовать диаграммы на бумажке.
это пример "интеллектуального", но "глупого" разработчика. Умный не будет пихать свой интеллект и знания всюду, только потому, что они у него есть.
Хотел бы увидеть статью на эту тему. Это действительно очень круто.
Я б охотно, но пусть мой патч сначала отревьюят.
Кто-нибудь из хабраобитателей может ненавязчиво пнуть мейнтейнеров, чтобы они уделили моему патчу внимание?
http://bugs.python.org/issue26526
Кто-нибудь из хабраобитателей может ненавязчиво пнуть мейнтейнеров, чтобы они уделили моему патчу внимание?
http://bugs.python.org/issue26526
Готово! https://habrahabr.ru/post/314062/
а сколько в скорости выиграли, если не секрет (понятно, на ваших вычислительных ресурсах)?
НЛО прилетело и опубликовало эту надпись здесь
Вопрос поставлен не корректно. Конечно все бы хотели хорошо разбираться в алгоритмах. Только вот не каждый готов тратить время на это. Особенно когда нужно срочно изучить очередной модный фреймворк, чтобы быть в тренде и зарабатывать себе на жизнь.
Вчера буквально друг-преподаватель рассказал про одного своего студента. Этот студент, скажем так, плохо учил математику и взялся отсортировать массив обезьянней сортировкой.
Ну преподаватель его пожалел, дал ему массив всего из восьми элементов, поэтому сортировка заняла всего лишь час.
Это я к тому, что понимать O-нотацию программисту обязательно необходимо. Любому. А это, видите ли, из оперы анализа алгоритмов, которая предполагает знание их устройства.
Ну преподаватель его пожалел, дал ему массив всего из восьми элементов, поэтому сортировка заняла всего лишь час.
Это я к тому, что понимать O-нотацию программисту обязательно необходимо. Любому. А это, видите ли, из оперы анализа алгоритмов, которая предполагает знание их устройства.
> поэтому сортировка заняла всего лишь час
А на чем же он её сортировал? Средняя сложность обезьяньей сортировки — n! * n, т.е. в среднем на 8 элементов порядка 300 тыс перестановок. Генераторы псевдослучайных чисел нынче неплохие, так что вероятность большого отклонения от медианы невелика. И в любом случае на захудалой персоналке 8 элементов абыззяна отсортирует за доли секунды.
А на чем же он её сортировал? Средняя сложность обезьяньей сортировки — n! * n, т.е. в среднем на 8 элементов порядка 300 тыс перестановок. Генераторы псевдослучайных чисел нынче неплохие, так что вероятность большого отклонения от медианы невелика. И в любом случае на захудалой персоналке 8 элементов абыззяна отсортирует за доли секунды.
Годный вброс для дискуссии, но в целом статья ни о чем...
Для 90% рутинного каждодневного кодинга в тривиальных области типа биллинга и учета, знание алгоритмов не требуется, имхо. Для оставшихся 10% нетривиальных задач знание алгоритмов возможно потребуется, но не факт, что этого будет достаточно — гораздо важнее может оказаться знать, к примеру, на скольких миллионах записей начнет затыкаться Oracle, с тем чтобы решить, нужен ли он вообще, или может можно файлами обойтись, и исходя из этого оптимально спроэктировать жизненный цикл данных.
Можно успешно кодить в группе 90% большинства, при этом набираться опыта, и постепенно переходить к 10% гуру.
Можно успешно кодить в группе 90% большинства, при этом набираться опыта, и постепенно переходить к 10% гуру.
А нужно ли знать программисту алгоритмы?