Комментарии 53
Пользуетесь ли вы структурами данных и алгоритмами в повседневной работе? Я обратил внимание на то, что всё больше и больше людей считает алгоритмы чем-то таким, чем, без особой связи с реальностью, технические компании, лишь по собственной прихоти, интересуются на собеседованиях.
Я не только пользуюсь алгоритмами, я их ещё и регулярно пишу. Я вообще себе слабо могу представить как должна выглядеть программа без алгоритмов. Потому что:
Алгори́тм (лат. algorithmi — от арабского имени математика Аль-Хорезми) — конечная совокупность точно заданных правил решения произвольного класса задач или набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи
И структурами данных пользуется и их регулярно пишут сами подавляющее большинство программистов. Потому что те же классы это уже структуры данных…
Ну как вы не понимаете, это другое. Многие презирают именно те продвинутые алгоритмы и структуры данных, которые проходят в Computer Science. А от O() просто шарахаются как от грязных ругательств. И сильно недовольны, что это спрашивают на интервью.
Ну я как бы тоже не особо люблю всякие там тестовые задания и просьбы написать "сортировку пузырьком" во время собеседований.
Но всё таки когда пишешь статьи на хабр, то на мой взгляд надо ну хоть немного разбираться в терминологии и этом самом ИТ...
Ну я как бы тоже не особо люблю всякие там тестовые задания и просьбы написать «сортировку пузырьком» во время собеседований.
В целом статья именно об этом — о том, что в FAANG и других компаниях из Долины очень любят алгоритмические задачи на собеседованиях. И там не спрашивают сортировку пузырьком, там спрашивают более сложные алгоритмы и структуры данных. И автор говорит, что это не очень хорошо.
Но всё таки когда пишешь статьи на хабр
Эта статья — не оригинал, а перевод.
А какие алгоритмы и структуры данных (ну, помимо классов, конечно) вы регулярно пишите?
Эта статья — не оригинал, а перевод.
Значит надо при переводе использовать правильную терминологию. Или может быть стоит задуматься что там пишет автор и стоит ли его вообще переводить.
А какие алгоритмы и структуры данных (ну, помимо классов, конечно) вы регулярно пишите?
А это принципиально важно в данном контексте? Речь о том что у вас по хорошему любой код состоит из алгоритмов и/или структур данных. Поэтому вопрос «Пользуетесь ли вы структурами данных и алгоритмами в повседневной работе?» звучит для меня абсолютно дико.
Значит надо при переводе использовать правильную терминологию.
Я считаю, в переводе надо использовать ту терминологию, которую использует автор оригинала. Ну, либо писать свою собственную статью-обсуждение оригинала.
А это принципиально важно в данном контексте? Речь о том что у вас по хорошему любой код состоит из алгоритмов и/или структур данных.
Мне просто интересно. Я понимаю, что вы пользуетесь классами, массивами, хеш-таблицами и подобными. Но фраза, что вы пишите структуры данных и алгоритмы (мне видится, что вы их сами пишите, а не используете встроенные в язык) вызывает интерес. Я сейчас как раз изучаю алгоритмы/структуры и мне интересно, что именно вы используете, а тем более пишите сами, в повседневной работе.
А алгоритмы тем более. Какие алгоритмы используются постоянно? Я не считаю написание метода в классе написанием алгоритма.
Я понимаю, что вы пользуетесь классами, массивами, хеш-таблицами и подобными.
Классы, структуры, массивы, деревья, листы, стэки, очереди, словари… Мне даже сложно сказать какие структуры данных я не использую.
Я не считаю написание метода в классе написанием алгоритма.
Я выше привёл общепризнанное определение алгоритма. По этому определению написание метода в классе вполне себе может являться написанием алгоритма. Ну или каким определением алгоритма пользуетесь вы?
Но фраза, что вы пишите структуры данных и алгоритмы (мне видится, что вы их сами пишите, а не используете встроенные в язык) вызывает интерес. Я сейчас как раз изучаю алгоритмы/структуры и мне интересно, что именно вы используете, а тем более пишите сами, в повседневной работе.
Для того чтобы ответить на этот вопрос мне сначала надо понять что вы понимаете под словом «алгоритм».
Чем «напрямую» отличается от «опосредовано, через библиотеки» и как одно должно быть возможно без другого
Тем, что во втором случае не надо ничего знать про эти самые алгоритмы-шмагоритмы.
Математика программистам не нужна же. /s
Если это важно, то прежде чем использовать библиотеку я как минимум смотрю что они там делают или хотя бы читаю в доках какая там сложность в тех или иных ситуациях.
А иногда приходится и самому всё это писать.
П.С: Ну и самые для меня «сложные алгоритмы» это пожалуй был расчёт оптимальной загрузки/маршрута для грузовиков. Вот там у меня мозги кипели. Правда писал я не один и среди нас были и математики.
Пользуясь библиотеками, но не вникая в их устройство в рискуете получить неэффективный код, сами того не понимая.
Как пример, в QT был реализован алгоритм SkipList. Но. Один из параметров, существенно влияющий как на производительность, так и на потребление памяти, был тупо установлен в некоторое усредненное значение и при этом скрыт от пользователя. Не понимая алгоритма и не вникая в его конкретную реализацию пользователь получал снижение производительности при увеличении потребления памяти.
И таких примеров я на своем веку встречал предостаточно.
К сожалению, сейчас такой код вполне себе приносит деньги. Т.е. слабали, спихнули заказчику, получили свои деньги и свалили. А через какое-то время заказчик вынужден искать людей, которые все это будут править или переделывать. Например, когда возрастет нагрузка и все это перестанет справляться.
И с таким тоже приходилось сталкиваться, увы.
Пользуясь библиотеками, но не вникая в их устройство в рискуете получить неэффективный код, сами того не понимая.
Абсолютно верно. Но просто очень часто эффективность вашего кода вас интересует только в определённых границах. И до тех пор пока эти границы не нарушаются, оптимизация кода «вручную» это никому не нужная потеря времени и/или денег.
Т.е. слабали, спихнули заказчику, получили свои деньги и свалили. А через какое-то время заказчик вынужден искать людей, которые все это будут править или переделывать. Например, когда возрастет нагрузка и все это перестанет справляться.
И такое бывает. Но с другой стороны если заказчик указал что он собирается использовать вашу систему с определённой нагрузкой, а сам потом вдруг решает увеличить нагрузку на несколько порядков, то это уже он сам и виноват.
Абсолютно верно. Но просто очень часто эффективность вашего кода вас интересует только в определённых границах. И до тех пор пока эти границы не нарушаются, оптимизация кода «вручную» это никому не нужная потеря времени и/или денег.
Я бы согласился, не будь у нас в бэклоге огромного пула задач на оптимизацию.
Вот это реальная потеря времени и денег.
Причем, во многих задачах явно видно что просто человек сделал как попроще, не задумываясь о том, а нет ли решения более эффективного. И выбор его на этапе начальной разработки обошелся бы намного дешевле последующей доработки с неизбежным ретестом.
У нас огромного пула задач на оптимизацию нет. Да и вообще оптимизация, которой мы занимаемся «за свой счёт» а не по заказу клиента, у нас достаточно редкое событие.
Но да, если на код ревью всплывает ну вот совсем плохо оптимизированное решение, то человеку об этом говорят. Или если тесты показывают что-то странное в этом плане, то тоже разбираемся обычно.
Ну и нагрузка порядка 3млрд изменений (только изменений) БД в сутки. И таблиц в БД тысячи.
Всего очень много. И оптимизация занятие вынужденное. Когда в пике нагрузка серверов (кластер из трех серверов по 16 12-ядерных SMT8 процессоров POWER9 в каждом) превышает 90%, мы вынуждены что-то с этим делать. Ибо остановка какой-либо системы это не только репутационные потери, но и в некоторых ситуациях штрафы со многими нулями от регулятора (да, там все регламентировано, в том числе и предельные времена простоя отдельных систем).
Но вот например у нас сейчас был запрос oт клиента добавить ему возможность дампа отдельных регионов памяти и просмотра этих дампов в хексе. Регионы при этом по спецификации не могут быть больше 256МБ. И я конечно могу написать сам с нуля этот самый hex viewer, но есть куча библиотек, которые 256МБ «рендерят» за секунду. И зачем мне тогда тратить на это время и деньги клиента?
Я сейчас как раз изучаю алгоритмы/структуры и мне интересно, что именно вы используете, а тем более пишите сами, в повседневной работе
Что понимать под «пишете сами»? Разработку собственного алгоритма? Разработку собственной реализации описанного где-то алгоритма (или адоптацию его под свою задачу)?
Весть процесс разаработки есть построение некоторого алгоритма для решения поставленной задачи.
Я про нормальные алгоритмы из книжек, где надо оптимизировать какую-нить функцию, применить каких-нить maxheap-ов и фильтров Блума, да хотя бы граф какой-нибудь обойти.
Добавлю от себя. Работая в гугле, приходилось писать динамическое программирование, использовать дек, бинарный поиск. На собеседованиях в качестве алгоритмической задачи задаю упрощенную версию того, что лично писал во время работы.
А для какого рода задач это надо было делать? Особенно динамическое программирование интересно.
HyperLogLog несколько раз применял. Причем не классически, для подсчета количества, а для отбрасывания копий данных. Если не важно что можно потерять часть данных при коллизиях, то вполне себе решение.
Операции над разреженными векторами, чтобы можно было тот же TFIFD считать с малыми затратами оперативы.
В embedded постоянно пользуюсь кольцевыми буферами и скользящим медианным фильтром (самодельными). Пару раз юзал самодельный map, потому что почти все структуры данных из стандартной библиотеки С++ используют кучу.
Но при этом считаю, что знать классические алгоритмы (типа сортировок и поиска в глубину) — это просто интересно.
Сейчас больше списки -обычные, с ключом и сортировкой (несколько типов списков делал сам на основе алгоритма SkipList).
Это где такое и для каких задач?
Предположу, что любая обработка датчиков, от GPS до уровня воды в бочке. Списки могут быть хитрым базами данных (колоночные, in-memory).
Ну и — библиотеки же кто-то пишет…
А ещё, как с криптографией, иногда надо подробно понимать алгоритм внутри, например значение параметров.
Эээ и почему вдруг "категорически не стоит"? В чём по вашему принципиальная проблема библиотек, которая не позволяет их использовать в такой ситуации?
Ну даже если взять ваш пример, то в общем-то совсем не исключено существование библиотеки с "заданными параметрами обработки" или просто с одним конкретным нужным фильтром.
Списки используются в основном для кеширования данных при работе с БД. Тут надо иметь ввиду, что сейчас работаю под AS/400 где скорость бывает очень критична, а вот с памятью особых проблем нет — на тестовом сервере 1.8Тб оперативки, на боевых по 2.5. На каждую задачу система выделяет 16Гб памяти.
Например, делается некая выборка, с которой потом нужно много работать. В этом случае используем обычный двусвязный список.
Бывает что нужно отсортировать выборку по неиндексированному полю. Была такая ситуация. Выборка из 50 000 — 100 000 записей с сортировкой по трем неиндексированным полям. В варианте с ORDER BY… в запросе время полной обработки 60-90 секунд.
Убрал ORDER BY из запроса, сложил результаты в SkipList с ключом в виде комбинации нужных полей, потом обработал список в порядке от первого элемента к последнему. Получил полное время обработки на тех же данных 10-15 секунд.
Есть просто сортированный список (на том же скиплисте, но где сами данные одновременно являются ключем) — может использоваться для контроля дублей или выделения списка уникальных элементов.
Есть «набор» — сортирванный список однотипных элементов с реализацией специфических функций типа AND, OR, XOR, DIFF. Тоже писался под конкретную задачу где нужно было актуализировать набор некоторых кодов связанных с определенным элементом. Там из БД читался набор существующих кодов, потом по определенным правилам строился набор тех кодов, которые должны быть для данного элемента. Ну а дальше DIFF(набор1, набор2) дает набор кодов, которые нужно удалить (они есть, но их не должно быть), а DIFF(набор2, набор1) — набор кодов, которые нужно добавить (они должны быть, но их нет).
Сейчас вот в работе очень большая задача где на вход прилетают XML (достаточно большие и сложные, содержащие списки, много уровней). Сначала они разбираются в память (с формированием списков там где это нужно). Затем их нужно разложить по десятку таблиц (опять же, с анализом что в таблицах уже есть, что нужно добавить, что изменить, что удалить).
В результате формируется список образов записей с пометкой для каждой — добавление, изменение или удаление. Потом записи по списку накатываются в БД. Причем, если по ходу наката возникла ошибка, то идем обратно по списку, откатывая все что успели накатить.
В этой задаче используется все — списки, наборы, скиплисты…
Фильтры использовались для постобработки GPS треков (там еще были свои хитрые фильтры для выявления участков «дрифта» — когда приемник неподвижен, а координаты гуляют).
а каким образом дрифты определяли?
в наличии только координаты или еще показания других датчиков как-то учитывали?
В общем, если не затруднит — поподробнее можете рассказать?
В целом, алгоритм получился достаточно запутанный и не сказать чтобы окончательный вариант. Но в общем и целом работало.
Подробностей не вспомню уже, но основано было на том, что задавалась «Апертура» и «Порог скорости». Затем выделялись «интервалы» — от каждой точки трека идем вперед по точкам до тех пор, пока очередная точка не удалится от исходной на расстояние, большее «апертуры». Для интервала считалась средняя скорость на интервале — расстояние на время между крайними точками интервала. Если скорость ниже пороговой — это считается дрифтом.
Ну а дальше там было что-то с медианным усреднением точек внутри дрифт-участков…
Я потом тот проект отдал другому человеку, не знаю уж что с ним стало. На гите он его выложил TrackProcessor
Собственно дрифт — Дрифт
Интерфейс: Интерфейс
Давно это было…
Это была вторая реализация. Первая сохранилась только у меня в древних исходниках. Там первичное определение дрифт-участков было более «графическим» — было некое скользящее «окно» в виде прямоугольника, охватывающего группу точек трека. И суть была в том, что чем ближе прямоугольник к квадрату, тем больше подозрение на дрифт. Но тот вариант иногда ловил лишнего, второй получился более надежным.
Нужно знать о том, что такое алгоритм, нужно уметь самостоятельно придумывать простые алгоритмы, например, работающие по «жадному» принципу. Ещё нужно обладать знаниями о самых распространённых структурах данных, вроде хеш-таблиц, очередей и стеков. Но что-то достаточно специфическое, вроде алгоритма Дейкстры или A*, или чего-то ещё более сложного, это — не то, что нужно заучивать наизусть. Если вам эти алгоритмы реально понадобятся — вы легко сможете найти справочные материалы по ним.
Этим все сказано. Отличная статья!
Один из наших программистов решил реализовать, для вывода контактов, сортировку вставками. В 2013 году, когда Skype подключался к сети, контакты загружались партиями. Для загрузки их всех требовалось некоторое время. В результате тот программист подумал, что лучше будет строить список контактов, упорядоченных по именам, используя сортировку вставками. Мы много обсуждали этот алгоритм, размышляли о том, почему бы просто не использовать что-то такое, что уже реализовано.
Занятно, я в такой же ситуации решил что самая быстрая сортировка это когда сортировать вообще не надо, и сделал на основе «быстрой» сортировку нужного «окна». Правда у меня ситуация была со списком размером 100-500 тысяч, и сортировка там действительно дико тормозила
Спасибо за статью! :-)
Скажите пожалуйста, как Вы относитесь к не целевому использованию инструментов для реализации алгоритмов и структур данных? Например, к очередям хранящимся и реализованным в реляционной БД.
Если реализация очереди на бд эффективна, значит она достойна применения (за неимением специализированного инструмента).
Опять же, как реализована «настоящая очередь»? Может быть как раз на основе той самой бд? :-)
Разве что замечу, что я приверженец идеи — топор у дровосека, скальпель у хирурга и никогда наоборот. А после супер эффективной реализации очереди в OLTP системе обнаруживается, что иметь длинную очередь больно, к примеру из-за MVCC в postgres
На мой взгляд побочные эффекты всегда надо (по мере возможности) рассматривать и предусматривать.
Хотя сталкивался с ситуациями, когда «целевое использование» оказывается неэффективным.
Вот из текущего. На AS/400 есть такой системный объект *DTAARA (Data Area) — область данных размером до 2000 байт куда можно писать и откуда читать что угодно. Например, некоторые настроечные параметры.
Вроде бы специально придумано для этого, есть чтение с блокировкой, просто чтение, запись… И реализованы специальные инструменты для работы с этими объектами. И в системе есть команды для их чтения и изменения… И все очень удобно.
Но. Оказалось что работа с этими объектами достаточно ресурсозатратна для системы. Значительно более ресурсозатратна чем работа с объектом типа *USRSPC (User Space). Который сложнее в работе (хотя и дает больше возможностей).
Структуры данных и алгоритмы, которыми я пользовался, работая в технологических компаниях