Я задал тут вопрос на форуме про шаблоны проектирования, и получил очень интересные ответы.
Теперь интересно знать про алгоритмы.
Как я часто слышу: алгоритмы нужны только для собеседования.
Интересно знать, как часто вам они нужны в работе( и какой сложности, какие нибудь Красно-чёрное деревья, или все ограничивается qsort)?
Сложные ли задачки по алгоритмам на собеседовании?
Ну и стоит ли на это тратить свои силы, или учить что то более важное?
звiдки ви такi взагалi вилазите? алгоритми i структури даних — це перше, що повинен знати девелопер.
але якщо хочеш бути рядовим кодерком на галерцi, то можеш забити.
<хейтерский оффтоп>
Вот лично меня удивляет когда джуниоры спрашивают блин, а стоит ли учить что-то (Си или Алгоритмы, не важно). Да блин, это же само по себе интересно! Ну посмотри и поковыряй их, напиши пару программулек с их использованием. Это же кайф.
Лично я например шаблоны проектирования изучал и рефакторинг не потому что это спрашивают на собеседованиях а потому что это блин круто!
Перед собеседованиями я только повторял или подтягивал совсем открытые пробелы. Причём очень просто: искал список вопросов на собеседование и проходился по ним.
А вот это вот их вечное «блин какой язык программирования учить, бла бла бла» для меня вообще что-то странное. Как они так могут, не понимаю.
Лично я на собеседованиях про алгоритмы не спрашиваю. Но если кто-то кто не джун сделает слияние списков через что-то в стиле list.contains()/list.indexOf() то смотреть я на него буду как на долбоеба.
Но что интересно — в лидерах рынка таким даже техлиды грешат, при чем не доганяют почему после перехода на хешсеты страничка стала грузиться пару мс против пары минут.
Вообще реально надо просто понимать свойства алгоритмов и уметь выбрать нужный в конкретной ситуации, писать их с головы на бумажку — это уже задача олимпиадников а не «промышленных» программистов. Ну или для студентов в очередном припадке учебного маразма :)
Одна из самых приятных вещей, которая осталась у меня после изучения алгоритмов — это какое-то «интуитивное» понимание сложности и времени работы кода, который я читаю или окидываю взглядом.
Смотришь на код, видишь там цикл, пару if-ов, уже есть в голове какая-то оценка, прикидываешь объемы данных и уже понимаешь, что тут что-то не так. Не всегда так получается, иногда за вызовом какой-нибудь функции может быть много чего скрыто, но в целом влияние на мозг положительное.
зовсім не важливо, не треба ніяких алгоритмів і паттернів чи якихось структур даних, головне — нічого не знати про Big O і ніколи не думати, просто копіпастити код з інтернету, він завжди production quality. глянув синтаксис мови, відкрив мануал фреймворку — і вперед. what could possibly go wrong?
найкращий софт пишеться програмістами, які не відрізняють сінглтону від бінарного пошуку, такий софт ніколи не жере зайвих ресурсів, не зависає і працює виключно коректно. часто, саме такий софт найкраще маштабується горизонтально. всі ми користуємося ним кожного дня — наприклад, сайтами, які навіть після проходу по них едблоком настільки швидкі і нересурсоємні, що відчуваєш, ніби можеш відкрити тисячі їх і все одно вони будуть «літати». в незнанні — сила. чим більше ти не знаєш і чим крутіший при тому оффер отримаєш, тим жирніше можна потролити на доу всяких лошків з їхніми, нікому не потрібними сортуваннями і пошуками
-
Тут ситуация для разных языков разная, для .net алгоритмы вообще не нужны, за три года, пару раз приходилось изобретать алгоритмы (для спец. сортировки и тд.), а так вообще тупо следования шаблонам.
Знания основных алгоритмов не важно, важно грамотное умение создать алгоритм самому, а вот научится этому можно изучая стандартные алгоритмы, по этому и спрашивают про стандартные.
Где-то важно, где-то нет.
Собеседования они очень разные, хоть проекты и одинаковые потом окажутся.
В последнее время находятся странные конторы со следующим пособом проводить интервью:
1. Тебя спрашивают, что знаешь, что умеешь, чем гордишься и чем занимался на последних местах работы.
2. Ты отвечаешь на этот вопрос
3. А собеседующий потом на эти темы вопросы нарочно НЕ задаёт, дабы потешить своё ЧСВ.
Даже если вакансия предполагает знание того и другого, тебя на эти темы не спросят вообще.
Хорошо знаешь базы данных и с ними на «ты»? Тебя об этом нарочно не спросят.
Хорошо владеешь алгоритмами и вообще бывший олимпиадник с пшеничными усиками? Тебя не спросят на эту тему ничего.
Боевой английский на уровне upper-intermediate с реальным опытом? Пофиг. Тебя спросят какую-то хрень, которая используется раз в пять лет, предварительно прощупав, что ты это вряд ли знаешь.
Наше айти превращается с цирк с голодными попугаями.
Тебе даже не перезвонят или перезвонят с отказом те, у кого ты отлично и уверенно прошел интервью, и сделают оффер оттуда, где было дурацкое интервью с попытками попустить и спрашивать всякую ерунду и где ты проявил себя не очень.
А по поводу алгоритмов — почитай, попрактикуйся, для общего развития.
Тебе даже не перезвонят или перезвонят с отказом те, у кого ты отлично и уверенно прошел интервью, и сделают оффер оттуда, где было дурацкое интервью с попытками попустить и спрашивать всякую ерунду и где ты проявил себя не очень.
Реальные офферы приходили от контор, куда я на собес приходил с бодуна, и молол всякую хрень.і пікапив хрюш
Знать на память — нет.
Куда важнее уметь придумать-реализовать алгоритм под задачу и оценить метрки в том числе различную «сложность». Особым бонусом будет уметь прочитать существующий код, понять что там происходит и тоже оценить «сложность», корнер кейсы, потенциальные баги, итд. Задрючивание алгоритмических задачек какраз помогает достичь данного навыка.
Но с учетом различных специализаций и готовых фреимворков, это уже не жизненно важный навык, ксожалению.
уметь придумать-реализовать алгоритм под задачу и оценить метрки в том числе различную "сложность«Ну какая то крутая задача разбивается на малые а там есть «гугл», «стэковерфлоу» или "из коробки«- все уже придумано. Мы ж говорим про алгоритмы, а не про архитектуру. А там вложеные циклы подсчитать или чето типа того, ну обучение 30 мин займет. Ну и если леваковый какой то язык тут уже тоже не про алгоритмы, а про собственно «че это за херь написана и что она вообще делает».
А там вложеные циклы подсчитать или чето типа того, ну обучение 30 мин займет.Для людей которые несталкивались — далеко не 30.
Ну какая то крутая задача разбивается на малые а там есть «гугл», «стэковерфлоу» или "из коробки"- все уже придумано.Ну несто нестандартное — редко, но встречаеться, какаянить хитрая сортировка таблиц, или по условию, или с редьюсом, где стандартным Arrays.sort не обойдешся. А если решать брутфорсом, то плохой перформанс.
Ну несто нестандартное — редко, но встречаеться, какаянить хитрая сортировка таблиц, или по условию, или с редьюсом, где стандартным Arrays.sort не обойдешсяНу наверно очень редко. Юзать гуглу тоже ж искуство :) Може челу просто впадло лапатить инет и он, имея соответствующие навыки и время, решил повыё... :) Учитывая всякие НДИ, кучу професуры и 7 000 000 000 народа на нашем шарике, странно что именно чел получил первый раз в истории человечества таск порешать некую задачу...
А если решать брутфорсомcs607521.vk.me/...
Учитывая всякие НДИ, кучу професуры и 7 000 000 000 народа на нашем шарике, странно что именно чел получил первый раз в истории человечества
Юзать гуглу тоже ж искуство :)Иногда написать реализацию быстрее чем найти чтото полезное :-)
Чтонить типа отсортировать банальную матрицу по диагонали — уже тупого готового решения нет. То что гуглиться — в него уже вникать нужно, то оно делает, или не то, и вообще яп другой, уже банальный копи-пейст не сделаешь.
Иногда написать реализацию быстрее чем найти чтото полезное :-)Да. Согласен. Ну тоже
Ну несто нестандартное — редко
Я доктор по нервам и мне не надо знать анатомию и кости? Не думаю, что чувак с таким подходом будет профи.
Энергетик-электрик не понимающий индукции и переходных процессов... Ну такое.
Наизусть все алгоритмы и классы алгоиртмов знать вряд ли стоит, но знать базовые структуры и алгоритмы на текущий момент, чтобы правильно ставить диагноз и делать решения — маст хэв. Иначе это превращается в карго-культ.
Если спросить, или попасть на полноценное техническое собеседование, то оказывается что необходимо знать все эти алгоритмы, структуры данных, шаблоны проектирования, нужно знать про фреймоврки, тестирование, уметь проектировать правильную архитектуру приложений и баз данных, для любых задач: от вывода кораблей в космос до сайтиков-визиток. А потом приходишь на работу, и интегрируешься с микросервисом, который раз в час уходит в себя и падает, а в промежутках между падениями выдает случайные данные. И получается так что и люди вроде не идиоты, и слова правильные говорят, и в сервисе все эти фреймокри и паттерны даже как-то уложены, и алгоритмов нет, в которых можно было бы накосячить, но... раз в час уходит в себя, падает и выдает случайные данные.
Учить алгоритмы? Учить паттерны? Тут скорее стоит не прокачивать свои слабые стороны, а давать развиваться сильным. Прут алгоритмы? — хороший вектор для развития, не засыпаешь на первой странице книги «банды четырех» — дочитай до конца, нравится копаться в новых технологиях — копайся, умеешь смотреть на «бизнес» часть проблемы — хорошее качество, всем надо, но некто ни признается. Хорошие команды делаются не из тех кто знает всего по чуть-чуть, а из сочетания разных хорошо прокаченных скилов(хотя все по чуть-чуть — это тоже скилл as is). На задачу можно смотреть под призмой алгоритмов, под призмой паттернов и под кучей других призм, и если есть разные точки зрения — это хорошо. Хороших команд мало, но в конце-концов в любой момент времени тебе нужна всего одна :)
N.B. мой любимый пример об алгоритмах рожденных суровыми математиками, и инженерами практиками
Списки с пропусками: вероятностная альтернатива сбалансированным деревьям — habrahabr.ru/post/230413
Балансировка красно-черных деревьев не во всякую голову вложится. И быстро оттуда выдувается.
И если на собеседовании, или в тестовом задании соискатель реализует сходу дерево skiplist’ом, а не будем вымучивать из себя «математические» алгоритмы — то я бы поставил более высокую оценку, чем зазубрившему балансировку красно-черных деревьев.
просто потому что в условиях ограничений по времени разработки — совершить ошибку в реализации сложного алгоритма более вероятно, как и неправильно его выбрать, и криво оттюнить под специфику, чем простого.
конечно, если чел планирует развиваться в сторону computer science, а не инженерную, то инженерные хаки у него должны вызывать приступы праведного гнева.
но тогда ему и не в программисты.
Мои знания о красно-чёрных деревьях, кроме очевидной +/- сбалансированости веток, ограничиваются фразой из первого тома Д. Кнута о том, что дополнительных двух бит в каждом узле достаточно для построения красно-чёрного дерева. И что впервые эта идея опубликована где-то в советском журнале. Достаточно ли это для того, чтобы на собеседовании вывести алгоритмы вставки/удаления, я не знаю. Может да, может нет. С другой стороны наверняка найдутся люди, который восстановят алгоритмы не зазубривая их.
Я не знаю, как звучит вопрос на собеседовании, но судя по всему там достаточно общая формулировка, что для меня является скорее уточнением задачи: где и как будет использоваться, куда расширяться... Всё таки реализация алгоритмов, отличная от библиотечной, часто связана с некоторой модификацией для решения других задач. Например, в случае красно-чёрного дерева узел может хранить некоторую дополнительну. информацию
На практике оба варианта кажутся мне примерно одинаковыми по затратам. Всё равно 50% времени уйдёт на написание тестов, которые прогонят алгоритм в разных ситуациях, чтобы исключить ошибки. А остальное время... Ну мне не сложно поднять Д. Кнута чтобы освежить идею, а заодно посмотреть реализацию. Skiplist более понятный, конечно, но рутинного кодирования, где можно допустить ошибку, там тоже достаточно. А если добавить шаблоны, которые позволят настраивать количество и шаг уровней избыточности, то задача резко станет весьма нетривиальной.
наверняка найдутся люди, который восстановят алгоритмы не зазубривая их.конечно найдутся. вопрос только в том — что это за люди. не те ли о которых
Ну мне не сложно поднять Д. Кнута чтобы освежить идею, а заодно посмотреть реализацию.скопипастить с stackoverflow, или с исходника либы на гитхабе — еще проще.
Skiplist более понятный, конечнос какой целью тогда писали пост?
так это ж очевидно для практиков, эмпириков, — инженеров. вот для теоретиков да, эти 0,0...1% — мука. теоретики — это ж богоискатели. иногда — очень полезные.
я тут недавно наткнулся на очередную статью на тему что в основе математического поиска лежит богоискательство — snob.ru/profile/27355/blog/63932
для написания обычных компьютерных программ оно если и не вредно, то избыточно.
Скопипастить можно, но я не доверяю... У Дональда Эрнестовича всё-таки есть описание, которое позволит освежить основную идею, что по готовому коду сделать сложнее. Плюс посмотреть упражнения, которые могут натолкнуть на идею некоторой модификации плюс более оптимального использования в данном конкретном случае. А тащить код не разобравшись в нём как-то не мой стиль.
А тащить код не разобравшись в нём как-то не мой стиль.а кого интересует ваш стиль?
а вот затраты на копание в томах Кнута — да, неприятно для многих.
я же вас ни в чем не переубеждаю, вы хоть лобзиком выпиливайте, — для пром производства мебели без разницы мнение художников.
> Мои знания о красно-чёрных деревьях, кроме очевидной +/- сбалансированости веток, ограничиваются фразой из первого тома Д. Кнута о том, что дополнительных двух бит в каждом узле достаточно для построения красно-чёрного дерева. И что впервые эта идея опубликована где-то в советском журнале.
Вангую, что это было про AVL, а не RB. RB достаточно одного бита :)
Балансировка красно-черных деревьев не во всякую голову вложится. И быстро оттуда выдувается.
Балансировка красно-чёрных деревьев банально запоминается, если вначале разобраться с B-деревьями, а потом узнать, что красно-чёрное дерево это растянутое представление B-дерева с 3 ключами на страницу (не говорю «порядка 4» или как-то ещё, потому что «порядок» B-деревьев каждый определяет, как хочет).
(Другой вопрос — нахрена вообще RB-деревья нужны. Все рассказы, что они быстрее AVL, пока что не подтверждаются.)
Skiplists, конечно, штука прикольная, но многим не понравится недетерминированность.
конечно, если чел планирует развиваться в сторону computer science, а не инженерную, то инженерные хаки у него должны вызывать приступы праведного гнева.
но тогда ему и не в программисты.
Ну почему. Он может писать, например, garbage collector или реализацию структур данных...
Другой вопрос — нахрена вообще RB-деревья нужныа в книжках про алгоритмы — что писать, если они не нужны? может оказаться что не только они.
а так, студентов есть чем грузить. и вот, топикастера толщиной книг по алгоритмам пугать.
Он может писать, например, garbage collectorможет. и то, скорее не писать, а проектировать.
и, более интересный вопрос — а сколько всего в мире сейчас garbage collector’ов, в штуках?
думаю больше сотни, а вот больше ли тысячи?
и сколько нужно для их поддержки программистов?
или реализацию структур данных...это да. Про деревья всегда пример приводят — а вот захочешь писать, или исправить свою БД, и не сможешь!
ужас какой, действительно, как же жить то дальше, ни разу не читавши исходник реализации индексов в мускуле...
Забавно наблюдать как каждый третий пытается в свой комментарий впихнуть побольше умных слов, дабы казаться уххх каким крутым спецом на фоне галерного множества :) градиентный спуск, машинное обучение, хэш функция... Тьфу блин.
градиентный спуск, машинное обучение, хэш функцияЭто элементарные вещи о которых должен знать любой джун, переходящий из трейни.
Это в вашем мире с розовыми пони ;) а в реальности украинского аутсорсинга мне знакомы люди с зарплатами 3+ не знающие сложности быстрой сортировки.
А она динамическая, от NlogN до N^2. Вот и какое число называть?
Лучший и худший случаи :)
Худший случай когда перегреется процессор или начнет сбоить память, а лучший случай, когда сортировку не нужно делать вообще.
«„лучший“ — отсортіруєт, „худший“ — нєт»
Иншалла сортировка. Иншалла сортирует с машаллах сложностью.
Термін «bogosort» заграв новими кольорами!
Зачем? (ну кроме конечно хэш функции)
Градиентный спуск — для решения оптимизационных задач. Если задача выходит за пределы — взять данные из базы и сгенерировать страничку, то это все пригодится. Так как сейчас стало модным AI (различные алгоритмы классификации и оптимизации), то все это скоро начнет использоваться в вебе. А понимать AI фреймворк без понимания механизмов на которых он построен будет выглядеть шаманством.
а) Для класификации, и для того что вы называете «оптимизацией», для «сгенерировать страничку» есть готовые из коробки фреимворки.
б) базис машин лернинга проходиться за месяц ненапряжного курса, чегото там особо знать — не требуеться.
базис машин лернинга проходиться за месяц ненапряжного курса, чегото там особо знать — не требуеться.
Так и Java на некоторых курсах до уровня профессионала изучается за 24 часа. Во всяком случае организаторы курсов гарантируют.
А в машин лернинге — самая сложная часть выделение features, так как неправильном выделении, не тех или лишних, можно получить крайне плохую сходимость. А далее начинается шаманство, посложнее чем оптимизация структуры БД.
Так и Java на некоторых курсах до уровня профессионала изучается за 24 часа.
А в машин лернинге — самая сложная часть выделение features, так как неправильном выделении, не тех или лишних, можно получить крайне плохую сходимость. А далее начинается шаманство, посложнее чем оптимизация структуры БД.С этим никто и не спорит. Однако дело практики, такоеже как и оптимизация БД.
Ой.... как человек, съевший ни одну стаю собак на алгоритмах.... Точно знаю.
Алгоритмы нужны. Вопрос только — в каком объеме? В достаточном, для того, чтобы не стрелять из пушки по воробьям
Моё мнение: это полезно, хотя и не обязательно. С другой стороны, это также не так уж сложно, чтобы не сделать за свою карьеру. Также я знаю интересные проекты, где у заказчика требование ко всем кандидатам знать хорошо основы программирования: алгоритмы и структуры данных, так что на такой интересный проект человек может просто не пройти по минимальным требованиям. У меня ушло на всё про всё где-то неделя активного изучения по книге MIT, javadoc’ам и википедии. Ещё cheatsheet BIG O bigocheatsheet.com помогло.
Скажите зачем в матане учат доказательство теорем, которые были доказаны надцать лет назад и всем хорошо известны?
P.s. похоже очередной троллинг ...
А зачем их учить? Их надо понимать и уметь доказывать самостоятельно.
В том числе и на экзамене. И вот те, кто не понимают, те — учат.
я правильно Вас понял — вы можете не появится ни на одной лекции, а просто по названию предмета «понять» все самостоятельно?
глагол учить и учиться подразумевает не только запоминать (например стихи), а и некий процесс познания.
Только нужно запомнить несколько контрольных точек, а детали пути восстанавливаются. Плюс нужен прокачанный скилл математической зрелости.
о нет, это был просто тролль
Алгоритмы 1)помогают пониманию, какой контейнер выбрать, полезно вцелом.
2) Да для собеседования в Google, Facebook, Amazon, Microsoft, etc.
3) Для разминки мозгов.
4) Если вы работаете с Computer Vision, Machine Learning, NLP, полезно понимать алгоритмы.
Ну еще CNN, Adaboost, Ensemble Learning, Random Forest,...
Если вдруг кто хочет начать изучать алгоритмы, то рекомендую вот этот бесплатный курс:
www.khanacademy.org/...
Изучение алгоритмов: простых и более сложных важно и в том случае, когда необходимо выбрать структуру данных для определенной задачи, на основе этих знаний, можно предсказать как будет вести себя ваше приложение в особо критических местах.
Кроме того, не во всех языках есть стандартная библиотека, вместе с бинарным поиском, например, как в Java Arrays#binarySearch или в C# Array#BinarySearch, вот в JavaScript, например, такого нет... но есть два npm пакета на выбор: binary-search и binarysearch... и какой выбрать? А может свой написать и не добавлять очередную npm-зависимость?
Я считаю, что первое время, и если тема алгоритмов не интересна, то без них можно обойтись. Программисты и так сейчас перегружены новыми языками, новыми библиотеками, новыми базами данных, платформами, контейнерами и интернетами оф сынгс... и для много чего уже есть готовые библиотеки написанные другими людьми... Но если вдруг захочется стать именно этим «другим человеком»...
По поводу комментаторов «алгоритмы не нужны», вспомнился клинический случай, когда один из моих папередников находил пересечение двух множеств при помощи двух вложенных циклов по массивам и как этот гениальный код тормозил.
При том, что проект вобщем-то с алгоритмами вообще не связан был.
Ну быстрее NLogN здесь ничего не светит, хотя если элементы не целые, то может быть и N^2.
Во-первых, светит, т.к. нигде не было сказано, что нельзя выделять дополнительную память, во-вторых NlogN всяко повеселее, чем N^2, а в-третьих, не совсем понял, почему нельзя не целые числа за NlogN обработать?
Как с дополнительной памятью? Если поиск по той же hastable O(1), то добавление элемента O(logM), так что все равно получится NlogM. В общем линейную сложность здесь все равно реально не сделать (можно создать булевый массив вместо Hashtable, там и добавление O(1) и поиск, но это код бессмысленный и беспощадный).
Добавление элемента в хеш таблицу это O(1), такая же сложность как и у поиска. Нет?
Нет. Если самортизировать на ресайзы при росте до существенных размеров, которые происходят при превышении следующего размера и требуют Θ(n), то средняя цена добавления элемента — O(log n), а пиковая — O(n). Рассматривать только идеальный случай слабо заполненной нерасширяющейся таблицы тут неинтересно.
При каком росте? У нас множество фиксированного размера, почему нельзя сразу выделить таблицу достаточного размера?
Вы говорили о хэш-таблице в общем случае, а не в случае конкретной задачи пересечения множеств. Если есть возможность задать размер заранее, тогда, конечно, эта затрата уходит.
Говорил о конкретной задаче, мы же пытаемся найти пересечение множества за O(n) :)
Добавление элемента в хеш таблицу это O(1)это лучший случай, в худшем случае имеем O(n), а реальный получается O(logn). Даже если задать Hashtable(int capacity), то все равно в реальном случае вы получите O(logn).
Можете протестировать просто по скорости работы добавления в Hashtable и булевый массив, так скажем на 1 млн элементов, просто тупо сгенерированных от 0 до 1 млн.
то все равно в реальном случае вы получите O(logn).Что такое «в реальном случае»? В среднем сложность вставки в хештаблицу О(1)
Ну сравните время вставки 1 млн элементов в BitArray и Dictionary, получите разные значения, даже если Dictionary создать как Dictionary(1млн).
Не думали что хеши на самом деле часто совпадают?
Ну сравните время вставки 1 млн элементов в BitArray и Dictionary, получите разные значенияА хэширование само по себе уже ничего не стоит?
Не думали что хеши на самом деле часто совпадают?Насколько часто совпадают — зависит от размера таблицы и типа функции — например, при наличии идеальной хэш функции они не будут совпадать вообще.
Хорошо, вы согласны что через BitArray реализация может быть быстрее чем через Dictionary, если множество не слишком разрежено? В реальном случае ускорение может достигать
Насчет того, что BitArray будет быстрее, я конечно согласен. Я не согласен с тем, что вставка в хэш в среднем будет logN.
Хорошо, может проблема в накладных расходах или чем-то еще, но чтобы получить реально быстрый мердж двух множеств, то лучше использовать bytearray.
Реальная проблема когда нам нужно получить пересечение двух множеств и сравнение идет не прямого равенства, а минимального расстояния между элементами. Вот там может быть даже N^2. Например когда нам нужно вычислить предварительные точки кластеризации для k-means алгоритма.
чтобы получить реально быстрый мердж двух множеств, то лучше использовать bytearrayМердж через хэш — реально быстрый по сравнению с двумя циклами по массивам :)
Во-первых, откуда вы вообще взяли NlogN ? Вы можете это как-то аргументировать?
Во-вторых, интересны детали реализации вашего алгоритма с BitArray. Без использования хеш функции он будет экспоненциальным по памяти. (Например для того, чтобы работать с миллионом элементов из диапазона [0, 10^9] без хеш функции вам придется увеличить размер массива до 10^9)
В-третьих, вы говорите, что будет много коллизий, «много» — это сколько? Если предположить что в Dictionary ровно 1000000 ячеек, а поверьте, в упомянутом вами примере это будет не так (см. ниже), то количество коллизий в среднем будет около 1000000/e или приблизительно 1.58 коллизии на один вставленный элемент. Это значение не будет меняться независимо от объема данных. Так что О(1) это абсолютно справедливая оценка средней скорости.
P.S. я не знаком с реализацией Dictionary (речь о C#?) . Но с очень большой степенью уверенности я могу предположить, что значение параметра конструктора — это начальное количество ячеек, и пока вы будете вставлять миллион элементов, он несколько раз вырастет при достижении пороговых значений l/b. Но даже в этом случае, в среднем вставка работает за О(1)
Кажется, в изначальной задаче не допускалось упрощение до сущностей, которые можно представить битом в BitArray.
вставка как ни крути в каком либо случае O(1)
Как же Вы получите Log N, если у вас размер выделен заранее? Это какая же плохая хеш функция должна быть? :)
Большая О — это мера роста сложности алгоритма от размера набора обрабатываемых данных.
Как можно говорить, что если в большинстве случаев сложность не зависит от кол-ва данных (O(1)), но очень редко требуется перелопатить весь набор данных (O(n)), то в среднем у нас O(log(n))?
Есть понятие аммортизированной сложности, т.е. на большом кол-ве операций, то что у вас называется «в реальном случае» смею полагать. Так вот в описанном случае аммортизированная сложность остается O(1).
С большой O всё непросто, это двузначный символ. Иногда его употребляют в значении Θ (асимптотическая сложность), а иногда в значении верхней оценки с точностью до постоянного множителя.
Навскидку — если можем позволить дополнительную память, то можно два массива объединить в один, а затем пройтись тем же квиксортом, например, попутно заполняя результирующий массив равными элементами, когда они нам встречаются. Получим NlogN.
Во-первых, светит, т.к. нигде не было сказано, что нельзя выделять дополнительную памятьА как можем линейную? Реально интересно, поделитесь.
P.S. Правда, это если считать тот же memcpy для изначального объединения как константный :)
Как уже обсудили выше, хэш будет работать в среднем за линейное время.
Кстати, что характерно, ниже в топике встречался джавист с 10 годами опыта, который даже не знает, что есть такая структура данных, как хэш :)
Навскидку — если можем позволить дополнительную память, то можно два массива объединить в одинКстати, из условия задачи не следует, что входная структура данных обязательно должна быть массивом, так что может и дополнительная память не потребоваться.
можно за N справиться. За N распихать в хешмап первую строку, потом пробежаться по второй и сделать value ++ на том, что уже есть (ключи — сами значения )
Вы пишете так, как будто вложенный цикл, это что-то плохое :)
Одна из самых приятных вещей, которая осталась у меня после изучения алгоритмов — это какое-то «интуитивное» понимание сложности и времени работы кода, который я читаю или окидываю взглядом.
Смотришь на код, видишь там цикл, пару if-ов, уже есть в голове какая-то оценка, прикидываешь объемы данных и уже понимаешь, что тут что-то не так. Не всегда так получается, иногда за вызовом какой-нибудь функции может быть много чего скрыто, но в целом влияние на мозг положительное.
Не всегда так получается, иногда за вызовом какой-нибудь функции может быть много чего скрыто
зовсім не важливо, не треба ніяких алгоритмів і паттернів чи якихось структур даних, головне — нічого не знати про Big O і ніколи не думати, просто копіпастити код з інтернету, він завжди production quality. глянув синтаксис мови, відкрив мануал фреймворку — і вперед. what could possibly go wrong?
найкращий софт пишеться програмістами, які не відрізняють сінглтону від бінарного пошуку, такий софт ніколи не жере зайвих ресурсів, не зависає і працює виключно коректно. часто, саме такий софт найкраще маштабується горизонтально. всі ми користуємося ним кожного дня — наприклад, сайтами, які навіть після проходу по них едблоком настільки швидкі і нересурсоємні, що відчуваєш, ніби можеш відкрити тисячі їх і все одно вони будуть «літати». в незнанні — сила. чим більше ти не знаєш і чим крутіший при тому оффер отримаєш, тим жирніше можна потролити на доу всяких лошків з їхніми, нікому не потрібними сортуваннями і пошуками
жирніше
Дев + знання структур даних/алгоритмів -> Елітний спартанець-весляр at галєра Microsoft/Amazon/Facebook etc.
Дев — знання структур даних/алгоритмів -> Кволий сироїд at галєра Eleks/SoftServe/EPAM etc.
Хулі, успіх :)
занадто тонко, не осилив(
то треба чи ні?
Не усі можуть веслувати на галєрах Microsoft/Amazon/Facebook, де треба знати о-нотації і алгоритми. В декого є призначення — стояти на варті корпоративного ентерпрайзу, українського аутсорсу, багфіксінгу і поїдання сирів, де по великому рахунку ці знання більше як хороший бонус, ніж вимога від бізнесу :)
Прочитал комменты. С точки зрения интереса у людей — все однозначно, многие пишут, что изучают ради интереса. Но вот, если лично у меня другие интересы? Мне, как андроид деву, нравится просто другие либы клацать либо просто технологии изучать. Теперь хочу спросить исключительно (!) у андроид девов и лидов: «На какие алгоритмы стоит обратить внимание? Я имею ввиду только те алгоритмы, которые вы внедряли как минимум один раз»
пригодились алгоритмы по обработке изображений, манипуляции с цветовыми матрицами. Особенно при условии что обработку нужно распараллелить (в случае android на Renderscript).
Лично я на собеседованиях про алгоритмы не спрашиваю. Но если кто-то кто не джун сделает слияние списков через что-то в стиле list.contains()/list.indexOf() то смотреть я на него буду как на долбоеба.
Но что интересно — в лидерах рынка таким даже техлиды грешат, при чем не доганяют почему после перехода на хешсеты страничка стала грузиться пару мс против пары минут.
Вообще реально надо просто понимать свойства алгоритмов и уметь выбрать нужный в конкретной ситуации, писать их с головы на бумажку — это уже задача олимпиадников а не «промышленных» программистов. Ну или для студентов в очередном припадке учебного маразма :)
надо быть достаточно твердолобым чтобы писать свои поделки, когда любой алгоритм гуглится за секунды, к тому же выглядит и работает лучше
Так ув. Alexander Vostres об этом сказал.
Проблема фанатов ненужности алгоритмов в дом, что они не знают, что гуглить. Пациент, которого я приводил в примере выше вроде бы в Гугле не забанен был, когда писал свой гениальный код.
та не обязательно же точное название гуглить, достаточно «как выбрать коллекцию», «как найти пересечение списков», «как организовать быстрый поиск в коллекции» и т.д., в первой ссылке узнает название алгоритма, дальше уже просто
Лично я на собеседованиях про алгоритмы не спрашиваю. Но если кто-то кто не джун сделает слияние списков через что-то в стиле list.contains()/list.indexOf()Т.е. Вы предпочитаете выявлять отсутсвие элементарных знаний в алгоритмах и структурах данных не на собеседовании, а в процессе работы?
К сожалению время не резиновое ни у меня, ни у кандидатов. Соответственно, тратить его на писанину чего-то непонятного на листочке универ-стайл и потом спорить заработает оно или нет смысла не вижу. Тем более что адекватно оценить реально хороший ответ на глубокий вопрос — тоже та еще задача, может быть такое что кандидат лучше меня в теме сечет и будет неловко. Ну и не забываем о том что нам такой эксперт не нужен потому что алгоритмы в реальной работе применяются в основном с гугла. Или на крайняк — реализуется то, что описано в найденной научной статье.
Вопросы задаются такие которые позволяют оценить общую адекватность кандидата, думает ли он «а как оно работает» и копает ли он вглубь. Если чуваку интересно — то даже если он чего-то не знает то точно сможет разобраться.
Для реально крутых кандидатов у меня есть вопросы в загашнике — например о том, как оптимизировать простейший классический алгоритм под реальную архитектуру процессора, но не поверишь — не спросил еще ни разу, хорошо если про коллекции расскажут.
Лично я на собеседованиях про алгоритмы не спрашиваю.Не совсем понял, Вы не спрашиваете глубоких вопросов по алгоритмам, или вообще никаких вопросов по алгоритмам, вроде «как слить 2 списка». Если второе, то очевидно потом придется доучивать людей на ходу, а если не получится (такое тоже бывает), то увольнять.
Имхо, наблюдать как пишеться код на листочке преследует другую цель — посмотреть, как человек думает. Чисто проверить культуру программирования, если есть сомнения. Тут больше подойдут простые неалгоритмические задачи.
Изобразить что-то алгоритмически нетривиальное на листочке вряд ли возможно — утонешь в деталях. Тут можно просто поговорить на вербальном уровне, при условии, что такой скилл реально нужен.
Блдь, что происходит ©
Во-первых,
в стиле list.contains()/list.indexOf() то смотреть я на него буду как на дол6оеба.
list.contains()/list.indexOf() будет работать эффективней на списках небольшого размера, с элементами в несколько (десятков/сотен) штук. И занимать меньше памяти. Твоей кейворд NESTED LOOPS
Во-вторых
почему после перехода на хешсеты
Хешсеты есть смысл юзать, когда списки неотсортированы и по ним прийдется строить HASH JOIN. Что дорого и накладно. Часто это неоптимальный путь. Если списки большие то их лучше предварительно отсортировать и использовать MERGE JOIN слияние.
Тут тоже, что и относительно паттернов. Понимание как работает тот или иной алгоритм — расширяет Ваш кругозор как программиста. Мало вероятно что Вы когда нибудь на «живом» проекте будете писать свою сортировку, но пока Вы разбираетесь, как работает этот алгоритм, Вы выстраиваете своё мышление. Если резюмировать мною сказанное, то:
1. Это выстраивает мышление начинающего программиста, показывает ему как писать компактные эффективные решения
2. Будучи опытным программистом, Вы сможете выбрать оптимальный алгоритм, соответствующий контексту задачи. Т.к. для одного и того же решение, может быть несколько алгоритмов эффективных в разной степени при решении типовой задачи, но отличающейся деталями. Например один потребляет больше памяти, но делает меньше итераций, второй наоборот и т.д. Ну и Вы уже смотрите, что для Вас критично в Вашем конкретном случае. Т.е. понимаение «а что там под капотом» ещё никому не мешало, наоборот помогает действовать не по инструкции,а с пониманием принципов и механизмов...
Мне кажется, реальное соотношение в данном случае ближе к 95% и 5%.
Точнее 4% (20% из тех 20%, которые используют паттерны)
<хейтерский оффтоп>
Вот лично меня удивляет когда джуниоры спрашивают блин, а стоит ли учить что-то (Си или Алгоритмы, не важно). Да блин, это же само по себе интересно! Ну посмотри и поковыряй их, напиши пару программулек с их использованием. Это же кайф.
Лично я например шаблоны проектирования изучал и рефакторинг не потому что это спрашивают на собеседованиях а потому что это блин круто!
Перед собеседованиями я только повторял или подтягивал совсем открытые пробелы. Причём очень просто: искал список вопросов на собеседование и проходился по ним.
А вот это вот их вечное «блин какой язык программирования учить, бла бла бла» для меня вообще что-то странное. Как они так могут, не понимаю.
Вот лично меня удивляет когда джуниоры спрашивают блин, а стоит ли учить что-то (Си или Алгоритмы, не важно). Да блин, это же само по себе интересно! Ну посмотри и поковыряй их, напиши пару программулек с их использованием. Это же кайф.Поясняю популярно: есть такая штука — пирамида Маслоу. В частности утверждается, что когда человеку хочется кушать, о всяких интересных вещах как то не думается, деньги надо. Так что джуниору в начале нужно устроиться на работу, а потом уже тратить время на всякие интеллектуальные изыски. Так что в данном случае вопрос вполне актуальный — человек не знает, что нужно для устройство на работу.
Если человеку неинтересно программировать, ему вообще не надо устраиваться на такую работу.
Ну, я думаю врядли кассирам в Макдональдсе интересно кричать «Вiльна каса!», но на работу туда люди устраиваются.
а карьерный рост до мыть картоху?)
Ну почему, можно и менеджером стать )
Да и вообще как оказывается, работа в маке многому учит(утверждают ИТ специалисты!).
ain.ua/2016/01/30/629347
А если человеку кушать хочется каждый день и его задача кормить семью?
Какая взаимосвязь между едой и программированием, простите. Человеку хочется кушать и какая-то неведомая сила заставляет его решать эту, весьма банальную, проблему таким экзотическим способом — заняться непонятным неинтересным делом?
тут вопрос -насколько неинтересно? , скучные моменты есть в любой работе, даже у кассиров Макдональдса) Не говоря уже о программистах.
Какая взаимосвязь между едой и программированиемНе поверите, но самая что ни есть прямая.
заняться непонятным неинтересным делом?Работа должна приносить либо удовольствие либо деньги(если сразу оба варианта — то это джекпот).
непонятным неинтересным делом
Нет, не позволяет. Программирование позволяет зарабатывать деньги программисту. Человеку, которому просто хочется денег, программирование само по себе не поможет. Надо еще что-нибудь уметь.
Так про любую профессию сказать можно, без умения и канализацию не прочистишь.
Но далеко не все сантехники влюблены в свою работу -а профессия безумно важная). Особенно в частном секторе и старых домах. Но платят хорошо -люди и работают себе потихоньку.
Я тоже считаю, что если программер не освоил алгоритмы, ему лучше в сантехники.
А если программист освоил алгоритмы, но до этого был сантехником -насколько сильно вы будете его презирать?)
Презрение вы вообразили. Разговор о том, что есть разные способы решения задачи «кушать хочется», люди справляются ее решать около 50 тыс лет уже.
есть разные способы решения задачи «кушать хочется»И «нечего лезть своим свиным рылом в наш калашный ряд»?
Такой прям бесценный ряд, офигеть. Чо нынешние программеры себя такой илитой считают. Просто у человека должны быть навыки и интерес. Не надо поваром в стейкхаусе работать вегетарианцу. Не надо работать программером тому, кому не интересно возиться-оптимизировать код. Кому интересно — тот сам все выучит, как сверху и заметили, а вы тут разводите балаган ни о чем.
Чо нынешние программеры себя такой илитой считают.не поверите:)
В сантехники нет, там понимать нужно)
Ну да, в сантехники х***к, х***к и в продакшн не получится сделать )
Как это не получится, когда постоянно делают?
Поясняю :программисты хорошо зарабатывают и им легко найти работу.
90% населения -вообще неинтересно работать, и если бы была возможность -лежали бы в гамаке на берегу Тихого океана под пальмой и потягивали бы смузи. Или пили бы пиво и играли бы в игры..
Таким, по-моему, надо учить всё. Паттернов там всего типа штук 30. Структур данных типа 7. Сортировок штук 7. Алгоритмов штук 10 общих. Вот это — взять, понять и зазубрить всё, сколько там той теории!
Идущий в айти ради денег должен быть готов много работать. В любом случае — не быстро будет, ибо конкуренция-с. Потому настроиться надо не на профит, а на долгую упорную учёбу — тогда будет профит. А человек, который реально в теории не 0 — уже будет выделяться. Есть таки от теории толк, хоть бы и ради собеседований.
сколько там той теории!Фактически надо выучить одну книгу, правда на 1200 страниц.
Воды многовато там, подробностей и не базовых алгоритмов. Но, кстати, за выходные осилил) Не с 0 знаний, конечно. Есть только пара хаков, как её читать:
На практике не важны подробности доказательств. Хватит ухватить общую идею. Что-то можно даже без доказательства, по крайней мере для начала, потом можно всегда вернуться.
Самые сложные также и самые малоиспользуемые. Например B-tree пропускайте при первом прочтении, это про кишки баз данных и файловых систем, не базовые штуки. БПФ — пропускайте.
Да, там нету шаблонов проектирования)
мне эта понравилась, для «обывателей» без математики и без воды www.amazon.com/...
Ну вы структурами данных и алгоритмами недооценили:
1) Связный список 2) Двусвязный список
3)Куча 4) Фибоначчева куча 5) Дерево отрезков 6) Дерево Поиска 7) Дерево Фенвека 8) Система не пересекающихся множеств 9) Декартово дерево 10) Splay деревья 11) Динамически расширяемый массив 12) Красно-Черное Дерево 13) Хеш -таблица 14)Персестентные структуры данных 15) Кольцевой буфер 16) AVL-деревья, B-tree... это только чуть
Да понятно, что всё — это весь computer science и его не выучить. Но вот хорошая такая база, которую даже не всякий синьор знает — учится весьма неспешно за пару месяцев. Имея её — видно, что многие перечисленные пункты крайне схожи и добавить их — не составит труда.
патернов около сотни, если не брать какие-то со сверхъизыском, структур тоже не 7 штук, в общем все заучить не выйдет, особенно учитывая то, что всеми пользоваться постоянно не выйдет, нужно перебирать
сотни ? вижу тема проявляет белый пятна в знаниях многих местных сеньйоров
не сотни, а около сотни, а ты только гоф читал и думаешь кроме них ничего нет?
Не, ну так-то любое более-менее абстрактное решение / алгоритм можно обозвать паттерном. Так что да, будут вам и сотни, и мб даже тысячи.
Блин, да. Я когда учился — был интересен сам процесс создания программы, даже если это было банальное вычисление чего-то по формуле. Язык вообще не волновал, Turbo Pascal устраивал.
Да блин, это же само по себе интересно!для того, шоб быть хорошим разработчиком — не обязательно этим гореть
Вот лично меня удивляет когда джуниоры спрашивают блин, а стоит ли учить что-то (Си или Алгоритмы, не важно). Да блин, это же само по себе интересно! Ну посмотри и поковыряй их, напиши пару программулек с их использованием. Это же кайф.Во-первых, далеко не всё — кайф.
Не знаю. Для меня само программирование, читай кодинг, самая унылая часть роботы, ибо задачу уже решил, а теперь сиди пиши тесты, потом пиши код, скукотища страшная...
1) Для замовника/клієнта/того , хто оплачує роботу важлива вчасно та якісно зроблені задачі.
2) Для інтервьюера — важливо зрозуміти чи ви зможете справитись із пунктом 1(це в ідеалі).
Як показує практика , здав екзамен , не значить, що знаєш предмет. Тому вивчайте предмет, а зі здачею екзамену розберетесь.
Як на мене в таких питаннях можна провести маленьку аналогію з медициною: не знаєте шаблони проектування і алгоритми — Ви фельшер або медсестра, якщо знаєте — Ви лікар
Супер! Думаю, после такой аналогии дискуссию реально можно заканчивать: кто понял — тот понял. Кто не захотел — ну, фельдшер, пусть даже опытный. Хотя и получает ПОКА достойную зарплату.
Сможет, этому учат всех врачей.
Насколько важно знать алгоритмы?...стоит ли на это тратить свои силыЯ на постой вспоминаю своего сокурсника, на
как часто вам они нужны в работеНу вот STL-ные контейнеры например, сплошь и рядом используем, а иногда стоит подумать: list vs vector, map vs сортированный vector, и пр.
Є вакансії де важливо в першу чергу знання і розуміння алгоритмів, це зазвичай що стосується всякіх Machine learning, Computer vision і розробка-вдосконалення алгоримів робити до тих же 3D принтерів, сканерів. А є для манки-кодерів де треба вміти вбивати код і користуватись stack overflow i google. Геймдеві часто намахані СТО вимагають від підлеглих знання алгоритмів, але як правило незавжди потрібно їх розуміння, бо вся необхідна інформація зазвичай лежить в інтернеті, хібащо аналітично геометрія іноді буває вийнятком.
если у тебя не наукоемкая отрасль, то достаточно знать O-метрики и разницу между базовыми алгоритмами сортировки и поиска, чтобы правильно выбрать алгоритм или тип контейнера для задачи
в некоторых отраслях требования к знанию алгоритмов повышенные. например если ты разрабатываешь систему навигации или поисковый движок
Наверное имелась навигация «в малом», aka поиск пути.
en.wikipedia.org/...
Геодезия обычно не нужна, а вот алгоритмы — да, и они там бывают посложнее O(n²).
Шаблоны то такое. И алгоритмы то тоже такое. А вот то что человек не умеет пользоваться поиском это фуфуфу.
Ну тут надо быть очень удачливым, чтобы из «туда, не знаю куда, то , не знаю что» нагуглить верное решение
Сами алгоритмы в чистом виде достаточно редко используются на практике.
Изучение алгоритмов развивает алгоритмическое мышление как таковое. Что в свою очередь несомненно помогает эффективнее решать практические задачи.
А если вам тут скажут, что алгоритмы не нужны, или не сильно, то вы как, примете судьбоносное для себя решение забить на них? Станете безграмотным кодером только потому, что на форуме вам так подсказали?
Судя по себе, предположу что вопрос стоит в приоритетности учебы. А не в целом учить\не_учить.
Учитывая бурность развития индустрии с их 1000 и 1 фреймворками, языками и методологиями, которые также важны для трудоустройства, реально стоит вопрос: потратить время на обучение алгоритмов, или необходимых фреймворков и т.д.?
Основи Computer Science вже не міняються десятиліттями.
А фреймворки випускають нові версії щороку.
все ходовые алгоритмы уже давно реализованы в готовых библиотеках или вообще встроены в язык. Реализация сортировки пузырьком последний раз мне нужна была лет 15 назад.
Вместо задавать глупые вопросы займитесь лучше практическим программированием и все подобные вопросы отпадут.
Вы напоминаете дядьку из села который приехал в город покупать компьютер и спрашиват сколько в компьютере надо памяти.
бывает же и наоборот — нужно знать хотя бы о существовании алгоритма, чтоб обнаружить его реализацию в стандартной библиотеке. Я так когда-то путем проб и ошибок фактически реализовал поиск расстояния Левинштейна, и только спустя несколько лет узнал, что недельную работу можно было заменить вызовом одной функции.
для этого и нужно заниматься практическим програмированием чтобы знать что существует а что нет. Плюс доки и гугл.
А не спрашивать что нужно знать — при нынешних темпах развитии ИТ и нарастающего количества инфы вообще нет смысла задавать вопрос — что мне завтра понадобится знать.
Думаю тебе не нада тут никого слушать, из вопросов получается «паттерны — не нужны, ну может один», алгоритмы — «не нужны, ну может один», а потом окажется что тут сидят формошлемы и верстальщики. Берешь какой нибудь большой проект и там сразу понеслось и фасады, и декораторы и синглтоны, и очереди и т.д. , ты конечно можешь и не знать всего этого и допиливать проект, но времени уходит раз в 5 больше что бы понять как оно вместе работатает и почему в лог пишутся какието строки если никто нигде их туда не пишет а у обжектов появляются какие то свойства которые нигде не описаннны.
На практике все это декораторы и прочее существуют только в описании архитектуры. Когда доходит до реального программирования — туда мало что попадает в первозданном виде. Помнится до моды на паттерны была мода на так называемый RUP, когда норовили рисовать архитектуру проектов в UML. Заканчивалось тем что писали проект как обычно, затем брали Rational Rose реверс инжинирингом генерили UML и втыкали картинки в ТЗ,
А вообще большие проекты с кучей патернов, интерфейсов абстрактных классов, фабрик, стратегий и прочих абстракций я видел только в реализации индусскими программистами. Но такое слабонервным лучше не смотреть.
ну недавно только смотрел какойто сетевой софт, логи все пишутся через декораторы. фактори тоже учавствовала для создания конфигурации, так что реально все пользуется.
А вообще большие проекты без патернов, интерфейсов абстрактных классов, фабрик, стратегий и прочих абстракций я видел только в реализации индусскими программистами. Но такое слабонервным лучше не смотреть.
Почитайте этот топик, много интересных рассуждений на эту тему dou.ua/forums/topic/17317
Для обычного программирования алгоритмы можно и не знать. Но нужно понимать принципы их построения и оценки
А для этого нужно изучать не сами алгоритмы, а ход рассуждений. Примерно как в школьной физике — можно зубрить формулы, а можно знать базовые И принципы вывода остальных формул. Умение рассуждать, понимание — гораздо ценнее на практике, чем знание готовых алгоритмов.
Как уже сказали, рафинированные алгоритмы есть в библиотеках.
А на практике придется иметь дело не с идеальными случаями, а специфическими. Для которых и нужно будет придумать алгоритм.
Например классика — выборка данных из БД, запросами в цикле. Реорганизация такой выборки в bulk потребует анализа специфики данных, и — создания нередко не очевидного алгоритма, на основе нескольких канонических.
Такому навыку можно научиться на примерах анализа и создания алгоритмов
к примеру в языке swift нет реализации очереди (и многих других структур данных), если не знать структур данных, будешь городить хрючево из массива. Если понадобится In-place sort или stable — хорошо было бы знать какие алгоритмы соответсвтуют таким требованиям. Priority Queues, graphs — навскидку задач хватает. Красно-черные деревья реализовывать самостоятельно вряд ли придется, просто стоит знать как это работает. Работа со строками имхо тоже мастхев, особенно в обработке данных, чтобы не видеть потом неработающие регекспы или вложенные циклы с O(n^2). Да и не так уж много времени на изучение этого всего счастья уходит. Средний программист в танки или доту за пару месяцев бегает больше.
если не знать структур данных, будешь городить хрючево из массиваШо, совсем низя очередь из массива? Даже если очень-очень хочется?
Да сколько угодно) особенно если хочется конечно
Можно и очередь из массива, но разве это жизнь?
Если уж совсем абстрагироваться, то всю доступную память можно представить как один большой массив, а вся computer science состоит из манипуляций над этим массивом, так что кто бы что не придумал, это будет манипуляция над массивом.
а вся computer science состоит из манипуляций над этим массивом
Для (почти) любого языка выше C эта абстракция не будет работать.
Что значит «не будет работать»? Если программа на языке выше С, то она в стране единорогов исполняться будет?
Любая структура данных это просто надстройка, которая определяет порядок и форму доступа к нижележащему массиву байт.
Если программа на языке выше С, то она в стране единорогов исполняться будет?
С точки зрения логики уровня ассемблера — да, именно так.
Любая структура данных это просто надстройка, которая определяет порядок и форму доступа к нижележащему массиву байт.
Грубо неверно. Там байтов вообще может не быть.
Грубо неверно. Там байтов вообще может не быть.Тут да, согласен. Зависит от того умеет ли ваша машина адресовать байты (8 бит) или нет.
Не от этого. А от того, что если вы работаете с чем-то вроде Perl/Python/etc., и без средств доступа нижнего уровня, как ctypes, вопрос массива байтов, трайтов или вообще неведомой семеричной хрени это всего лишь вопрос качества эмуляции необходимых возможностей.
Аналогично для компилируемых типа Ada — даже если вы сказали «type byte is new mod 2**8», неважно, как именно оно берёт остаток от деления на 256, и всё равно это не даст никакого указателя на байт, в лучшем случае ссылку на объект.
А раз нельзя адресовать память побайтно даже через хаки — то этой памяти для программы фактически нет.
Тогда почему одни алгоритмы работают быстрее чем другие?
Пузырёк и квиксорт могут гоняться на том же массиве байтов, а скорость разная
Какие байты? Нету никаких байтов. Это фантастика.
Пусть коллекция неведомых объектов, какая разница.
Не уверен, что понял вопрос насчёт почему
Люди толстые книги пишут про алгоритмы, периодически что-то новое изобретают, а вы не можете рассказать почему алгоритм А отличается по скорости от алгоритма Б.
Смотрите, мой изначальные тезис что все и везде это байты. Когда вы тыцаете кнопочку на экране, то кучка байтов из одного места, копируется в другое. Когда вы отправляете что-то по сети, то массив байтов из процесса пользователя, копируется куда-то в сетевой стэк. Я так понимаю что этот тезис вы не оспариваете. Соответственно мой вопрос был адресован Валентину, который утверждает что байт не существует и что всё абстракция.
В О-нотации, которую считают математики в количестве операций, никаких байтов и тактов нет.
Они в ней и сложность по дополнительной памяти считают
Да. Но фигурируют абстрактные элементы, а не байты (которые можно перевести в байты в зависимости от типа но не суть)
Я утверждаю одновременно две вещи: 1) что так представлять просто неадекватно, даже если работаете на уровне ассемблера/C, из-за массы отрицательных эффектов, 2) на языках более высокого уровня такая абстракция памяти вам может быть просто недоступна.
Потому что лучше соответствуют слою реализации. Например, для функциональных языков обычные структуры и методы часто не подходят из-за проблем с изменяемостью элементов массива (сейчас про это уже есть книги типа «Полностью функциональных структур данных» Окасаки).
Но вообще-то Ваш начальный комментарий был «память — всё равно массив байтов» на замечание про реализацию очереди, а это уже не в тему потому, что так рассматривать просто неэффективно. Можно считать, что у любой программы есть под рукой массив из 2**64 байт, но что вы будете делать с этим методом, если у машины всего 8GB RAM?
так рассматривать просто неэффективноно можно
absolute code?
но можно
«Делать можно что угодно, если вас не интересует результат» []
а как пишут загрузчики программ в MBR и прочее -есть же в этом потребность?
Я ещё не видел «загрузчика программ в MBR», который бы предполагал, что у нас 2**64 доступных байт.
Если это действительно загрузчик в MBR для стандартной x86/Wintel-like платформы, он обязан предполагать наличие только первых 512KB (даже не 640!), из которых первые 2KB ему недоступны, ибо заняты чем-то системным. И я ни разу не видел, чтобы такому загрузчику требовалось реализовывать очередь:) В 99.99% случаев их функциональность — уточнить, откуда читать следующую часть цепочки bootloader’ов, и выполнить это чтение, а затем передать управление. И только после того, как (в типичном случае) очередная часть дошла до включения
Можно и очередь из массива, но разве это жизнь?
не знаю чи це був сарказм, тому побуду кепом — у багатьох бібліотеках вона так і реалізована (особливо в managed мовах, де треба поменше робити дебільних memory allocations). ще, це дозволяє швидко ітеруватись (cache friendly), але це не так важливо (напевно)
не знаю чи це був сарказм, тому побуду кепом — у багатьох бібліотеках вона так і реалізована
У багатьох нормальних (а не через одне місце) реалізаціях вона зроблена, наприклад, у два масива — коли перший спорожнюється, другий заповнюється, а потім міняються місцями; можна й більше, наприклад, список (так, список) з масивів фіксованого розміру, або зростаючого з ростом повної довжини черги. Це буде ефективно, а один масив буде тупим жахіттям.
один масив буде тупим жахіттям.
можеш це якось трохи аргументувати, бо мені не дуже очевидно. чому черга на одному масиві (зі, скажімо, експоненціальним ресайзом чи іншим фіксованим ресайз фактором) — це жахіття? чим саме погано і в яких _частих юзкейсах_ це проявляється?
чому черга на одному масиві (зі, скажімо, експоненціальним ресайзом чи іншим фіксованим ресайз фактором) — це жахіття?
Тому, що дані буде треба регулярно зсувати, а це безглуздо дорого. У випадку декількох масивів — старий звільнив, або почав заповнювати по новій.
Тому, що дані буде треба регулярно зсувати, а це безглуздо дорого.
що саме і коли треба «зсувати»? переважно роблять щось типу:
* виділити масив фіксованої довжини
* тримати індекс на head, tail, тримати поточний size
* при вставці просто вставляти в преалокейтнуте місце в масиві і зробити ++/— head, tail, size
* при досягненні розміру масиву, збільшити його в два рази і скопіювати (це на практиці стається дуже рідко, особливо якщо ресайзити експоненціально)
* ще можна трімати розмір, якщо фактична кількість елементів сильно менша
а якщо розмір ± відомий, то взагалі circular buffer, нічого швидшого і бути не може
чим саме краще будуть два масиви?
при досягненні розміру масиву, збільшити його в два рази і скопіювати (це на практиці стається дуже рідко, особливо якщо ресайзити експоненціально)
1. Не рідко.
2. Все одно за вашим підходом копіювати, і чим далі, тим більші обʼєми. Навіщо, коли можна не копіювати марно?
А якщо черга постійно рухається, звичайно коротка, але є сплески великої довжини (на попередньому проекті в мене це була типова картина) — ваш метод приведе до великого масиву, який потім не скоротиться, а в мене сливе одразу половина звільниться, а скоро і зовсім скоротиться до розумно малої довжини.
а якщо розмір ± відомий,
А якщо не цінити памʼять, то можна і фіксований розмір.
1. Не рідко.
десь бачив в інтернеті статистику по середніх розмірах масивів і тд, які використовуються в типових програмах, то для того, щоб її досягнути експоненціальним ресайзом починаючи з 4 елементів треба дуже мало ресайзів (і всі вони на коротких масивах, тому дуже швидкі). зараз знайти лінку не можу. а ще команда .net framework робила схожий аналіз, тому в фреймворку черга, список і багато чого якраз на динамічному масиві і реалізована з експ ресайзом і стартом з 4 елементів, по тому алгоритму, який я описав і де ніяких «зсувів» ніхто не робить, і це перевірено на практиці і підкріплено внутрішньою статистикою
Все одно за вашим підходом копіювати, і чим далі, тим більші обʼєми. Навіщо, коли можна не копіювати марно?
ну а з підходом «два масиви» нічого копіювати не треба? чим саме такий підхід принципово відрізняється? що ти будеш робити, якщо пам’ять закінчиться? я так і не почув опису такого алгоритму і його явних переваг, чи це ти маєш на увазі, щоб зекономити на копії ти прохардкодиш кейс коли можна виділити +1 масив. а якщо і він закінчиться?
я ще розумію список масивів, бо тоді не треба буде дані копіювати, а тіки алокейтити нові масиви якогось фіксованого розміру, але це дуже неочевидно, що копіювати дані буде сильно дорого в порівнянні з цими алокейтами, а от перфоманс ітерації по всьому цьому впаде, бо воно в пам’яті вже не послідовно.
А якщо черга постійно рухається, звичайно коротка, але є сплески великої довжини (на попередньому проекті в мене це була типова картина) — ваш метод приведе до великого масиву, який потім не скоротиться, а в мене сливе одразу половина звільниться, а скоро і зовсім скоротиться до розумно малої довжини.
з чого ти взяв, що не скоротиться? я ж писав
* ще можна трімати розмір, якщо фактична кількість елементів сильно менша
а в мене сливе одразу половина звільниться, а скоро і зовсім скоротиться до розумно малої довжини.
ще раз, в чому принципова різниця, крім того, що коду при 2х масивах більше? пам’ять в тебе теж закінчиться і теж треба буде ресайзати, а якщо ти припускаєш, що не треба буде, то це тільки частково прооптимізований кейс, який порівнювати з загальною реалізацією впринципі не має сенсу. я вже показав, як можна ще далі оптимізувати — виділити відразу скільки треба, якщо знаєш скільки треба
А якщо не цінити памʼять, то можна і фіксований розмір.
при чому тут цінування пам’яті? якщо я знаю, що розмір буде
то для того, щоб її досягнути експоненціальним ресайзом починаючи з 4 елементів треба дуже мало ресайзів
«Експоненціально» це в 1.2, 1.5, 2, 3 або 10 разів? (я бачив багато варіантів)
а ще команда .net framework робила схожий аналіз,
Добре, але їх досвід не збігається з моєю областю (я ж розповідав, що типово черги короткі, але бувають сплески до дуже великих довжин).
ну а з підходом «два масиви» нічого копіювати не треба?
Я агітую за список масивів. При ньому — ні, не треба. Якщо вже зайняті, наприклад, на 1000 і 2000, наступний буде створений на 3000 (взагалі, використовується якась політика типу «поточна довжина черги плюс 10»). У випадку двох масивів зайве копіювання є, але його вже значно менше і потрібно воно тільки при різкому росту довжини.
я ще розумію список масивів
Про це я сказав з самого початку, і далі тільки про цей варіант, і не треба говорити всі ці «я ще розумію», як будто це відкриття по ходу.
але це дуже неочевидно, що копіювати дані буде сильно дорого в порівнянні з цими алокейтами
Так, буде сильно дорого. Алокації і звільнення памʼяті в сучасних менеджерах дуже дешеві.
а от перфоманс ітерації по всьому цьому впаде, бо воно в пам’яті вже не послідовно.
Якщо один масив хоча б в
ще можна трімати розмір, якщо фактична кількість елементів сильно менша
І що? Ну знаєш той розмір, від цього памʼять сама звільниться?
виділити відразу скільки треба, якщо знаєш скільки треба
Не знаю і знати не можу. Або знаю щось на зразок «усталена довжина — 20, у піку до 2 мільонів». Тобто, з різницею в декілька порядків.
«Експоненціально» це в 1.2, 1.5, 2, 3 або 10 разів? (я бачив багато варіантів)
2 по дефолту
Добре, але їх досвід не збігається з моєю областю (я ж розповідав, що типово черги короткі, але бувають сплески до дуже великих довжин).
не, ну почекай, мова ішла про _загальну реалізацію_ черги, ± оптимальну для середніх кейсів, яку в бібліотеках пишуть
Про це я сказав з самого початку, і далі тільки про цей варіант,
ну спочатку і казав, але далі все було про 2 масиви, от я на них і відповідав
Не знаю і знати не можу. Або знаю щось на зразок «усталена довжина — 20, у піку до 2 мільонів». Тобто, з різницею в декілька порядків.
ну круто, так би і поставив початкову задачу, тоді б говорили про те, як саме цю задачу оптимальніше вирішити, я не пригадую, щоб сперечався, що в таких умовах ресайзити 1 масив буде краще, не буде. але ми почали з
У багатьох нормальних (а не через одне місце) реалізаціях вона зроблена, наприклад, у два масива — коли перший спорожнюється, другий заповнюється, а потім міняються місцями; можна й більше, наприклад, список (так, список) з масивів фіксованого розміру, або зростаючого з ростом повної довжини черги. Це буде ефективно, а *один масив буде тупим жахіттям.*
і з цього я зробив висновок, що ми про загальну бібліотечну реалізацію говоримо, а не про специфічні кейси. ну я надіюсь ти погодився, що робити чергу на 1 масиві — це ніяке не «тупе жахіття», а цілком нормальна реалізація для середніх кейсів, яку в не одному фреймворку запилили, включно з .net
2 по дефолту
OK. Звичайно так і робиться (останніх років 15).
не, ну почекай, мова ішла про _загальну реалізацію_ черги, ± оптимальну для середніх кейсів, яку в бібліотеках пишуть
Що таке «середні» кейси? Хто їх виміряв як «середні»? Ви згадуєте кілька разів дотнет. Вірю, але мої задачі по більшості критично відрізняються від тих, що вирішують на дотнеті.
І навіть у цьому випадку бібліотечна реалізація повинна не допускати критичної втрати ефективності у нетиповому випадку.
і з цього я зробив висновок, що ми про загальну бібліотечну реалізацію говоримо, а не про специфічні кейси.
Саме так! Про загальну. Яка повинна працювати в дуже широких умовах.
Ціна створення списку масивів середнього або великого розміру — менш ніж копійки, а от вигода для складних випадків — колоссальна.
яку в не одному фреймворку запилили, включно з .net
Для мене дотнет скоро стане еталоном розвʼязку через зад та реалізацій, зроблених на «відчепись». Ось як, наприклад, в SortedDictionary можна було не зробити аналог {floor, ceiling, lower, higher}Entry()? Він такий не потрібен, від слова «зовсім». Або BigInteger, який не має BitLength(). У вас є приклад з середовища, яке зроблене не повними носорогами?
за 10 лет в java, знание алгоритмов пригодилось только на собеседованиях
в конце концов, есть Arrays.sort() или String.indexOf(), зачем мне знать как они реализованы?
Например затем, чтобы знать, например, они O(n), O(n log n) или O(n^3). Или затем, чтобы знать, что sort (или сводимая к нему задача) за O(n^2) — это ненормально, и надо поискать другой. Или чтобы знать, что такое amortised linear time и что случается, если звать такую функцию в цикле, например. Чтобы знать, куда смотреть (а какие места — пропускать), когда «что-то тормозит».
Погоди, bigO это другая тема. Я могу посчитать его для своего алгоритма.
Я знаю, что быстрая сортировка имеет nLogn, но зачем мне умение написать этот алгоритм на бумажке?
Возможно это и бесполезное знание. Но каждый раз, когда я вижу на собеседовании человека, у которого нет никакой интуиции о том, какое O() у вставки в Dictionary в питоне или поиске по нему, или о том, что может стоить слияние двух map-ов в Java, я думаю о том, что знание деталей реализации (структур данных и алгоритмов на них) тут бы здорово помогло ...
о-нотация чуть менее чем полностью бесполезна, если что-то тормозит я никогда не стану оценивать сложность алгоритмов по всему приложению, просто открою профайлер и он покажет проблемные места, которые надо оптимизировать, сразу писать оптимизированное можно только если других людей на проекте нет, потому что после рефакторинга, тех кто не париться за производительность и прочих людей оптимизированного кода все равно не будет => никакой пользы кроме как для упоротого собеседования
Полезность такого подхода резко уменьшается, когда тормозящий код пишешь ты, а тормозит он у кого-то другого (или наоборот). Например, ты пишешь библиотеку, а кто-то ее использует (или наоборот). Да, профайлер тебе безусловно покажет, что 90% времени — внутри вот этой функции из вот этой библиотеки. Как отвечать на вопрос — это так и должно быть, или оно глупо устроено, а самое главное — оно в принципе может быть быстрее или нет? Стоит пытаться переписывать, или тут один фиг O(x), и x не у меньшается? Можно, конечно, отфутболить вопрос «на ту сторону» (автору библиотеки, или наоборот — приложения), но там же может быть такой же нелюбитель О(), который скажет «as designed», «я не знаю» или «Я тут юзаю List.find, быстрее не будет», и круг замкнется ....
ну что значит «я не знаю»? если библиотека коммерческая, то ее никто не купит, если опенсорс, то одни могут допедалить, другие вообще не могут использовать, если другие подразделение компании надо протолкнуть доработку
у тебя ситуация оторвана от жизни, когда 2 программера договорились написать программу и один накосячил и не хо исправлять, нафиг так жить? и даже в ней как о нотация поможет, ну будет знать что там много о от н и что дальше?) все равно идти гуглить как перепедалить, а профайлер опять же покажется точное место что нужно поправить
Ну, ладно. Похоже, я один встречался с людьми, которые «правили про профайлеру» ужасные алгоритмы, выжимая капли производительности из inner loop вместо того, чтобы изменить сам алогритм — и все из-за того, что им не хватало знаний классически алгоритмов и структур данных. Спишем на абберации моего опыта.
о-нотация как бы помогла? сама способность посчитать сложность аглоритма не тоже самое что знание алгоритмов
Самурай без меча подобен самураю с мечом. Но без меча.
Да, это не одно и то же. Мой point в том, что тот, кто знает обе вещи будет при прочих равных лучше того, кто знает только одну. И все они будут лучше того, кто не знает ни алгоритмов, ни О().
знаю о и алгоритмы == знаю только алгоритмы > знаю только о == ничего не знаю
Не, Димыч, ты не один. )
Ну и может я уже стар и брюзжу, но по-моему для программиста не интересоваться такими вещами (причем всеми тремя — и алгоритмами, и О() и паттернами) и не копаться в них из собственного интереса даже, а не потому что «на собеседовании спросить могут», это просто позор и повод задуматься о смене профессии.
Угу, вот представь: ты — молодой специалист и не знаешь что учить. Можно копаться в алгоритмах сося лапу, а можно выучить PHP и зарабатывать первые деньги. Что выберешь?
Не знаю, возможно что для «вайтивайти» этот вопрос и актуален, но в большинстве эти вещи проходятся еще эдак курсе на
И учитывая, что в те годы поголовно все «самые талантливые и умные», обсуждение столь животрепещущих материй должно возникать на каждой второй (а то и первой) пьянке на неделе даже неприменительно к реальному коду или заданиям.
Сам таким был и в те годы даже не представлял себе, как можно иначе. )
просто открою профайлер
А теперь представь себе, что тебе надо знать, успеет ли выполниться задача, до того, как ты её запустил.
Хотя бы с погрешностью до полутора раз.
успеет ли выполниться задача, до того, как ты её запустил.думаю не успеет, т.к. она не начнет выполняться только после того как я ее запущу
Ты не будешь контролировать запуск задачи, это будет на другом конце страны и без тебя.
а я не имею права ее запустить посмотреть как работает? или если человек пишет либы, которыми будут пользоваться другие становиться настолько убогим, что сам уже не может ими воспользоваться чтобы проверить как они работают? что ты за такие фантастические ситуации выдумываешь?
а я не имею права ее запустить посмотреть как работает?
Право - имеешь. Возможность - не всегда. Например, имеет ли MS возможность наблюдать за запуском каждой винды? ;)
чтобы проверить как они работают?
Так ты ж не хочешь проверять у себя, как работает, хочешь на живом клиенте.
что ты за такие фантастические ситуации выдумываешь?
Если для тебя это фантастика, то я боюсь себе представить, в какой песочнице ты работаешь и какие детские задачи решаешь.
Право - имеешь. Возможность - не всегда. Например, имеет ли MS возможность наблюдать за запуском каждой винды? ;)в виндовс 10 прикрутили
Так ты ж не хочешь проверять у себя, как работает, хочешь на живом клиенте.у клиента должен быть только один способ использования, тогда все предсказуемо, будет больше - как ни старайся будет какая-то беда и только по фидбекам можно будет пофиксить
Если для тебя это фантастика, то я боюсь себе представить, в какой песочнице ты работаешь и какие детские задачи решаешь.ну я такие ситуации мидлом мог выдумать, теперь не приемлимо когда ситуация выходит из под контроля, поэтому они для меня и фантастические
в виндовс 10 прикрутили
Не-не, там ещё файрволлы по дороге могут быть.
у клиента должен быть только один способ использования, тогда все предсказуемо, будет больше - как ни старайся будет какая-то беда и только по фидбекам можно будет пофиксить
Вспоминаем классику. У тебя, похоже, "внутреннее" на 200%. У меня консультационное на грани коробочного, а часто с элементами встроенного. Вариант "один способ использования" мне, мягко говоря, фантастика.
теперь не приемлимо когда ситуация выходит из под контроля,
От middle/senior/etc. это не зависит.
Вспоминаем классику. У тебя, похоже, "внутреннее" на 200%. У меня консультационное на грани коробочного, а часто с элементами встроенного. Вариант "один способ использования" мне, мягко говоря, фантастика.я писал все 5 пунктов из этого списка, встроенное меньше всего
Вариант "один способ использования" мне, мягко говоря, фантастика.самое простое что в голову пришло библиотека третьей стороны с архиватором, там один путь развития событий, ты просто больше ничего не сможешь ею сделать, поэтому и проверить скорость архивирования можешь прямо у себя, более сложное разбивается на много мелких, они не должны иметь сложных зависимостей между собой и все получится
Например затем, чтобы знать, например, они O(n), O(n log n) или O(n^3)Т.е. вы намекаете что в джаву встроили алгоритм с кубической сложностью?
Т.е. теперь это разговор исключительно про sort? Я-то думал, что sort приведен как пример...
зачем мне знать как они реализованы?Это и называется «микроскопом забивать гвозди». И не знать, что для этой цели есть как минимум плоскогубцы и разводной ключ :8)
И что, использовать Arrays.sort для сортировки это уже называется забивать микроскопом гвозди?
Читайте плиз вышее, и Вам ответили про сложности алгоритмов. Если Вы в курсе, когда вам нужен Arrays.sort, а когда лучше использовать что-то вроде TreeMap и-или TreeSet, если Вы знаете, какой алгоритм там реализован и подходит ли он к Вашим конкретным данным — ответ «ни в коем случае». Если нет — ответ «да» :( ... есть такой антипаттерн, «золотой молоток» :) , но паттерны и антипаттерны тоже ж знать не обязательно :)
Знание алгоритмов программисту нужно в двух случаях:
1) Он собеседуется в гугл, амазон, макрософт и тому подобное пафосные место с большим количеством желающих
2) Он будет работать разработчиком этих самых алгоритмов: картография, трейдинг, машинное обучение, разработка движка игр. В этом случае важно знать совершенно конкретные вещи. БОлее того людей на рынке с такими знаниями мало, поэтому иногда если общий уровень хорош, человека готовы обучать.
В остальных случаях полезно алгоритмы НЕ знать: это убережёт вас от работы с пафосными задротами, которые прочитали вчера книжку/ решили задачку и думают, что и другие должны читать и знать то же самое. В большинстве случаев такие люди слегка, как бы это помягче сказать, пыльным мешком по голове стукнутые и работа с ними удовольствие на любителя.
Я как то собеседовался в датаарт, так там эйчаром работает замдекана то ли КПИ, то ли Шевченко. Думаете он меня спрашивал по матанализу, или по алгоритмам сортировки(хотя все думаю согласны, что академические вещи этот человек знает)? Нет: разговор о том, какие проекты, что делал, чего хочу.
А почему? Да потому, что на практике для 95% задач достаточно знать какую структуру данных выбрать да где искать нужную информацию в случае необходимого. И тот факт, что я таки могу взять интеграл, или помню алгоритмы сортировки, или могу решить задачку по алгоритмам никак не поможет мне в багфиксе веб проекта. И потому ещё, что всегда можно найти чего человек не знает, даже если он семи пядей во лбу
Для программиста важно специальное мышление не меньше, чем знание конкретного языка. Мышление, как мне кажется, развивается также как и мышцы в спортивных тренировках — годами упорных занятий. Так вот математика, алгоритмы и т.п. — это как раз такая тренировка.
А как же вы выберете нужную структуру данных?
Если часто вставлять — LinkedList, если часто искать ArrayList
Я сразу подумал про «хочешь — пироженное, хочешь — мороженное»
А если часто вставлять и постоянно иметь доступ к n минимальных элементов? В любой момент времени
теперь перечитываем статью о сравнении ArrayList и LinkedList, вспоминаем что сдвиг при remove в ArrayList происходит native методами и бежим выпиливать LinkedList из проекта. операции вставки по индексу в конец списка меняем на добавление, а в местах где используется remove из начала нужно задуматся о другой структуре данных.
Сильно смущает, что операции со связным списком происходят по индексу, а не по ссылке/итератору, или что там в этой вашей жабе.
Но список правда на малых объёмах данных смысла не имеет, т.к. кеш и аллокации.
А теперь вспоминаем, что жаба — не единственный язык программирования.
А теперь вспоминаем, что способов создать ArrayList много, очень много. Читаем классику :)
У Шепелева был клевый ток о джава интерналсах, который напроч рвал шаблон, и в конце утверждалось что LinkedList ненужен от слова совсем, но я немогу его нагуглить.
hr и не будет спрашивать алгоритмы. Алгоритмы спрашивают на технических собеседованиях.
Он проводит в том числе техническое, по крайней мере для руководителей
Каких таких руководителей? Возможно этот hr имеет квалификацию проводить технические собеседования, но в 99% процентах случаев hr просто фильтрует на входе, а по настоящему оценить человека может только технический спец. И да возможно бывает, что и на техническом собеседовании не спрашивают алгоритмы, но в серьезных американских конторах (не боди шопах) как раз налегают на алгоритмы. И там и зп не как в бодишопах, а повыше. И речь не только о всяких гуглах.
Чувак, вот скажи: какого рода вопрос задан, про гугл или первую работу? Да, возможно в американских крутых компаниях алгоритмы и нужны, но мы тут не о них общаемся. Человеку нужна первая работа
Первая работа означает что человек практикант. Практикант обязан понимать базовые алгоритмы. Иначе есть большой риск не пройти практику (на практике в том числе спрашивают и теорию). Ну да не спорю, что можно проскочить и клепать кнопочки на морде. Таким конечно ни к чему алгоритмы)
В большинстве случаев первая работа, это и есть кнопочки на форме
на первой работе, когда показать кроме «у меня тут было две лабы по крестам» нечего — обычно и спрашивают про все эти сортировки пузырьком и прочие нахождения циклов в односвязном списке. Просто чтобы понять что перед тобой — не идиот, протерший в своем вузе три пары штанов и ни на что не годный.
Смотря чем заниматься, в BigData без алгоритмов никуда, в играх тоже, а в вебе вряд ли они пригодятся.
в BigData без алгоритмов никудана самом деле много куда.
Я как раз и имел ввиду «алгоритмы», а не реализованные в куче библиотек алгоритмы сортировки, как и автор.
Я к тому что обычный
В нормльных работах такой «синьор» даже собес не пройдёт. Бигдата — э то не только ETL-чики а-ля яйца почесать. Когда дело заходит о сложных ситуациях (а-ля повысить уровень согласованости в существующей инфраструктуре, или ещё адовей — ускорить сортировку в готовом mpp) — без алгоритмов, причём ещё и распределённых, а ещё желательно и неблокирующих — та фиг там.
В нормльных работах такой «синьор» даже собес не пройдёт.
Это какраз не «нормальные работы», а «редкие работы». В 95% случаях таки
яйца почесать.
Видел вакансии в бигдата консалтинге, там предлагали доучивать кандидатов
Кстати с играми тоже не очевидно, ибо можно взять готовый движок...
самые лучшие игры на своем движке
Мне кажется, важно вот что:
— понимать как расчитывается сложность алгоритмов, чтобы уметь сравнить 2 реализации одной и той же логики и сказать какой вариант оптимальнее (по скорости, по обьему занимаемой памяти);
— знать набор основных алгоритмов чтобы вы не изобретали велосипед когда столкнетесь с тем, что уже давно придумали как делать, до вас
Я задал тут вопрос на форуме про шаблоны проектирования, и получил очень интересные ответы.
Теперь интересно знать про алгоритмы.
Хотите прийти к выводу, что для работы программиста нужен только синтаксис ЯП, но и тот можно в референсе подсмотреть?
А вы знаете С++ и Qt? Все стандарты? Все версии и модули?
В таком контексте вы напрасно называете это технологиями. Вы имеете ввиду _интерфейсы_ к технологиям. На самом деле, и этого знать не надо — в нормальных IDEшках есть автокомплит, он вам подскажет и синтаксис языка, и сигнатуры нужных функций. И вы в свой список забыли добавить главный скилл — «copy/pasting from stackoverflow».
звiдки ви такi взагалi вилазите? алгоритми i структури даних — це перше, що повинен знати девелопер.
але якщо хочеш бути рядовим кодерком на галерцi, то можеш забити.
Більшості людей і цього вистачає. Хіба на доу мало людей з личками сіньйорів в «лідерах ринку» які розповідають що освіта не потрібна?
It was kc tier and it was on DOU
рядовим кодерком на галерцi, то можеш забити.наскільки мені відомо, навіть рядовий кодер отримує у нас до 2к, а то і більше. І не потрібно нічим забивати голову.....
sanchez
Sergey Ponomarev
Alexander Vostres
Dmytro Krasun
anonymous
Olya Kapinos
Punk Floyd
Alex Olnichenko
mobile mobile
Pigeon On
Alexander Semenov
Vasyl Lytovchenko
undefined pointer
Andrew Sevastianov
Dmytro Hnatiuk
Alexandr Gavriluk
Dmytro Hnatiuk
Natalia Riabokon
De Money
Bogdan Rudnytskyi
Игорь Рубан
Anatolii Papenko
ultras
Дмитрий Вежнин
Vadym Baranenko
Дмитро Борисенко
Dmytro Zharii
Eugene But
Roman Gorodishcher
Oksana Chuiko
Denis Reznik
Ihor Lazarenko
Vasilij Tjorkin
Sergey Sheshenya
Mycroft Holmes
Andrey Derkach
Vadim Kopanev
Alexander Vostres
DNA Exp
Rostislav Nikitin
Stanislav Demchenko
Владимир Кожаев
Maksym Sharov
Alex Koshterek
Александр Липских
Gennady Dogaev
Євген Козлов
Yevhen Lozov
Viktor Kondolovskiy
Dmytro Sharadkin
Євген Лесько
Volodymyr Kuksynok
Victor Mikhaylov
Mikhail Boiko
Валерий Макаров
Victoria Globa
Леонид Мартынюк
Eugene Varava
mobile mobile
Bogdan Rudnytskyi
Oksana Chuiko
Полная трехмерная копия Юры Буряка
Dmitry Astapov
Полная трехмерная копия Юры Буряка
Євген Лесько
Владимир Кожаев
Andrey Oleynik
Arthur Belov
Olena Sharovar
Oleksiy Protas
Taras Kolodiy
Найкращі коментарі пропустити