Комментарии 53
Пользуетесь ли вы структурами данных и алгоритмами в повседневной работе? Я обратил внимание на то, что всё больше и больше людей считает алгоритмы чем-то таким, чем, без особой связи с реальностью, технические компании, лишь по собственной прихоти, интересуются на собеседованиях.
Я не только пользуюсь алгоритмами, я их ещё и регулярно пишу. Я вообще себе слабо могу представить как должна выглядеть программа без алгоритмов. Потому что:
Алгори́тм (лат. algorithmi — от арабского имени математика Аль-Хорезми) — конечная совокупность точно заданных правил решения произвольного класса задач или набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи
И структурами данных пользуется и их регулярно пишут сами подавляющее большинство программистов. Потому что те же классы это уже структуры данных…
Ну как вы не понимаете, это другое. Многие презирают именно те продвинутые алгоритмы и структуры данных, которые проходят в Computer Science. А от O() просто шарахаются как от грязных ругательств. И сильно недовольны, что это спрашивают на интервью.
Ну я как бы тоже не особо люблю всякие там тестовые задания и просьбы написать "сортировку пузырьком" во время собеседований.
Но всё таки когда пишешь статьи на хабр, то на мой взгляд надо ну хоть немного разбираться в терминологии и этом самом ИТ...
Ну я как бы тоже не особо люблю всякие там тестовые задания и просьбы написать «сортировку пузырьком» во время собеседований.
В целом статья именно об этом — о том, что в FAANG и других компаниях из Долины очень любят алгоритмические задачи на собеседованиях. И там не спрашивают сортировку пузырьком, там спрашивают более сложные алгоритмы и структуры данных. И автор говорит, что это не очень хорошо.
Но всё таки когда пишешь статьи на хабр
Эта статья — не оригинал, а перевод.
А какие алгоритмы и структуры данных (ну, помимо классов, конечно) вы регулярно пишите?
Эта статья — не оригинал, а перевод.
Значит надо при переводе использовать правильную терминологию. Или может быть стоит задуматься что там пишет автор и стоит ли его вообще переводить.
А какие алгоритмы и структуры данных (ну, помимо классов, конечно) вы регулярно пишите?
А это принципиально важно в данном контексте? Речь о том что у вас по хорошему любой код состоит из алгоритмов и/или структур данных. Поэтому вопрос «Пользуетесь ли вы структурами данных и алгоритмами в повседневной работе?» звучит для меня абсолютно дико.
Значит надо при переводе использовать правильную терминологию.
Я считаю, в переводе надо использовать ту терминологию, которую использует автор оригинала. Ну, либо писать свою собственную статью-обсуждение оригинала.
А это принципиально важно в данном контексте? Речь о том что у вас по хорошему любой код состоит из алгоритмов и/или структур данных.
Мне просто интересно. Я понимаю, что вы пользуетесь классами, массивами, хеш-таблицами и подобными. Но фраза, что вы пишите структуры данных и алгоритмы (мне видится, что вы их сами пишите, а не используете встроенные в язык) вызывает интерес. Я сейчас как раз изучаю алгоритмы/структуры и мне интересно, что именно вы используете, а тем более пишите сами, в повседневной работе.
А алгоритмы тем более. Какие алгоритмы используются постоянно? Я не считаю написание метода в классе написанием алгоритма.
Я понимаю, что вы пользуетесь классами, массивами, хеш-таблицами и подобными.
Классы, структуры, массивы, деревья, листы, стэки, очереди, словари… Мне даже сложно сказать какие структуры данных я не использую.
Я не считаю написание метода в классе написанием алгоритма.
Я выше привёл общепризнанное определение алгоритма. По этому определению написание метода в классе вполне себе может являться написанием алгоритма. Ну или каким определением алгоритма пользуетесь вы?
Но фраза, что вы пишите структуры данных и алгоритмы (мне видится, что вы их сами пишите, а не используете встроенные в язык) вызывает интерес. Я сейчас как раз изучаю алгоритмы/структуры и мне интересно, что именно вы используете, а тем более пишите сами, в повседневной работе.
Для того чтобы ответить на этот вопрос мне сначала надо понять что вы понимаете под словом «алгоритм».
А всё это вы используете напрямую, или опосредовано, через библиотеки? Для какого класса задач?
Я если честно не совсем понимаю вопрос. Чем «напрямую» отличается от «опосредовано, через библиотеки» и как одно должно быть возможно без другого? И что такое «классы задач» и какие вообще бывают?
Чем «напрямую» отличается от «опосредовано, через библиотеки» и как одно должно быть возможно без другого
Тем, что во втором случае не надо ничего знать про эти самые алгоритмы-шмагоритмы.
Математика программистам не нужна же. /s
Ну я вполне себе часто использую просто библиотеки и не заморачиваюсь как оно там внутри имплементированно.
Если это важно, то прежде чем использовать библиотеку я как минимум смотрю что они там делают или хотя бы читаю в доках какая там сложность в тех или иных ситуациях.
А иногда приходится и самому всё это писать.
П.С: Ну и самые для меня «сложные алгоритмы» это пожалуй был расчёт оптимальной загрузки/маршрута для грузовиков. Вот там у меня мозги кипели. Правда писал я не один и среди нас были и математики.
Если это важно, то прежде чем использовать библиотеку я как минимум смотрю что они там делают или хотя бы читаю в доках какая там сложность в тех или иных ситуациях.
А иногда приходится и самому всё это писать.
П.С: Ну и самые для меня «сложные алгоритмы» это пожалуй был расчёт оптимальной загрузки/маршрута для грузовиков. Вот там у меня мозги кипели. Правда писал я не один и среди нас были и математики.
Ну не надо прямо сгущать краски. Просто во втором случае можно довольно долго работать как слесарь, а не как инженер, и произвести довольно много полезного и приносящего деньги кода. А в первом случае — надо уж совсем по-честному погружаться в алгоритмику с головой.
Тут вопрос несколько спорный.
Пользуясь библиотеками, но не вникая в их устройство в рискуете получить неэффективный код, сами того не понимая.
Как пример, в QT был реализован алгоритм SkipList. Но. Один из параметров, существенно влияющий как на производительность, так и на потребление памяти, был тупо установлен в некоторое усредненное значение и при этом скрыт от пользователя. Не понимая алгоритма и не вникая в его конкретную реализацию пользователь получал снижение производительности при увеличении потребления памяти.
И таких примеров я на своем веку встречал предостаточно.
К сожалению, сейчас такой код вполне себе приносит деньги. Т.е. слабали, спихнули заказчику, получили свои деньги и свалили. А через какое-то время заказчик вынужден искать людей, которые все это будут править или переделывать. Например, когда возрастет нагрузка и все это перестанет справляться.
И с таким тоже приходилось сталкиваться, увы.
Пользуясь библиотеками, но не вникая в их устройство в рискуете получить неэффективный код, сами того не понимая.
Как пример, в QT был реализован алгоритм SkipList. Но. Один из параметров, существенно влияющий как на производительность, так и на потребление памяти, был тупо установлен в некоторое усредненное значение и при этом скрыт от пользователя. Не понимая алгоритма и не вникая в его конкретную реализацию пользователь получал снижение производительности при увеличении потребления памяти.
И таких примеров я на своем веку встречал предостаточно.
К сожалению, сейчас такой код вполне себе приносит деньги. Т.е. слабали, спихнули заказчику, получили свои деньги и свалили. А через какое-то время заказчик вынужден искать людей, которые все это будут править или переделывать. Например, когда возрастет нагрузка и все это перестанет справляться.
И с таким тоже приходилось сталкиваться, увы.
Пользуясь библиотеками, но не вникая в их устройство в рискуете получить неэффективный код, сами того не понимая.
Абсолютно верно. Но просто очень часто эффективность вашего кода вас интересует только в определённых границах. И до тех пор пока эти границы не нарушаются, оптимизация кода «вручную» это никому не нужная потеря времени и/или денег.
Т.е. слабали, спихнули заказчику, получили свои деньги и свалили. А через какое-то время заказчик вынужден искать людей, которые все это будут править или переделывать. Например, когда возрастет нагрузка и все это перестанет справляться.
И такое бывает. Но с другой стороны если заказчик указал что он собирается использовать вашу систему с определённой нагрузкой, а сам потом вдруг решает увеличить нагрузку на несколько порядков, то это уже он сам и виноват.
Абсолютно верно. Но просто очень часто эффективность вашего кода вас интересует только в определённых границах. И до тех пор пока эти границы не нарушаются, оптимизация кода «вручную» это никому не нужная потеря времени и/или денег.
Я бы согласился, не будь у нас в бэклоге огромного пула задач на оптимизацию.
Вот это реальная потеря времени и денег.
Причем, во многих задачах явно видно что просто человек сделал как попроще, не задумываясь о том, а нет ли решения более эффективного. И выбор его на этапе начальной разработки обошелся бы намного дешевле последующей доработки с неизбежным ретестом.
Ну я бы тогда пожалуй сказал что это у вас что-то идёт не так.
У нас огромного пула задач на оптимизацию нет. Да и вообще оптимизация, которой мы занимаемся «за свой счёт» а не по заказу клиента, у нас достаточно редкое событие.
Но да, если на код ревью всплывает ну вот совсем плохо оптимизированное решение, то человеку об этом говорят. Или если тесты показывают что-то странное в этом плане, то тоже разбираемся обычно.
У нас огромного пула задач на оптимизацию нет. Да и вообще оптимизация, которой мы занимаемся «за свой счёт» а не по заказу клиента, у нас достаточно редкое событие.
Но да, если на код ревью всплывает ну вот совсем плохо оптимизированное решение, то человеку об этом говорят. Или если тесты показывают что-то странное в этом плане, то тоже разбираемся обычно.
Просто у нас за долгое время накоплена огромная кодовая база. И на проме очень много чего работает.
Ну и нагрузка порядка 3млрд изменений (только изменений) БД в сутки. И таблиц в БД тысячи.
Всего очень много. И оптимизация занятие вынужденное. Когда в пике нагрузка серверов (кластер из трех серверов по 16 12-ядерных SMT8 процессоров POWER9 в каждом) превышает 90%, мы вынуждены что-то с этим делать. Ибо остановка какой-либо системы это не только репутационные потери, но и в некоторых ситуациях штрафы со многими нулями от регулятора (да, там все регламентировано, в том числе и предельные времена простоя отдельных систем).
Ну и нагрузка порядка 3млрд изменений (только изменений) БД в сутки. И таблиц в БД тысячи.
Всего очень много. И оптимизация занятие вынужденное. Когда в пике нагрузка серверов (кластер из трех серверов по 16 12-ядерных SMT8 процессоров POWER9 в каждом) превышает 90%, мы вынуждены что-то с этим делать. Ибо остановка какой-либо системы это не только репутационные потери, но и в некоторых ситуациях штрафы со многими нулями от регулятора (да, там все регламентировано, в том числе и предельные времена простоя отдельных систем).
И поэтому я с вами абсолютно согласен что вам очень хорошо надо следить за производительностью. И в такой ситуации я бы тоже сторонние библиотеки использовал очень осторожно.
Но вот например у нас сейчас был запрос oт клиента добавить ему возможность дампа отдельных регионов памяти и просмотра этих дампов в хексе. Регионы при этом по спецификации не могут быть больше 256МБ. И я конечно могу написать сам с нуля этот самый hex viewer, но есть куча библиотек, которые 256МБ «рендерят» за секунду. И зачем мне тогда тратить на это время и деньги клиента?
Но вот например у нас сейчас был запрос oт клиента добавить ему возможность дампа отдельных регионов памяти и просмотра этих дампов в хексе. Регионы при этом по спецификации не могут быть больше 256МБ. И я конечно могу написать сам с нуля этот самый hex viewer, но есть куча библиотек, которые 256МБ «рендерят» за секунду. И зачем мне тогда тратить на это время и деньги клиента?
Я сейчас как раз изучаю алгоритмы/структуры и мне интересно, что именно вы используете, а тем более пишите сами, в повседневной работе
Что понимать под «пишете сами»? Разработку собственного алгоритма? Разработку собственной реализации описанного где-то алгоритма (или адоптацию его под свою задачу)?
Весть процесс разаработки есть построение некоторого алгоритма для решения поставленной задачи.
Ну слушайте, я вот последние лет пять занимаюсь маппингом json-ов на формочки и маппингом формочек на json-ы. Можно конечно, считать, что это тоже алгоритмы, просто очень простые, но размеры логических блоков, которыми я оперирую очень уж высоки (недавно поймал себя на том, что не помнил, можно ли у строки взять по индексу символ, типа так: s[3]).
Я про нормальные алгоритмы из книжек, где надо оптимизировать какую-нить функцию, применить каких-нить maxheap-ов и фильтров Блума, да хотя бы граф какой-нибудь обойти.
Я про нормальные алгоритмы из книжек, где надо оптимизировать какую-нить функцию, применить каких-нить maxheap-ов и фильтров Блума, да хотя бы граф какой-нибудь обойти.
«Грокаем алгоритмы» — странная рекомендация. Это научпоп для тех, кто занимается кодингом на любительском уровне. Если человек хочет быть профессионалом, читать он должен не популяризаторские книжки с картинками, а нормальные учебники. Начиная с Вирта или Кормена («Водный курс») и — при желании — продолжая Корменом («Построение и анализ») или Кнутом.
Добавлю от себя. Работая в гугле, приходилось писать динамическое программирование, использовать дек, бинарный поиск. На собеседованиях в качестве алгоритмической задачи задаю упрощенную версию того, что лично писал во время работы.
Из неперечисленного в статье и комментариях.
HyperLogLog несколько раз применял. Причем не классически, для подсчета количества, а для отбрасывания копий данных. Если не важно что можно потерять часть данных при коллизиях, то вполне себе решение.
Операции над разреженными векторами, чтобы можно было тот же TFIFD считать с малыми затратами оперативы.
HyperLogLog несколько раз применял. Причем не классически, для подсчета количества, а для отбрасывания копий данных. Если не важно что можно потерять часть данных при коллизиях, то вполне себе решение.
Операции над разреженными векторами, чтобы можно было тот же TFIFD считать с малыми затратами оперативы.
В embedded постоянно пользуюсь кольцевыми буферами и скользящим медианным фильтром (самодельными). Пару раз юзал самодельный map, потому что почти все структуры данных из стандартной библиотеки С++ используют кучу.
Но при этом считаю, что знать классические алгоритмы (типа сортировок и поиска в глубину) — это просто интересно.
В прошлых проектах много использовал алгоритмы фильтрации — Дуглас-Пеккер, Калман, Хеджвик-Прескотт, медианный фильтр, ФНЧ.
Сейчас больше списки -обычные, с ключом и сортировкой (несколько типов списков делал сам на основе алгоритма SkipList).
Сейчас больше списки -обычные, с ключом и сортировкой (несколько типов списков делал сам на основе алгоритма SkipList).
Это где такое и для каких задач?
Предположу, что любая обработка датчиков, от GPS до уровня воды в бочке. Списки могут быть хитрым базами данных (колоночные, in-memory).
А почему это нельзя какой-нибудь библиотекой делать?
потому, что для конкретного контроллера, например, библиотеки может не быть. Или она может «не влазить» по памяти, например.
Ну и — библиотеки же кто-то пишет…
Ну и — библиотеки же кто-то пишет…
А ещё, как с криптографией, иногда надо подробно понимать алгоритм внутри, например значение параметров.
Потому что ее может не быть под данную платформу. Или ее на эту платформу тяжело портировать. Или она слишком общая, универсальная, а это значит что с ней тяжело работать в каждом конкретном случае и любая универсальность делается за счет эффективности — код заточенный под решение конкретной задачи будет всегда эффективнее некоего универсального на все случаи жизни.
Иногда встречается «старое» железо, или ограничения по памяти/производительности у существующего, и библиотеки применять там категорически не стоит. Даже в наше время не всё железо «2 ядра, 2 гига»)
Эээ и почему вдруг "категорически не стоит"? В чём по вашему принципиальная проблема библиотек, которая не позволяет их использовать в такой ситуации?
Я, например, при малом количестве памяти у железки, лучше самописный фильтр сделаю с заданными параметрами обработки, чем буду тянуть в нее все виды фильтров. Я не критикую идею применения библиотек в целом — она даже очень хорошая и упрощает жизнь — я сам постоянно, в этом же lad или fbd, ими пользуюсь, часть библиотек делаю сам для ЦОС или мониторинга в проекте, я говорю просто о разумном подходе к их применению=)
Фильтры использовались для постобработки GPS треков (там еще были свои хитрые фильтры для выявления участков «дрифта» — когда приемник неподвижен, а координаты гуляют).
Списки используются в основном для кеширования данных при работе с БД. Тут надо иметь ввиду, что сейчас работаю под 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 (достаточно большие и сложные, содержащие списки, много уровней). Сначала они разбираются в память (с формированием списков там где это нужно). Затем их нужно разложить по десятку таблиц (опять же, с анализом что в таблицах уже есть, что нужно добавить, что изменить, что удалить).
В результате формируется список образов записей с пометкой для каждой — добавление, изменение или удаление. Потом записи по списку накатываются в БД. Причем, если по ходу наката возникла ошибка, то идем обратно по списку, откатывая все что успели накатить.
В этой задаче используется все — списки, наборы, скиплисты…
Списки используются в основном для кеширования данных при работе с БД. Тут надо иметь ввиду, что сейчас работаю под 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
Собственно дрифт — Дрифт
Интерфейс: Интерфейс
Давно это было…
Это была вторая реализация. Первая сохранилась только у меня в древних исходниках. Там первичное определение дрифт-участков было более «графическим» — было некое скользящее «окно» в виде прямоугольника, охватывающего группу точек трека. И суть была в том, что чем ближе прямоугольник к квадрату, тем больше подозрение на дрифт. Но тот вариант иногда ловил лишнего, второй получился более надежным.
В целом, алгоритм получился достаточно запутанный и не сказать чтобы окончательный вариант. Но в общем и целом работало.
Подробностей не вспомню уже, но основано было на том, что задавалась «Апертура» и «Порог скорости». Затем выделялись «интервалы» — от каждой точки трека идем вперед по точкам до тех пор, пока очередная точка не удалится от исходной на расстояние, большее «апертуры». Для интервала считалась средняя скорость на интервале — расстояние на время между крайними точками интервала. Если скорость ниже пороговой — это считается дрифтом.
Ну а дальше там было что-то с медианным усреднением точек внутри дрифт-участков…
Я потом тот проект отдал другому человеку, не знаю уж что с ним стало. На гите он его выложил TrackProcessor
Собственно дрифт — Дрифт
Интерфейс: Интерфейс
Давно это было…
Это была вторая реализация. Первая сохранилась только у меня в древних исходниках. Там первичное определение дрифт-участков было более «графическим» — было некое скользящее «окно» в виде прямоугольника, охватывающего группу точек трека. И суть была в том, что чем ближе прямоугольник к квадрату, тем больше подозрение на дрифт. Но тот вариант иногда ловил лишнего, второй получился более надежным.
Там еще были всякие алгоритмы. Например, Фильтр Хеджвика-Прескотта, который используется в бизнесе в основном. Но я его использовал для фильтрации выбросов (точек, слишком далеко улетевших от трека) — сначала Хеджвиком с достаточной степенью гладкости строится линия «тренда», а потом фильтруются точки, которые улетели от тренда дальше заданного предела. Такое вот неожиданное применение :-)
Нужно знать о том, что такое алгоритм, нужно уметь самостоятельно придумывать простые алгоритмы, например, работающие по «жадному» принципу. Ещё нужно обладать знаниями о самых распространённых структурах данных, вроде хеш-таблиц, очередей и стеков. Но что-то достаточно специфическое, вроде алгоритма Дейкстры или A*, или чего-то ещё более сложного, это — не то, что нужно заучивать наизусть. Если вам эти алгоритмы реально понадобятся — вы легко сможете найти справочные материалы по ним.
Этим все сказано. Отличная статья!
Один из наших программистов решил реализовать, для вывода контактов, сортировку вставками. В 2013 году, когда Skype подключался к сети, контакты загружались партиями. Для загрузки их всех требовалось некоторое время. В результате тот программист подумал, что лучше будет строить список контактов, упорядоченных по именам, используя сортировку вставками. Мы много обсуждали этот алгоритм, размышляли о том, почему бы просто не использовать что-то такое, что уже реализовано.
Занятно, я в такой же ситуации решил что самая быстрая сортировка это когда сортировать вообще не надо, и сделал на основе «быстрой» сортировку нужного «окна». Правда у меня ситуация была со списком размером 100-500 тысяч, и сортировка там действительно дико тормозила
Солидарен с автором — гораздо важнее понять (что человек знает, умеет и может), чем то (что человек ПОКА не знает, не умеет или не может). Особенно это относится к случаям, когда узнать это можно за короткое время, как в примере с (Макс Хауэлл).
Спасибо за статью! :-)
Спасибо за статью! :-)
Удивительно! Я оказывается использовал «бинарное дерево» в программе гидравлического расчёта (макросы VBA Excel) отопление и водоснабжение… Спасибо за статью!
Отличная статья! Спасибо!
Скажите пожалуйста, как Вы относитесь к не целевому использованию инструментов для реализации алгоритмов и структур данных? Например, к очередям хранящимся и реализованным в реляционной БД.
Скажите пожалуйста, как Вы относитесь к не целевому использованию инструментов для реализации алгоритмов и структур данных? Например, к очередям хранящимся и реализованным в реляционной БД.
Что значит «нецелевое использование»? Тут метрикой может быть только эффективность в выполнении поставленной задачи и ничего более.
Если реализация очереди на бд эффективна, значит она достойна применения (за неимением специализированного инструмента).
Опять же, как реализована «настоящая очередь»? Может быть как раз на основе той самой бд? :-)
Если реализация очереди на бд эффективна, значит она достойна применения (за неимением специализированного инструмента).
Опять же, как реализована «настоящая очередь»? Может быть как раз на основе той самой бд? :-)
Ваш ответ мне понятен. Холивар не буду устраивать. :)
Разве что замечу, что я приверженец идеи — топор у дровосека, скальпель у хирурга и никогда наоборот. А после супер эффективной реализации очереди в OLTP системе обнаруживается, что иметь длинную очередь больно, к примеру из-за MVCC в postgres
Разве что замечу, что я приверженец идеи — топор у дровосека, скальпель у хирурга и никогда наоборот. А после супер эффективной реализации очереди в OLTP системе обнаруживается, что иметь длинную очередь больно, к примеру из-за MVCC в postgres
Ну мы тут не ради холиваров :-)
На мой взгляд побочные эффекты всегда надо (по мере возможности) рассматривать и предусматривать.
Хотя сталкивался с ситуациями, когда «целевое использование» оказывается неэффективным.
Вот из текущего. На AS/400 есть такой системный объект *DTAARA (Data Area) — область данных размером до 2000 байт куда можно писать и откуда читать что угодно. Например, некоторые настроечные параметры.
Вроде бы специально придумано для этого, есть чтение с блокировкой, просто чтение, запись… И реализованы специальные инструменты для работы с этими объектами. И в системе есть команды для их чтения и изменения… И все очень удобно.
Но. Оказалось что работа с этими объектами достаточно ресурсозатратна для системы. Значительно более ресурсозатратна чем работа с объектом типа *USRSPC (User Space). Который сложнее в работе (хотя и дает больше возможностей).
На мой взгляд побочные эффекты всегда надо (по мере возможности) рассматривать и предусматривать.
Хотя сталкивался с ситуациями, когда «целевое использование» оказывается неэффективным.
Вот из текущего. На AS/400 есть такой системный объект *DTAARA (Data Area) — область данных размером до 2000 байт куда можно писать и откуда читать что угодно. Например, некоторые настроечные параметры.
Вроде бы специально придумано для этого, есть чтение с блокировкой, просто чтение, запись… И реализованы специальные инструменты для работы с этими объектами. И в системе есть команды для их чтения и изменения… И все очень удобно.
Но. Оказалось что работа с этими объектами достаточно ресурсозатратна для системы. Значительно более ресурсозатратна чем работа с объектом типа *USRSPC (User Space). Который сложнее в работе (хотя и дает больше возможностей).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Структуры данных и алгоритмы, которыми я пользовался, работая в технологических компаниях