Комментарии 83
Кажется, в последнем варианте было-бы оптимальнее сделать так:
var top = memory.SplitAny(separators)
.OrderByDescending(w => w.Length)
.Where(w => predicate(w.Span))
.Select(w => w.ToString())
.Distinct()
.Take(count)
.ToArray();
Да, вы правы, так будет лучше. По скорости разница не очень большая, а вот памяти в 2 раза меньше расходует.
Это предложение не совсем универсальное, дело в тонкостях реализации метода Distinct. Вообще говоря он не гарантирует что порядок сохранится. Это актуально если работать с базами данных, там порядок может изменится. Его реализация для работы в памятью сохраняет порядок. К тому же если предикат отсеивает много элементов, то его лучше поднять выше сортировки.
Спасибо за статью и приятно что моя статья получила отклик.
Если позволите, то дам комментарии.
1) Вы неверно протрактовали смысл моей статьи. Ваша статья как раз является полным подтверждением моей и высказанных там тезисов, что легко подтвердить:
мои слова "всё же считаю, что всегда важен сам контекст задачи" и ваши "Всё зависит от контекста, в котором будет работать алгоритм", то есть в основной части смысла мы сходимся.
Так же, я объясняю, почему кастомная реализация может быть неприменима "многие простейшие задачи оборачивают в готовые методы актуального ЯП, что в первую очередь решает основную задачу бизнеса - быструю разработку", что соответствует тезису из вашей статьи "В первую очередь, я пишу код для людей. Он должен легко читаться, поддерживаться и меняться по мере необходимости".
То есть и в введении и в заключении мы оба говорим абсолютно одинаковые вещи.
2) Так как я жутко не люблю когда мне приписывают то, чего я не говорил, то отдельного комментирования требуют следующие ваши слова,
Не так давно прочитал статью "В поисках алгоритмического дзена", где автор обсуждает подходы к использованию алгоритмов в рабочих задачах
Я в своей статье не обсуждал подходы к использованию алгоритмов в рабочих задачах. Я чётко обозначил проблему использования стандартных методов при решении задач на собеседованиях и при выдаче результатов на сервисах вроде StackOverflow. Это раз. И два - я однозначно пишу в финале статьи что
ни алгоритмы, ни современность ЯП, ни ваши зазубренные знания стандартных методов напрямую не оказывают влияния на качество вашего кода. Всё зависит от того - как вы всем этим научитесь пользоваться.
Что полностью соответствует финалу вашей статьи
Современные языки/платформы предоставляют кучу готовых алгоритмов, структур данных, которые могут сильно улучшить производительность без необходимости писать сложный код. Самое главное - их правильное использование.
3)
В статье подчеркивается, что даже наивная реализация конкретного алгоритма будет быстрее готовых средств/реализаций, существующих в платформе
Ну этому есть подтверждающие факты.
и уж тем более будет быстрее специальный алгоритм для данного конкретного случая
и это тоже факт.
Возникает ощущение, что использование самописных алгоритмов обладает абсолютным преимуществом над использованием готовых реализаций
Только у малопосвященных в тему.
Например я еще с 80-х, используя стандартные библиотеки часто говорил, что "пишут их люди поумнее нас", на вопросы от тех, кто вместо std норовил написать что-то своё. Тут мы возвращаемся к началу - важен контекст.
4)
В этой статье я постараюсь показать почему использование самописного алгоритма не всегда оправдано, даже если он работает значительно быстрее
Стандартные методы сами по себе являются специальными реализациями определенных алгоритмов, просто их делают универсальными, а не привязанными к char, byte или int, а так же оформляют соответствующим образом - чтобы ЛЮДИ могли легко читать написанное. В этом смысл. И вы не спешите их переписывать и вас не волнует насколько красиво они написаны внутри. Ну во всяком случае это точно не будет волновать 99% тех кто ими будет пользоваться (я частенько залезаю внутрь чтобы посмотреть как именно происходит какая-то проверка, хотя бы тот же IsAsciiLetter() ).
То есть любой специальный метод легко можно сделать "стандартным", разместить в Nuget и ставить для своего проекта. Не вижу почему моя реализация Jump хуже того-же TimSort или RuNS, которые мало кто даже написать своими силами сможет, не то что исправить (вы же в курсе что TimSort входил в состав Java/Python >10 лет имея на борту ошибку?).
---
В заключении - вы написали хорошую статью в качестве продолжения затронутой мной проблематики, но неверно расставили акценты. Статье я поставил плюс, а вам поднял карму, так как на мой взгляд проблематика первичнее, нежели моё отношение к недоработкам статьи.
Тем более я не отношусь к профессиональному сообществу программистов, хотя образование и позволяет, и наверное могу в чём-то ошибаться, хотя в рамках этих статей считаю что мы оба говорим об одном и том же.
Дополню - можно Jump реализовать как класс с методами для <T>, <object>, ну и в целом расширить задачу как - поиск однотипного максимума последовательности, добавить возможность использования своей реализации компаратора. В общем в по уму, по ООПэшному. Завернуть в пакет, разместить в Nuget и github и отдать сообществу в пользование. Не вижу причин в таком виде игнорировать его в проде для любой софтверной компании.
То есть это не задача поиска экстремума, а поиск максимальной длительности сигнала.
Кстати никто не мешает для стандартных типов написать реализации с применением каких-то хитростей, что например для char даст сопоставимую производительность, которая показана в наших статьях, а для <object> вероятно как-то более универсально реализовать.
Спасибо за отзыв, и за плюсы!
Если я не так понял ваш посыл, и, на самом деле, мы сходимся во мнении, то это замечательно! И я прошу прощения если где-то неправильно передал ваши слова.
Я написал эту статью, потому что хочу явно прояснить некоторые моменты, для себя, и для тех, кто, возможно, так же, как и я понял вашу статью, и для тех кто может воспринять её как руководство к действию.
вы пишите: "Всё зависит от контекста, в котором будет работать алгоритм", но не даёте тот самый контекст для задачи. И, по умолчанию, я воспринял это в контексте бизнес задачи.
Я чётко обозначил проблему использования стандартных методов при решении задач на собеседованиях и при выдаче результатов на сервисах вроде StackOverflow.
Я не увидел в статье упоминания того, что это задача для собеседований.
ни алгоритмы, ни современность ЯП, ни ваши зазубренные знания стандартных методов напрямую не оказывают влияния на качество вашего кода. Всё зависит от того - как вы всем этим научитесь пользоваться.
Со вторым предложением я полностью согласен, без умения пользоваться никакой ЯП не поможет. А вот с первой частью - совсем нет!
Что полностью соответствует финалу вашей статьи
Совсем нет, я пытался высказать противоположное мнение! Именно современные ЯП и знание стандартных методов могут сильно улучшить качество кода. А вот использование алгоритмов может сделать код сложнее в поддержке.
Возникает ощущение, что использование самописных алгоритмов обладает абсолютным преимуществом над использованием готовых реализаций
Только у малопосвященных в тему.
Это отлично что вы понимаете, когда стоит использовать свой алгоритм, а когда стандартный. Но лично мне это не было очевидно из вашей статьи. И, возможно, у кого-то еще возникло подобное ощущение, и я постарался предостеречь людей, чуть меньше посвященных в тему.
Стандартные методы сами по себе являются специальными реализациями определенных алгоритмов
Ну с этим трудно спорить)
Если вам показалось, что я во всех случаях отговариваю пользоваться самописными алгоритмами из-за их сложности, то это не так. При написании библиотек/фреймворков они могут быть очень полезны и востребованы, я рассматривал контекст именно бизнес задач.
Если сократить мою статью до одного предложения:
Не нужно использовать специальные алгоритмы, пока вы можете решить вашу задачу стандартными средствами языка/фреймворка.
Не нужно использовать специальные алгоритмы, пока вы можете решить вашу задачу стандартными средствами языка/фреймворка
Полностью я такую точку зрения не разделяю. Скорее я придерживаюсь подхода (в опросе упомянул о нем), что нужно БЫСТРО написать наивно и стандартно, а потом, как от точки старта плясать в сторону улучшения. Тут есть один момент, мы подразумеваем что сама архитектура решения уже спроектирована оптимально (или близко к оптимальному), то есть вопрос только в реализации. При "кривой" архитектуре не важно вообще что и как вы напишете, так как переписывать придутся всё и много раз.
Переписывать придётся много раз, потому что требования будут меняться много раз.
И вопрос только в том, на сколько легко вы сможете адаптировать свой код под новые требования.
Ну а какая разница между TimSort и Jump? Я разницу не вижу. Это такой же придуманный алгоритм как и все. Сделайте класс универсальный, не вижу никакой проблемы. Если ваша задача уйдет за рамки использования TimSort вам точно так же придется менять код под другой алгоритм.
Я никогда не сравнивал TimSort и Jump.
Разница между Jump и связкой Split().MaxBy() в том, что метод Jump вам придется написать, протестировать, поддерживать, а Split и MaxBy уже есть в системе.
Для Jump тоже есть своя ниша, он не бесполезен. Но, затраты на его написание и поддержку должны быть оправданы, только и всего.
Сравниваю я, так как TimSort появился как "поделка на коленке", оброс, возмужал и был встроен в библиотеки (при этом оставался забагован). Так почему вы запрещаете такому (не багам конечно) происходить с другими алгоритмами? Но всегда есть какое-то начало. Какая-то контора применит у себя, будет тяжелый к сопровождению код, потом кто-то напишет реализацию удобную в работе (если вы про ООП, так как я и сейчас не вижу проблем с её использованием).
Какая разница напишете вы Split или Jump? Split в NET 1 вообще был?
Запрещаю? Ни в коем случае!
Если вы оформите свой алгоритм в виде библиотеки, это будет отличным решением. Буду ли я ей пользоваться - вопрос. Выбор опенсурсной библиотеки это тема на отдельную статью.
У меня есть вопросы только в том случае, если вы пишите подобный код как решение конкретной бизнес задачи.
Split в NET 1 вообще был?
Важно что он есть сейчас, и сейчас мы можем его использовать
Ну то есть вопрос не в самописных методах, а в том как они оформлены?
Вопрос в том, какую задачу вы решаете этим кодом.
Это понятно, просто раз вы статью пишете в противовес моей, то вас не устроили мои тезисы. Я и пытаюсь найти что же не так. Пока вы всё пишете - похоже на то, что писал я, не в деталях конечно. Почему? Потому что я в статье написал например такое:
1) многие простейшие задачи оборачивают в готовые методы актуального ЯП, что в первую очередь решает основную задачу бизнеса - быструю разработку
2) я всегда сначала пишу "наивный код", мне нужно проникнуться задачей, поймать волну так сказать. И только потом заниматься оптимизацией
3) мне кажется тот, кто сразу напишет через Split или LINQ и будет думать, что у него всё отлично - не особо эффективен
И я в статье не трогал задачи бизнеса совсем, а вы, как я понимаю, как раз и говорите о том, что важнее для бизнеса, то есть в этом аспекте статьи даже не пересекаются.
Может из статьи не понятно, но основные штрихи там о том, что много говорят про алгоритмы, а на деле их не применяют, это раз. Когда применяют, то делают это бездумно. И меня в первую очередь занимает контекст того как это подано в общедоступном интернете, для новичков в том числе. Тот же SO не научит вас выбирать, потому что на SO не обсуждаются задачи, там обсуждаются реализации, а без контекста, как мы уже выяснили любой способ - это пальцем в небо. SO не бесполезен, просто он не решает этой проблемы (вероятно никогда и не пытался).
что в первую очередь решает основную задачу бизнеса - быструю разработку
Быстрая разработка не всегда есть основная задача бизнеса.
Строго говоря, основная задача любого бизнеса есть получение прибыли. А разработка есть способ автоматизации бизнес-процессов для увеличения прибыли (напрямую, за счет снижения накладных расходов и т.п.).
Но у любого бизнеса есть приоритеты. Есть бизнес, основанный на скорейшем выводе на рынок некоего продукта. Пусть кривого-косого, но вперед всех (сейчас и так сойдет, потом поправим). Тут да. Скорость разработки.
Но есть бизнес, где требуется предоставить качественный продукт. Или бизнес, где некачественная автоматизация процессов приведет к убыткам (репутационные, штрафы регулятора и т.п.). И здесь уже главное не скорость разработки, а качество кода. Другие приоритеты, другие требования.
В остальном с Вашими тезисами в целом согласен.
Быстрая разработка не всегда есть основная задача бизнеса.
Тут во многом зависит от цены ошибки и стоимости доставки. Команда, которая пишет софт для стиральной машины, вряд ли будет применять agile.
По моему опыту, в Альфа-банке такие ТЗ пишут, что во время разработки ни одного вопроса не возникает. Больше нигде не видел настолько проработанных ТЗ.
По моему опыту, в Альфа-банке такие ТЗ пишут, что во время разработки ни одного вопроса не возникает. Больше нигде не видел настолько проработанных ТЗ.
Потому что ТЗ является еще и документацией по задаче. Если что-то приходит на доработку, всегда логику можно по ТЗ понять.
Больше скажу - часто ТЗ потом еще корректируется по написанному коду для полного соответствия.
Переписывать придётся много раз, потому что требования будут меняться много раз.
Ну, казалось бы, если мы начинаем с начала, то есть со сборки требований, то мы можем примерно понять, в каком диапазоне они меняются. Таким образом, предусмотреть архитектуру так, чтобы переписывать пришлось минимальное кол-во раз.
Крупные проекты живут десятилетиями. В таких случаях изменение требований предсказать, практически, невозможно. Преждевременное абстрагирование в ООП так же вредно, как и преждевременная оптимизация. Годами поддерживать ненужный (неиспользуемый) уровень абстракции - довольно дорого. ИМХО дешевле будет отрефакторить, когда (если) он понадобится.
В статье как раз есть пример подобных изменений: сначала нам было нужно только 1 слово, а потом список самых длинных.
Если предусмотреть заранее такое изменение, и писать сразу под список, то придётся писать гораздо более сложный алгоритм, и работать он будет медленнее чем для одного слова. И ещё не факт что в дальнейшем нам вообще он потребуется.
Хороший ли это подход? На мой взгляд - нет. Я лучше напишу код который решает текущую задачу, но напишу его так, чтобы в дальнейшим было легко его править.
Не хочу быть неправильно понятным, так что сразу оговорюсь : это не значит что я считаю что не надо заранее выяснять требования, продумывать архитектуру. Архитектура важна, и она должна предусматривать изменения.
Я лучше напишу код который решает текущую задачу, но напишу его так, чтобы в дальнейшим было легко его править.
Ну, вообще-то, можно сразу уточнить про список. Если заказчику непонятно, то, конечно, пишете решая текущую задачу так, чтобы легко было изменить.
Так в этом и вся соль, заказчик не знает что ему потребуется через неделю, месяц, год.
Потому и подход такой, аджаил)
на хабре было, если правильно помню, про один проект, который лет за 15 стал очень крупным, и когда начались проблемы кто-то пытливый докопался до сути и оказалось, что изначально (тут я просто придумываю так как не помню саму статью) код был написан под работу со строками, потом на него повесили надстройку, а чтобы не переписывать надстройка генерировала данные в строках. Спустя десятилетие огромный проект в основном занимался конвертацией данных в строки и обратно.
Так что я просто не верю что вы сразу можете написать так, что всё будет правильно и легко.
Так что я просто не верю что вы сразу можете написать так, что всё будет правильно и легко.
Любое усложнение кода должно быть обосновано. И "быстрее работает" - вообще не аргумент. У бизнеса не может быть требования вида "надо, чтобы в коде продукта приватная функция f работала как можно быстрее".
Тут говорят что бизнес вообще ничего не решает и ничего не знает, вот вы кодите, а у вас требования к памяти, к производительности и бизнесу вы разве будете что-то говорить? Мне кажется нужно сначала найти консенсус того какой он этот бизнес и какое его участие, а то у одного одно, у другого другое, а я за всему не угонюсь.
вот вы кодите, а у вас требования к памяти, к производительности и бизнесу вы разве будете что-то говорить?
Я не совсем понимаю вопрос. Если есть требования к памяти и производительности, то их нужно удовлетворить. Если исследование вопроса показало, что для этого нужно поменять Split на Jump, то это нужно сделать.И это будет уже обоснованное (требования + замеры вариантов 1 и 2) усложнение кода.
Если есть требования к памяти и производительности, то их нужно удовлетворить
Нет, все тут пишут что заказчик туп и его не нужно посвящать в детали разработки (что я считаю откровенной ерундой), вот в этой парадигме вы пишете код, при реализации вы понимаете (может еще на этапе проектирования), что будут определенные требования к тому-то и тому-то. Если ранее озвученная парадигма работает, то вы ничего бизнесу говорить не станете.
В моей парадигме заказчик определяет архитектуру, вы её разрабатываете и предлагаете, озвучивая минусы и плюсы, а заказчик идёт на выбор. Так как платить ему.
Нет, все тут пишут что заказчик туп и его не нужно посвящать в детали разработки (что я считаю откровенной ерундой)
Вы серьезно рассказываете заказчику что "вот тут у меня Split, а вот там Jump"? Ему это реально интересно?
Наш бизнес работает так - "у нас тут вебсервис который должен получать ответ на запрос .... - сделаете нам сервис-модуль для него". Ну не вопрос - делаем. Внутри достаточно сложный скуль с агрегатными функциями и вот этим всем. Отдаем на тест. Нам отвечают - "на реальных данных ваш сервис-модуль работает до 3-х секунд (данных достаточно много, выборка сложная), наш вебсервис через раз по таймауту отваливается, нам нужно чтобы оно гарантированно укладывалось в 200мс".
Следующий этап - сопровождение. Которое тоже может сказать - ваш модуль потребляет слишком много ресурсов процессора. В условиях пиковых нагрузок это может привести к нехорошим последствиям. Надо поправить.
При этом ни тех ни других не интересует как я это реализую внутри. Им важен правильный результат за минимальное время и с минимальными затратами ресурсов.
Вы серьезно рассказываете заказчику что "вот тут у меня Split, а вот там Jump"? Ему это реально интересно?
Нет. Я предлагаю два варианта - один с требованием к ОЗУ в размере 128 Гб, а второй к 32Гб и быстрее в работе, но в дополнительной потребности к обслуживанию кастомных сервисов (обслуживать же мне, значит это отдельный договор). Вот пусть и выбирают сами что им проще - памяти купить или сопровождать сервис.
При этом ни тех ни других не интересует как я это реализую внутри. Им важен правильный результат за минимальное время и с минимальными затратами ресурсов.
Ну судя по вашему описанию там не заказчик, а стадо дебилов. Если их не интересует как вы реализуете, то откуда требования про 200 мс? Показания не сходятся.
Ну судя по вашему описанию там не заказчик, а стадо дебилов. Если их не интересует как вы реализуете, то откуда требования про 200 мс? Показания не сходятся.
Очень интересное суждение.
Бизнес выставляет требования - данные на входе, данные на выходе, максимальный таймаут. Это все, что их интересует.
Вы когда покупаете стиральную машину - вас что интересует в первую очередь? Функционал, или то, какие микросхемы там внутри?
Нет. Я предлагаю два варианта - один с требованием к ОЗУ в размере 128 Гб, а второй к 32Гб и быстрее в работе, но в дополнительной потребности к обслуживанию кастомных сервисов (обслуживать же мне, значит это отдельный договор). Вот пусть и выбирают сами что им проще - памяти купить или сопровождать сервис.
Каких кастомных сервисов? О чем вы? Мы сейчас говорим исключительно о внутренней реализации. Split который работает медленно и требует больше памяти (зато не думая, левой ногой), или Jump, который работает быстро и требует меньше памяти (но чуть больше строк кода и нужно ум наморщить немного). Вы всерьез считаете, что вариант с Jump потребует какого-то особого обслуживания? Или что в Вашем коде реализации Jump кроме вас никто не разберется? Остальные настолько тупы? Вы пишете такой закрученный код, что кроме Вас никто его не понимает? Серьезно?
Ну и если говорить о железе, то мы работаем на
IBM Power E980
• 120 процессорных ядра Power9
• RAM - 12Тб
• LAN - 10Гигабит
• Storage - 400Тб на SSD
• Operation System: IBMi7.4
Как думаете, сколько стоит нарастить его мощность раза в два?
Функционал, или то, какие микросхемы там внутри?
В первую очередь платформа, технологии, ремонтопригодность. Функциональность месте на 4-5.
Бизнес выставляет требования - данные на входе, данные на выходе, максимальный таймаут.
Ну вы это преподнесли иначе, сначала вы написали софт, а потом вам рассказали про 200 мс.
Вы всерьез считаете, что вариант с Jump потребует какого-то особого обслуживания?
Я как раз так не считаю, но достаточно тех кто так считает.
Или что в Вашем коде реализации Jump кроме вас никто не разберется? Остальные настолько тупы? Вы пишете такой закрученный код, что кроме Вас никто его не понимает? Серьезно?
Процитируйте где я такое утверждаю.
Как думаете, сколько стоит нарастить его мощность раза в два?
К чему этот вопрос вообще?
У бизнеса требования типа "вот этот модуль должен выдавать ответ на запрос в течении не более чем 200мс". Как вы этого добьетесь их не волнует.
Кроме бизнеса есть еще сопровождение. У которого требования по нагрузке. И которые могут выдать вам такое вот заключение:
Из PEX статистики работы PBC01U01R видно, что 33% времени и 36% ресурсов CPU тратится на выполнение QSQRPARS в программе STL#CHKN, т.е. парсинг статических выражений при подготовке SQL запроса,
Поскольку CU130 один из наиболее активно используемых сервис модулей, необоснованное повышенное ресурсопотребление является малодопустимым. Просьба инициировать доработку STL#CHKN.
При "кривой" архитектуре не важно вообще что и как вы напишете, так как переписывать придутся всё и много раз.
Чем проще код, тем проще его переписывать. Если всё равно переписывать, то имеет смысл написать как можно проще.
@Zara6502мне кажется вы не правы, в том плане что как раз в вашей статье все внимание уделено узко специализированному алгоритму. А его даже не надо было делать. Нужно было просто убрать неоптимальные моменты метода Split и всё. И это просто сделать. Т.е. нужно было сделать быстрый алгоритм ленивого перечисления слов в строке и всё. Ленивое перечисление это ключевой момент, так так позволяет избавится от большого потребления памяти. Дальше можно легко выполнять любую необходимую обработку слов. Да он будет в 2-5 раз дольше работать для частного случая, но его можно будет легко менять под большинство требований.
в моей статье есть самый первый абзац, он и определяет то, почему статья написана. то что я сделал там что-то узкоспециализированное (а позже вы предложили свой вариант) это лишь частности. основной акцент как раз на том, что упор в алгоритмы, который обсуждается во множестве статей на Хабре, на мой взгляд, не имеет смысла. и ваши выводы только это подтверждают, то есть мы едины в понимании того, что алгоритмы ради алгоритмов - это не тот путь.
но в статье есть и вторая проблема - унифицированные библиотечные реализации порой сильно далеки даже от наивной, про которые тоже много пишут на Хабре, например применительно к сортировке. Поэтому я не зря упомянул TimSort в обсуждении этой статьи, так как когда-то TimSort был "узкоспециализированным". То есть использование чего-то узкоспециализированного не является табу, важен контекст.
поэтому пардон, но я не могу быть не правым, так как и с автором этой статьи и с вами мы говорим об одном и том же, разве что разными словами. я же нигде в своей статье не пишу о том, что срочно нужно запретить Split и начать пользоваться Jump, мысль моя описана в финале - нужно с умом пользоваться как ЯП так и бибилиотеками.
У вас нигде в статье не написано что НЕ надо писать реализации типа Jump вот в чем моё уточнение. Либо если вы такое написали, то очень незаметно или неявно.
Я же, как и автор второй статьи прямо говорим что надо писать простые и эффективные (пусть и не самые эффективные алгоритмы) и знание стандартной библиотеки это сильно упрощает. Стремление к максимальной эффективности частного алгоритма зло в подавляющем большинстве случаев.
У вас нигде в статье не написано что НЕ надо писать реализации типа Jump вот в чем моё уточнение. Либо если вы такое написали, то очень незаметно или неявно.
Акцент статьи строится на том, что когда мы бездумно пишем сами или требуем от других (это про вопрос образования и тестирования) использование стандартных методов, то это далеко не всегда тот результат, который действительно вам нужен. То есть это такая же крайность, как и написание собственного беспорядочного кода. Как вывод статьи - нужно уметь писать думая головой.
Мне кажется этот смысл сам говорит о том, что "не нужно писать Jump ради Jump'а", так как важен контекст задачи. Для ботлнека на высоконагруженном сервере это одно, для фронта который рисует одну кнопку - это другое.
Я же, как и автор второй статьи прямо говорим что надо писать простые и эффективные (пусть и не самые эффективные алгоритмы) и знание стандартной библиотеки это сильно упрощает.
Да, но это плохо коррелирует с контекстом задачи, иначе вы просто можете оказаться в условиях, когда сначала ляжет ваш сервис, будут у бизнеса убытки, а только потом вы возьмётесь за оптимизации. Об этом пишут и другие, не только я. Я не считаю что упрощение ради упрощения тоже хороший путь, это такая же крайность.
Стремление к максимальной эффективности частного алгоритма зло в подавляющем большинстве случаев.
Я думаю это верно только для определенных ситуаций и проектов. Вы ведь согласитесь, что например геймдев в таких вопросах будет сильно отличаться от вэб-сервера с лендингом, ну а само существование гугла прямо утверждает, что переписывать нужно всё подряд, так как требования и условия эксплуатации сильно отличаются от среднестатистических.
То есть это такая же крайность, как и написание собственного беспорядочного кода.
А можно пояснить - почему вы считает что библиотечный код есть абсолютное добро, а собственный - абсолютное зло.
Вы считаете, что сами не способны реализовать что-то эффективное? Вы всерьез считаете, что простой линейный алгоритм с минимумом ветвлений, занимающий 10-20 строк кода (и абсолютно прозрачный и понятный) будет хуже чем вызов какой-то библиотечной функции, под которой скрывается 100500 уровней абстракций и столько же уровней стека (а когда это вызывается, скажем, 20 000 000 раз это уже очень ощутимые накладные расходы)?
Вот откуда такая уверенность?
Если взять например python, то в нем много чего в библиотеках написано на C, который на порядок быстрее paython. И любой ваш супер оптимальный алгоритм будет проигрывать в скорости коду на C. Да и по затратам памяти массив в numpy намного меньше чем аналогичный paython - ский список. Поэтому для прикладной разработки использовать библиотеки это наверное более оптимально, чем самому изобретать. А вот для системной разработки наверное уже может иметь смысл что-то придумывать.
Давайте посчитаем насколько Jump может быть быстрее. Средняя длина слова я думаю 5-7 букв от языка зависит, на английском думаю в районе 5, значит в 5 раз в теории.
В реальности последовательный перебор имет несколько меньше затрат, поэтому процентов на 20% быстрее остаётся примерно в 4-5 раз на практике.
И это только если требования не изменятся, как только они усложнятся будет ещё меньше разница.
Если вы хотите быстро, то такие расчёты выполняются раз и результат сохраняют. Вся работа по чтению и сохранению данных намного дольше чем сам алгоритм, итоговая разница десятки процентов максимум. Ну и зачем тогда, если на бизнес это не повлияет.
То что есть критические места для бизнеса я не спорю. Архитектура системы намного более тут критична чем супер оптимизация конкретного алгоритма, если она всего в 4-5 раз лучше, но с накладными расходами максимум 10-20%. А может и вообще меньше процента вносить в итоговый результат.
Если вы хотите быстро, то такие расчёты выполняются раз и результат сохраняют
А теперь представьте, что это не один раз. А 10 000 000 раз. Т.е. задача, например, в том, что вам на вход дается 10млн строк и для каждой надо выбрать самое длинное слово.
Ну и зачем тогда, если на бизнес это не повлияет
Откуда такая уверенность? Вот предположим, что у вас на сервере одновременно работает десятки тысяч процессов. А ваш процесс всего лишь звено в длинной цепочке - его результат нужен другому процессу.
И если все они реализованы исходя из таких вот соображений, то все это будет работать очень медленно. А в случае увеличения нагрузки может вообще встать колом. А через год количество данных увеличится и оно потребует тотальной оптимизации всего и вся.
И все потому что вам просто лень лишний раз подумать "а как это можно реализовать быстрее и эффективнее".
Если вы будете в реальности то большие данные не из воздуха берутся, и там уже будет буферное чтение и чтение по словам по токенам и голого чтения по памяти у вас просто не будет... И следовательно вы и не сможете этот алгоритм применить.
Нет. Это может быть 10...50млн записей из БД которые требуют обработки. В том числе (среди всего прочего) - выбор самого длинного слова по одному из полей. Вполне реальный сценарий. Результаты обработки каждой записи потом уходят куда-то дальше.
Тормозит ваша задача - тормозит вся цепочка куда она встроена. А поскольку кроме вашей задачи еще параллельно крутится несколько десятков тысяч других - больше ресурсов процессора вы на себя возьмете - меньше останется другим. И там тоже могут начаться тормоза. А если все это случится в периоды пиковых нагрузок, то есть риск вообще весь сервер затормозить так, что все это скажется в масштабах миллионов клиентов по всей стране. Прецеденты были.
А дальше - комиссия по инцидентам и разборки - кто писал код, кто делал ревью, кто тестировал, кто согласовывал внедрение...
Посему, любой код должен быть максимально быстрым и эффективным. Иначе никак. Не умеешь - ищи где попроще и требования пониже.
Чтение из БД настолько медленнее чем обработка строк в памяти что тут вообще нет смысла обсуждать. Я хоть за нулевое время буду делать обработку строк, в итоге это уменьшит общие затраты на пару процентов максимум.
Это может быть важно в каких то сетевых протоколах, да там есть много мест для тонкой оптимизации. Там её и пременяют, тут я спорить не буду.
Вообще-то нет. Личный опыт.
Вообще, разговоры о том, что современный софт становится медленнее и требует больше ресурсов уже стали общим местом. И одна из причин как раз в том, что разработчикам лень лишний раз "включить мозг" и они предпочитают использовать готовые библиотеки, рассчитанные "на все случаи жизни", но не оптимальные под данную конкретную задачу. К тому же несущие большое количество накладных расходов вследствие большого количества уровней абстракции.
Я ваши желания понимаю, но вы попробуйте у себя на работе им последовать, мне будет интересно насколько быстро вас выставят на мороз или насколько быстро ваш продукт обойдут конкуренты. Для меня критерием является выбор покупателей, и конкуренция на рынке, за что покупатели платят деньги, а не о чем они просто мечтают и рассуждают, при этом многие их них не написали ни строчки кода.
Я понимаю что с ARad у нас не 100%-е общее представление в этом вопросе, но всё же я считаю что упираться рогом в оптимизации и производительность нельзя. Потому что есть классическое деление задачи 20/80, где 20% усилий дают 80% результата. Любое последующее усилие влияет на результат всё меньше и меньше. Поэтому написание быстрого и эффективного кода может просто быть экономически невыгодным. Иногда будет проще увеличить производительность аппаратной части, это ведь тоже вариант решения и бизнес смотрит на цифры, а не на абстрактное заявление "код должен быть ...". Вы же должны понимать что решение о внедрении кода принимают не программисты?
Иногда будет проще увеличить производительность аппаратной части
Вы готовы оплатить увеличение производительности аппаратной части из своего кармана, или предпочтете подумать и решить задачу так, чтобы оно работало на имеющемся железе?
Иными словами, вы предпочитаете делать как вам проще, и при этом "выставить" заказчика на закупку нового железа?
Наращивание производительности железа - те же самые 20/80. Чем дальше, тем дороже. А в современных условиях еще не любое железо здесь просто так доступно.
Вы готовы оплатить увеличение производительности аппаратной части из своего кармана, или предпочтете подумать и решить задачу так, чтобы оно работало на имеющемся железе?
Этот выбор делает заказчик а не я. А вот выбор предоставлю я. Моя задача реализация, а не размышления на тему вселенского блага.
Иными словами, вы предпочитаете делать как вам проще, и при этом "выставить" заказчика на закупку нового железа?
Вы читаете по диагонали.
Наращивание производительности железа - те же самые 20/80
Само собой, только если вы рогом упёрлись в софт забыв про железо, то и эффективного решения ваши заказчики не дождутся.
Само собой, только если вы рогом упёрлись в софт забыв про железо, то и эффективного решения ваши заказчики не дождутся.
За железо отвечаю не я. Я отвечают за максимально эффективное решение по софту. И мне не лень это решение найти.
Простой пример. Есть некая подсистема, которая разрабатывалась давно. На момент разработки скорость ее работы всех устраивала (и многое там писало именно "как проще", плюс возможности инструментария тогда были более ограничены). С тех пор объем данных увеличился в несколько раз (только по количеству клиентов более чем в два раза). И время работы подсистемы начало выходить за рамки отведенного для нее временного окна. Что делать? Покупать новый сервер помощнее? Я уже привел с чем мы работаем - стоимость нового железа сотни тысяч. Не рублей. Плюс время на закупку, доставку, развертывание и т.п. Все это может занять полгода.
Я за две недели провел рефакторинг подсистемы, ускорив ее в среднем в 4-5 раз (там много чего было, в т.ч. пара сопутствующих задачек, которые на много чего еще положительно повлияли за пределами данной подсистемы). За зарплату которую мне тут платят. Что стоит минимум на порядок дешевле нового сервера и существенно быстрее по времени.
По теперешним нормам такие решения, как были там, просто не пройдут ни кодревью, ни нагрузочное тестирование - требования по эффективности сейчас намного жестче. Именно ради того, чтобы реже тратить время и деньги на замену железа (да, периодически это приходится делать, но тут чем реже, тем лучше).
не влезая в разговор, просто о цифрах когда тестировал: обратный цикл, где i-- имело среднее значение в 3 и практически не определялось размерами текущего максимального слова, а средний прыжок сильно зависел от того, насколько близко к началу находится какое-то большое слово. Например для одной из книжек Жюля Верна среднее значение было 12.
есть реальная потребность в оптимизации, вот тогда настает время алгоритмов!
Как вы узнаете что "есть реальная потребность в оптимизации"? Когда на проде в период пиковой нагрузки все встает колом?
Не устану приводить пример когда в одном из банков в период пиковой нагрузки (предновогодний период когда толпы людей ломятся в магазины за покупками) такая ситуация привела к тому, что в течении нескольких часов по всей стране у миллионов клиентов были проблемы при оплате картами в магазинах.
Вам такая ситуация нужна чтобы понять необходимость оптимизации?
По-хорошему, проводят нагрузочное тестирование, находят узкие места и оптимизируют именно их.
Использование более быстрого алгоритма в 1 месте не гарантирует что система начнёт работать быстрее.
У нас все поставки проходят через нагрузочное тестирование на копии промсреды. Но оно не дает ответа на вопрос - "что будет в условиях пиковых нагрузок". И "что будет через год когда количество обрабатываемых данных возрастет на 25%".
НТ может вам показать лишние вызовы, лишнюю динамическую работу с памятью, лишние переоткрытия файлов и т.п. Но это не серебряная пуля.
Задача разработчика писать не как ему проще (о чем многие забывают), но максимально эффективно в заданные сроки. И если вы видите, что можно реализовать алгоритм, который с учетом конкретики задачи будет работать быстрее "среднеуниверсальных" - вы просто обязаны это сделать. При том, что он скорее всего будет еще и проще (т.к. там решается одна конкретная задача с конкретными граничными условиями, а не попытка реализовать нечто на все случаи жизни).
вы просто обязаны это сделать
Вот тут я с вами не согласен.
Если ваш "хороший" алгоритм быстрый, простой в поддержке, в него легко вносить изменения, и стоимость его разработки аналогичная, то - да, его стоит реализовать.
Например, я не вижу ни одной причины не использовать Memory.Split вместо string.Split в данном случае, это необходимая оптимизация.
Но в других ситуациях это не всегда так очевидно, что я и попытался показать в статье: Jump быстрый, но вносить изменения в него в разы дольше.
И стоит делать осознанный выбор между стоимостью разработки и скоростью работы алгоритма для каждой конкретной ситуации.
Если ваш "хороший" алгоритм быстрый, простой в поддержке, в него легко вносить изменения, и стоимость его разработки аналогичная, то - да, его стоит реализовать.
Ну, видимо, вам просто не приходилось работать в условиях, где скорость и эффективность (прежде всего использования CPU) всегда стоят на первом месте.
А я в таких условиях работаю уже не один десяток лет. Так что считайте это профдеформацией.
Вы сравниваете велосипед с детским кодом. Сравнение совершенно неправомерно. Здесь нет лучшего варианта. Даже обсуждать и холиварить не стоит.
Честно говоря, слабо верится, что в шарпе нет аналога StringTokenizer, как в Java, либо strTok из C. В дельфи есть токенизер, и в плюсах тоже (уже не помню).
Не может быть, чтобы в шарпе не было. Задача профессионала - не быстро слепить детский код. Не написать велосипед. А найти подходящую для решения данной задачи библиотеку.
Честно говоря, слабо верится, что в шарпе нет аналога StringTokenizer, как в Java, либо strTok из C.
Есть. Это Split, который используется в статье.
Вы сравниваете велосипед с детским кодом.
Почему детский?
Сплит напрямую создает массив строк. Токенизер никаких массивов не создает. При каждом вызове getNextToken объекта токенизера возвращается слово-токен. Его можно сравнить со словом максимумом и заменить им максимум.
"Детский" в том смысле, что берется первый попавшийся, без учета внутренней работы библиотечной функции/класса.
"Взрослый" подход, когда выбирается необходимый класс/функция, четко понимая, какие алгоритмы они реализуют и как вообще работают.
Сплит напрямую создает массив строк
А теперь представим, что проанализировать нужно, например, "Войну и мир". Или "Капитал"... И долго удивляемся - "чей-то у нас не так-то???"
В задаче на вход поступает строка, в которой нужно найти самое длинное слово. То есть, эта строка уже в памяти. Если нужно проанализировать "Войну и мир", то мы не будем считывать в память целиком, а напишем функцию, которая принимает путь к файлу.
string GetLongestWordMemory(string fileName, char[] separators)
{
IEnumerable<string> getWords(string s) => s.AsMemory().SplitAny(separators);
var maxWord = File.ReadLines(fileName).SelectMany(getWords).MaxBy(w => w.Length);
return maxWord.ToString();
}(писал в блокноте, поэтому возможны ошибки).
Сплит напрямую создает массив строк
Но ведь про это написано в статье)
И там же предложен альтернативный вариант с Memory, и он не создает строки, так же, как и озвученный вами StringTokenizer.
В чем тогда отличия? Почему один детский, а второй нет?
"Детский" в том смысле, что берется первый попавшийся, без учета внутренней работы библиотечной функции/класса.
Я вот всё учёл, всё проанализировал и взял Split. Мой код (точно такой же, как у автора) не детский?
p.s. Что бы Вы взяли?
Скорее всего, здесь будет быстрее всего работать простой потоковый проход в цикле по символам со счетчиком. Пока не наткнулись на разделитель - увеличиваем счетчик. Наткнулись - сравниваем значение счетчика с предыдущим максимальным. Больше - нашли очередной максимум. Сбрасываем счетчик и идем дальше.
Такой, с позволения сказать, "алгоритм" не будет содержать никаких лишних вызовов (которые тоже не бесплатные - не нужно разматывать и сматывать новые уровни стека) и уложится в десяток строк кода (он еще и компилятору будет прост для оптимизации).
По крайней мере от этого можно плясать.
Рекомендую прочитать мою статью, которую автор и обсуждает, ваш способ является наивным решением и может быть улучшен.
Я в курсе. Специально написал "от этого можно плясать".
Но реально понять может ли он быть улучшен можно только на нагрузочном тестировании. Поскольку много с НТ имею дел, то сталкивался с ситуациями когда наивные алгоритмы с силу своей простоты и линейности (минимум переходов, минимум ветвлений) на больших объемах данных показывают лучший результат, нежели "улучшенные" (казалось бы), но менее линейные и более сложные.
В принципе, этот алгоритм еще и легко параллелизуется - разбиваем входной текст на блоки, каждый блок обрабатываем в отдельном потоке (задании), затем из полученных результатов выбираем наилучший.
Мы обсуждаем с вами две разные проблемы:
Вы рассказываете о том, что этот код можно ускорить (с чем я абсолютно согласен)
Я же пытаюсь рассказать про реализацию бизнес-задач, где, зачастую, стоимость поддержки кода гораздо важнее скорости его работы.
Что будет с вашим супер оптимальным алгоритмом, когда изменятся требования к задаче? Вам придется его выбросить и написать новый. Новый тоже будет очень быстр, я не сомневаюсь, вот только на разработку вы потратите значительно больше времени.
И да, в каком-то случае оно будет стоить того, но далеко не всегда.
Я же пытаюсь рассказать про реализацию бизнес-задач, где, зачастую, стоимость поддержки кода гораздо важнее скорости его работы.
Точно? В наших, к примеру, бизнес-задачах на первом месте скорость, на втором эффективность использования ресурсов процессора, а потом уже все остальное.
Точно. Если вам не важны стоимость и время разработки, что же, это просто не ваш кейс, у вас всё по-другому.
Да. Я к тому и говорю, что ситуации бывают разные. У нас (mission-critical задачи) неэффективный медленный код создаст больше проблем чем решит. Следовательно, ценность его для бизнеса скорее даже не нулевая, а отрицательная.
Разработка ведется силами собственного IT-подразделения (в котором, кстати, порядка 5 000 человек, если считать все направления и системы). Т.е. за фиксированную з/п.
Общий ТТМ, если считать от выкатывания бизнес-требований (BRD) складывается из согласования архитектурного решения, разработки FSD на основе согласованного BRD, собственно разработки и тестирования (которое занимает больше времени чем разработка т.к. состоит из многих этапов - компонентное, на соответствие FSD, бизнес, на соответствие BRD, нагрузочное, интеграционное и техтест на прелайве). Все это направленно на одну цель - минимизировать вероятность проблем на проде.
Так что увеличение времени на разработку в общем ТТМ сказывается незначительно.
мысль понял. но вступает в ход описанное мной же - важен контекст задачи. и моя статья как раз об этом в том числе.
Задача профессионала - решить задачу бизнеса максимально эффективно в заданные сроки. А как он это сделает заказчика не волнует вообще. Ему главное чтобы через полгода-год не пришлось искать очередного "профессионала" (который "будет искать очередную библиотеку" или просто скажет "это невозможно потому что нет нужной библиотеки") потому что увеличилось количество данных и текущее решение перестало удовлетворять по скорости работы.
А тот самый бизнес готов вам платить большие деньги чтобы вы не использовали готовые библиотеки так как есть гипотетическая вероятность каких-то там проблем в будущем? Сколько бизнесов видел я - платить много и сразу никто не собирается особенно за абстрактные ништяки в будущем. Это касается и западных компаний, благо интернет обильно пестрит такими историями.
Бизнесу все равно что я использую. Бизнес платить за то, чтобы все работало.
Реальный факап: предновогодняя суета, все ломятся по магазинам. Нагрузка на сервера доходит до 90% (при штатной 50-60%). И тут некий модуль начинает жрать ресурсы как не в себя, тормозить сам и тормозить остальные процессы. В результате по всей стране миллионы клиентов в течении пары часов (пока сопровождение в мыле откатывает кривые патчи и налаживает WA) не может расплатиться картами банка в магазинах - "нет ответа от банка" - вылеты по таймауту.
Или вот, от сопровождения письмо:
Коллеги, сервис *** за последние 5 недель увеличил потребление процессорных ресурсов в 3 раза!!!
Он уже является 2-м по величине сервисом после *****.
В качестве альтернативы мы рассматриваем перенос запуска сервиса на резервный сервер, но там есть лаг по отставанию до 10 мин.
Заказчикам сервиса это может не понравиться :(
Так вот нам платят чтобы подобных вещей не было. Потому что "тушить" их приходится в авральном порядке. Да, это мы тоже умеем, и получать такие вот письма, конечно приятно (особенно с поименным перечислением героев), но лишний раз не хочется давать повода.
Спасибо за оперативное решение вопроса с устранением проблемы в онлайн-контроле платежей, которые генерировали для банка огромные риски и спровоцировали неприятное внимание к банку со стороны ЦБ
Очень оперативно собралась команда
Нашли нестандартное, но эффективное и быстрое решение вопроса.
Каждый этап для исправления и внедрения был пройден в полном контакте с командой, что позволило оперативно закрыть возникающие вопросы.
Для понимания - это очень высоконагруженный сервис (возможно, один из самых "плотных" по объему перерабатываемой за сутки информации). И там тоже была проблема с эффективностью, приводящая к задержкам прохождения платежей. А "внимание со стороны ЦБ" запросто может обернуться штрафами с очень многими нулями. Что отрицательно сказывается на прибыли (как, впрочем, и репутационные издержки) и очень нехорошо для бизнеса в целом.
У нас огромное количество "нефункциональных требований", связанных как раз с эффективностью. По широкому кругу вопросов. От работы с БД до использования тех или иных паттернов. Потому что скорость работы и эффективность использования ресурсов для нас стоит на первом месте (с большим отрывом) от всего остального. Скорость разработки вообще мало влияет - кратно больше времени уходит на всестороннее тестирование - компоненты, бизнес, нагрузка, интеграция, техтест на прелайве...
Ваша статья вызывает у меня ряд замечаний.
По учету затрат памяти. В C# затраты памяти конвертируются, прежде всего, в затраты времени на сборку мусора. И я не увидел, что вы не только пытаетесь их учесть,. ни явным образом - я понимаю - это непросто, особенно - на коротких методах: "естественная" (по решению GC) сборка мусора начне вносить непредсказуемость, принудительная - утопит производительность в накладных расходах - ни даже хотя бы упомянуть о них: может даже, бенчмарк их учитывает как-то сам, но об . этом упомянуть надо IMHO.
По выбору алгоритма, с которым вы сравниваете. (UPD: Да, я понял, что это - из обсуждаемой статьи, но IMHO контекст обсуждения в вашей статье шире). Вы взяли какой-то сильно оптимизированный вариант, пытающийся сэкономить количество просматриваемых символов, который, будучи оптимизированным, естественно, непонятен. Если писать алгоритм по-простому, не упарываясь преждевременной оптимизацией, то решение можно написать далеко не такое длинное и запутанное, хотя с той же, линейной по числу элементов, асимптотикой и без лишних выделений памяти. Например, так:
public string GetLongestWordMemory(string s, SearchValues<char> separators)
{
int ipos=0,maxlen=0;
string maxstr="";
do {
iposprev=ipos;
ipos=str.IndexOfAny(AnyOf,iposprev);
curlen=(ipos>=0?ipos:str.Length)-iposprev;
if(curlnen>maxlen) {
maxlen=curlen;
maxstr=str.Substring(iposprev,curlen);
}
} while(ipos++>=0);
return maxstr;
}
Достаточно компактно, почти линейно (один очевидный цикл) и вполне понятно, где модифицировать на проверку того, является ли слово годным и на сохранение нескольких слов - там, где if стоит . И да, никаих хитрых "алгоритмов" тут тоже нет.
И последнее. Сложность читать и модифицировать код - это, вообще говоря, субъективная оценка: кого чему учили. Ибо если человека не учили специально функциональному подходу (или, хотя бы, работе с множествами, на математике), то для него элементы функционального подхода будут вызывать затруднения сами по себе. Тогда как от императивного подхода таких затруднений не будет: он - пошаговый рецепт получения результата - в обыденной жизни куда чаще встречается. И это усложнение самих элементов может запросто съесть упрощение от снижения их числа.
Спасибо за критику, постараюсь ответить:
Затраты времени на сборку мусора я действительно не учитывал, не уверен, что бенчмарк такое умеет, если расскажете как - буду признателен. Косвенно их можно оценить через объем выделенной памяти, он есть в колонке Allocated.
Вот метрики предложенного вами метода (я назвал его Simple)
По производительности он что-то среднее между Split и Memory, для меня он читается хуже. Вкусовщина? возможно, но как минимум строк в нем больше) И переделать в список его будет уже и не так просто, не 2 строчки дописать.
Я бы, все же, остановился на Memory.
По выбору алгоритма: если рассматривать какой-то очень простой алгоритм, на 1 цикл, то тут и говорить не о чем: написать быстро, а в случае чего и выбросить не жалко. Моя статья именно о достаточно сложных алгоритмах.
Была у меня дилемма разработки отчёта-использовать свой алгоритм или стандартную библиотеку генератора отчётов. Свой алгоритм был основан на использовании стандартного excell и ole automation. Загрузив стандартную библиотеку отчёта, я не смог сделать отчёт, выдавалась какая то ошибка в модулях генератора отчётов, возможно требовался подбор нужной версии библиотеки. Надо было разбираться а времени как всегда было мало. Применив свой алгоритм я достаточно быстро добавил формирование его в excell их бланка-заготовки. К тому же отчёт получился редактируемым
, что и было нужно. Теперь всегда использую такую технологию генерации отчётов. Можно формировать отчёты любой сложности, в том числе и с переменным количеством строк, используя вложенные циклы запросов к бд и ole управление Excel используя готовые бланки. Не очень сложно. Не используешь зависимости от дополнительных библиотек генератора отчётов, код довольно прост для рефакторинга.
Я не нашёл у `ReadOnlyMemory` метода SplitAny с одним параметром, похоже вы его сами написали?
Всё ещё в поисках алгоритмического дзена