С одной стороны, да, это выбор алгоритма. Среди множества можно быстро найти если не оптимальный, то набор лучших и дальше работать с ними.
С другой, это общее понимание подхода к программированию. Если понимать, что O(n^2) масштабируется плохо, и понимать что два вложенных for — это, как правило, как раз такой случай, то программисты, может быть, два раза подумают, прежде чем пихать всюду «for i for j».
Все эти деревья, связные списки и прочие хитрые придумки программистов сложно объяснить и понять без понимания Big-O. А начать ими пользоваться не только потому что «так надо»?
Иногда нахожу мнение, что Big-O это такая волшебная палочка: сверься с ней — и будешь счастлив. А иногда — что это бесполезная фигня с лекций олдскульщиков. На самом деле, эта нотация обладает главным полезным свойством — она простая, но позволяет моментально делать выводы о том или ином подходе, не вдаваясь в детали.
В данном случае реализация алгоритма влияет на пресловутую константу в О-нотации.
Первое, О-нотация исключает константы.
Второе, без констант два алгоритма одного класса будут одинаковы в Big-O, и простое сопоставление ни к чему не приведёт.
До одной буквы сокращают, когда из контекста очевидно, что за элемент мы используем.
Например, у нас есть список products, productsArray, productsList и т.п. Соответственно, один элемент этого списка — product, сокращаем до первой буквы p. Как-то так
Но я не могу придумать ни одной причины, почему список ячеек нужно сокращать до «ё». А когда идёт что-то типа «ё => ё.foo()» я читаю это как «ё моё».
Да, не несут. Именно поэтому так тоже не стоит писать. Бессмысленные названия переменных — это плохо. Для того, чтобы понять, что такое j придётся читать всю строку и осмысливать каждый метод.
Похоже, пишут несколько человек, которые друг с другом не общаются. Получается интересный диалог:
Раз:
> получил бы хомячок пару минусов в карму за попытку протащить политоту — в следующий раз подумал бы, стоит ли открывать рот
> В самом деле, как можно считать людей разумными, когда все, на что хватает их мозжечка в ответ на неприятную порцию информации — попытаться заткнуть рот собеседнику?
Два:
> за любое мнение, отличное от мнения партии, человека тут же сливают.
> минусите посты и сливайте карму оголтелым хомячкам.
Три:
> Мне-то на карму плевать с высокой колокольни
> Хабра — на моей памяти единственный ресурс, на котором приятные каменты плюсуют, а за неприятные — минусят сразу в карму.
> Мне пламенные хомячки карму уже слили
Четыре:
> Вас разве в детстве не учили, что переходить на личности в дискуссии — дурной тон, и в ответку вам может прилететь в таком же стиле?
>натолкать полну жопу огурцов хомячкам
>Большой ум видно издалека, лол.
>если вас что-то не устраивает в моих каментах или даже пригорело — не держите, просто сглотните.
Забавно, что человек, у которого почти в каждом комментарии политика и выгораживание власти пишет, что этот ресурс — пропагандистский.
Забавно, что в статье, которая про РВСН и диск (https://geektimes.ru/post/279026/) про откатчиков всего два упоминания: про западных и в вашем комментарии. А насчёт флешки автор всё объяснил: https://geektimes.ru/post/279026/#comment_9471332. Да и, чёрт возьми, вы лжёте, нет там никаких воплей толп хомячков.
Забавно, что человек, которому так не нравится ресурс аж с 2012, но сокрушается о том, как тут всё плохо, некому писать, аудитория ушла, продолжает читать и комментировать.
Мы используем рейтинг Эло для подсчёта индивидуальных рейтингов игроков в реальном футболе (который бегать-мяч-поле-команда). Используем модификацию для футбола https://ru.wikipedia.org/wiki/Футбольный_рейтинг_Эло. В ней учитывается разница мячей, так что игра идёт не только за победу, но и буквально за каждый мяч.
Ещё ярче была вспышка 1006 года https://ru.wikipedia.org/wiki/SN_1006
>По словам китайского астронома, звезда светила столь ярко, что ночью были хорошо различимы предметы. Некоторые источники говорят, что днём от её света падала тень.
> Ничто не мешает существовать алгоритму с O(n), на каждое n которого на практике тратиться секунда, имея в то же время аналог с O(n^2), где на каждое n тратится миллисекунда.
Да, не мешает. Пусть n равен миллиону. Первый выполнил за 11 дней, второй — за более чем 31 год. Если у нас задача только для ограниченных n, мы вернулись к эмпирическому правилу измерений. Собственно, и ваши «секунда» и «миллисекунда» — это тоже результат измерений, а не приближения уровня Big-O. Не стоит путать эти вещи, как сделал автор.
> Для начала стоит еще взглянуть на сложность по памяти, а то так недалеко и сортировку подсчетом везде брать.
Сомневаюсь, что сортировку со временем O(n^2) стоит использовать везде. Сложность по памяти, конечно, тоже стоит учитывать.
Если быть ещё точнее, то Big-O описывает классы производительности алгоритмов при достаточно больших n. Именно эти классы и есть ориентир на то, какой алгоритм будет лучше. Алгоритм класса O(n^2) будет настолько хуже алгоритма O(n), что их нет смысла даже сравнивать, выбирайте сразу O(n).
А вот какой из двух разных алгоритмов одного класса (!) будет лучше — да, он не говорит. Там уже есть смысл упражняться в оптимизациях и сравнениях (чем и занимается автор статьи), но это уже вопросы куда более мелкие.
> В нашем случае вставка происходит в 5 раз чаще, чем проход, так что, кажется, вывод очевиден. Пока n достаточно большой, связный список должен в целом быть эффективнее.
Судя по всему, автор не понимает Big-O. Вне зависимости от того, на какое константное число раз вставок будет больше, чем проходов, O(F(x)) не изменится.
т.е. мы имеем для массива вставку и проход = O(n) + 5O(n) = O(n)
для связного списка O(n) + 5O(1) = O(n)
Делаем графики, они действительно растут примерно одинаково, но это почему-то:
> Неожиданные для многих результаты.
> Чтобы производительность стала хуже, отношение вставок к проходам должно измениться, а не только размер коллекции.
Если делать ТОЛЬКО вставки, то связный список будет СУЩЕСТВЕННО лучше, только об этом говорит Big-O. Он не говорит ни о конкретной реализации, ни о том, кто из двух O(n) быстрее. Ему, если хотите, всё равно. Для Big-O разница в 2 раза — это не «неплохой отрыв», это пшик.
Для реальных применений, конечно, разница даже в миллисекунду может иметь значение. Но тут единственное правило — измеряйте. Big-O даёт отличный старт для поиска оптимального решения и оно не «подводит», как написано в заголовке (или, как у оригинала, «обманывает»).
Больше меня порадовало, что после этого примера идёт фраза:
«Этот пример не очень аккуратный и продуманный, зато полностью передает то, как из концепции ООП вытекает всё то, что так требуют на собеседованиях. Именно это понимание и позволяет следовать SOLID принципам».
Хотя пример нарушает принцип единственной обязанности (SRP, который в SOLID первый, т.е. S).
Из всего, что я нашёл о PLA можно сделать вывод, что в обычных условиях он вообще не разлагается, ему нужны специальные условия и много времени (промышленный компост и несколько месяцев).
Вот, например, сравниваются два образца из PLA: http://www.waters.to/blog/is-pla-really-biodegradable/ Тот, который просто «лежал на полке» совершенно не изменился.
Это сложно назвать «прекрасно разложившимся» пластиком.
Потому что биоразложимый пластик — это, скажем так, недоказанный маркетинговый ход. Более того, в проведённом недавно исследовании было установлено, что биоразложимый пластик ничем не отличается от обычного, кроме названия: http://pubs.acs.org/stoken/presspac/presspac/full/10.1021/es504258u
С одной стороны, да, это выбор алгоритма. Среди множества можно быстро найти если не оптимальный, то набор лучших и дальше работать с ними.
С другой, это общее понимание подхода к программированию. Если понимать, что O(n^2) масштабируется плохо, и понимать что два вложенных for — это, как правило, как раз такой случай, то программисты, может быть, два раза подумают, прежде чем пихать всюду «for i for j».
Все эти деревья, связные списки и прочие хитрые придумки программистов сложно объяснить и понять без понимания Big-O. А начать ими пользоваться не только потому что «так надо»?
Иногда нахожу мнение, что Big-O это такая волшебная палочка: сверься с ней — и будешь счастлив. А иногда — что это бесполезная фигня с лекций олдскульщиков. На самом деле, эта нотация обладает главным полезным свойством — она простая, но позволяет моментально делать выводы о том или ином подходе, не вдаваясь в детали.
Первое, О-нотация исключает константы.
Второе, без констант два алгоритма одного класса будут одинаковы в Big-O, и простое сопоставление ни к чему не приведёт.
Нет, можно. Да, в общем случае, но вполне себе можно.
Другой вопрос — про ограниченный набор данных, специфические задачи и прочую конкретику. Но это уже не просто «один алгоритм эффективнее другого».
До одной буквы сокращают, когда из контекста очевидно, что за элемент мы используем.
Например, у нас есть список products, productsArray, productsList и т.п. Соответственно, один элемент этого списка — product, сокращаем до первой буквы p. Как-то так
Но я не могу придумать ни одной причины, почему список ячеек нужно сокращать до «ё». А когда идёт что-то типа «ё => ё.foo()» я читаю это как «ё моё».
ЕСЛИ понятно, что это за переменная. Переменная «ё» или «ъ» не даёт никакого понятия об этом.
То есть
выглядит понятно, а
уже не очень.
Раз:
> получил бы хомячок пару минусов в карму за попытку протащить политоту — в следующий раз подумал бы, стоит ли открывать рот
> В самом деле, как можно считать людей разумными, когда все, на что хватает их мозжечка в ответ на неприятную порцию информации — попытаться заткнуть рот собеседнику?
Два:
> за любое мнение, отличное от мнения партии, человека тут же сливают.
> минусите посты и сливайте карму оголтелым хомячкам.
Три:
> Мне-то на карму плевать с высокой колокольни
> Хабра — на моей памяти единственный ресурс, на котором приятные каменты плюсуют, а за неприятные — минусят сразу в карму.
> Мне пламенные хомячки карму уже слили
Четыре:
> Вас разве в детстве не учили, что переходить на личности в дискуссии — дурной тон, и в ответку вам может прилететь в таком же стиле?
>натолкать полну жопу огурцов хомячкам
>Большой ум видно издалека, лол.
>если вас что-то не устраивает в моих каментах или даже пригорело — не держите, просто сглотните.
Дурной тон, месье, ну как же так?
Забавно, что человек, у которого почти в каждом комментарии политика и выгораживание власти пишет, что этот ресурс — пропагандистский.
Забавно, что в статье, которая про РВСН и диск (https://geektimes.ru/post/279026/) про откатчиков всего два упоминания: про западных и в вашем комментарии. А насчёт флешки автор всё объяснил: https://geektimes.ru/post/279026/#comment_9471332. Да и, чёрт возьми, вы лжёте, нет там никаких воплей толп хомячков.
Забавно, что человек, которому так не нравится ресурс аж с 2012, но сокрушается о том, как тут всё плохо, некому писать, аудитория ушла, продолжает читать и комментировать.
>По словам китайского астронома, звезда светила столь ярко, что ночью были хорошо различимы предметы. Некоторые источники говорят, что днём от её света падала тень.
Да, не мешает. Пусть n равен миллиону. Первый выполнил за 11 дней, второй — за более чем 31 год. Если у нас задача только для ограниченных n, мы вернулись к эмпирическому правилу измерений. Собственно, и ваши «секунда» и «миллисекунда» — это тоже результат измерений, а не приближения уровня Big-O. Не стоит путать эти вещи, как сделал автор.
> Для начала стоит еще взглянуть на сложность по памяти, а то так недалеко и сортировку подсчетом везде брать.
Сомневаюсь, что сортировку со временем O(n^2) стоит использовать везде. Сложность по памяти, конечно, тоже стоит учитывать.
А вот какой из двух разных алгоритмов одного класса (!) будет лучше — да, он не говорит. Там уже есть смысл упражняться в оптимизациях и сравнениях (чем и занимается автор статьи), но это уже вопросы куда более мелкие.
Судя по всему, автор не понимает Big-O. Вне зависимости от того, на какое константное число раз вставок будет больше, чем проходов, O(F(x)) не изменится.
т.е. мы имеем для массива вставку и проход = O(n) + 5O(n) = O(n)
для связного списка O(n) + 5O(1) = O(n)
Делаем графики, они действительно растут примерно одинаково, но это почему-то:
> Неожиданные для многих результаты.
> Чтобы производительность стала хуже, отношение вставок к проходам должно измениться, а не только размер коллекции.
Если делать ТОЛЬКО вставки, то связный список будет СУЩЕСТВЕННО лучше, только об этом говорит Big-O. Он не говорит ни о конкретной реализации, ни о том, кто из двух O(n) быстрее. Ему, если хотите, всё равно. Для Big-O разница в 2 раза — это не «неплохой отрыв», это пшик.
Для реальных применений, конечно, разница даже в миллисекунду может иметь значение. Но тут единственное правило — измеряйте. Big-O даёт отличный старт для поиска оптимального решения и оно не «подводит», как написано в заголовке (или, как у оригинала, «обманывает»).
«Этот пример не очень аккуратный и продуманный, зато полностью передает то, как из концепции ООП вытекает всё то, что так требуют на собеседованиях. Именно это понимание и позволяет следовать SOLID принципам».
Хотя пример нарушает принцип единственной обязанности (SRP, который в SOLID первый, т.е. S).
Вот, например, сравниваются два образца из PLA: http://www.waters.to/blog/is-pla-really-biodegradable/ Тот, который просто «лежал на полке» совершенно не изменился.
Это сложно назвать «прекрасно разложившимся» пластиком.