Всем известно, что преждевременная оптимизация — это плохо и надо себя одёргивать когда, возникает желание пооптимизировать не вовремя. Однако на практике чаще бывает ситуация когда естественное (и, возможно, интуитивно правильное) желание пооптимизировать подавляется по принципу «если вообще не оптимизировать — это не будет преждевременно». Либо так:



На мой взгляд, подобные ситуации возникают потому, что границы понятия «преждевременности» весьма нечёткие и интуитивные, как будто это что-то эмпирическое и неуловимое вроде сочности хруста французской булки.

Хотя в принципе довольно странно оперировать какими-то эмпирическими понятиями по отношению к архитектуре программ, алгоритмам и их оптимизации — поскольку это вполне измеримые вещи. А значит — можно достаточно просто измерить своевременность оптимизации. Об этом и поговорим.

Что такое оптимизация?


Оптимизация простыми словами — это приведение программы от состояния «не устраивает» до состояния «устраивает» по параметрам производительности (время выполнения, потребление ресурсов, пропускная способность). Т.е. мы знаем, какие показатели нас устраивают, и когда мы видим, что программа до них не дотягивает — пора её оптимизировать.

Что такое преждевременная оптимизация?


В тех случаях, когда мы думаем, что попадаем в состояние «не устраивает», а на самом деле всё «устраивает» — мы оптимизируем преждевременно.

Что такое своевременная оптимизация?


Мы знаем, что программа нас уже/вот-вот/будет «не устраивать» — и принимаем меры по исправлению ситуации.

В идеальном мире мы создаём программу, удовлетворяющую требованиям, выпускаем её на волю — и там нас всё сразу «устраивает». Как случается в реальном мире чаще всего, мы все прекрасно знаем.

К счастью, чтобы понять, своевременно или преждевременно мы оптимизируем, нужно совершить одни и те же действия и для этого обычно достаточно листка бумаги.

Измеримая своевременность


В общем и целом, само по себе измерение своевременности/преждевременности требует довольно простых действий:

  1. Взять требования по производительности
  2. Посчитать, укладывается ли программа в эти требования
  3. Если укладывается — жить счастливо; в противном случае — оптимизировать программу

Поскольку самым распространённым требованием является время отклика, пропускная способность сводится к нему же, а потребление ресурсов отдельная и большая тема сконцентрируемся на первом.

Итак, у нас есть требуемое время выполнения программы — ТВ и требуемое кол-во обрабатываемых данных за проход — ТД.

Мы ещё только проектируем или разрабатываем программу, и нас не покидает ощущение, что что-то идёт не оптимально и возникает боязнь преждевременной оптимизации. Для измерения нашего ощущения и предотвращения развития фобии нужно выполнить следующие действия:

  1. Определить временную сложность спроектированного/разработанного алгоритма O(n), учитывая константы. 3*n так 3*n, n*logn + n и т.п. Чем точнее — тем лучше.
  2. Получить кол-во выполняемых операций за проход — КО путём подстановки ТД в функцию, описывающую временную сложность.
  3. Посчитать среднее допустимое время обработки одного элемента — СВЭ входного массива (подразумеваем верхнеуровневую сущность, один документ, одного пользователя) на основе TB. Т.е.
    СВЭ = TB / KO
  4. Далее мы убеждаемся что фактическое время обработки одного элемента <= среднего допустимого времени обработки одного элемента, при необходимости повторяя шаги 1 и 2 для программ/алгоритмов находящихся выше по стэку.

Разберём простой пример


Допустим, что нам нужно написать программу, которая должна обработать 100 записей и уложиться в 2 секунды. В ходе разработки мы придумали некий алгоритм, временная сложность которого O(n^2).

В таком случае у нас есть 2/100^2=2*10^-4 секунд (0,2 миллисекунд или 200 микросекунд) в среднем для обработки каждой записи. Этого хватит для выполнения простых действий (арифметика и обращения к памяти занимают десятки или сотни наносекунд, если, например, судить по этой инфографике), но какие бы то ни было сетевые взаимодействия уже становятся недоступны.

Т.е. если мы пишем сортировку массива чисел под такие требования — нас «устраивает», а если нам нужно отправить 100 запросов SOAP — нас «не устраивает» и пора что-то придумывать.

Заключение


В общем-то это всё, данный подход легко масштабируем и позволяет легко оценить верхнюю границу своевременности, избавляет от чувства неопределённости и повышает осмысленность производимых программ. А самое главное — делает ваших пользователей и менеджеров счастливыми, поскольку в продакшене меньше горит.

Естественно, этого подхода недостаточно для вывода в промышленную эксплуатацию — поэтому проконсультируйтесь со специалистом прежде, чем отказываться от нагрузочных испытаний.

Спасибо за внимание!
Поделиться с друзьями
-->

Комментарии (65)


  1. acmnu
    14.03.2017 12:59
    +6

    Где-то я уже писал, что есть определенное не понимание, когда нормальный инженерный подход начинают называть преждевременной оптимизацией. Подумать над кодом и его маштабированием заранее не является примером преждевременной оптимизации. Особенно если код после этого не усложняется ибо нет ничего хуже "неоптимизированного" написанного за пять минут кода, который на самом деле является просто примером применения парадигмы "фигаг фигаг и в продакшен".


    Короче говоря уж очень часто запретом на оптимизацию прикрывают собственную некомпетентность.


    1. VolCh
      14.03.2017 13:17
      +1

      нет ничего хуже "неоптимизированного" написанного за пять минут кода

      Если этот код приносит или экономит деньги, то с точки зрения бизнеса лучше сначала в продакшен, а потом думать над оптимизациями. Вот сейчас сижу и думаю, насколько повысится производительность от смены Rest-like на GraphQL, сколько времени это займёт, а деньги бизнесу от Rest уже идут.


      1. acmnu
        14.03.2017 14:28

        Если этот код приносит деньги, то его действительно выгодно быстро вкинуть в продакшен, но потом, немедленно начать разбираться с тем техническим долгом, который с ним связан. Иначе, спустя годы, будет очень дорого его пытаться оптимизировать.


        Пример с GraphQL не вполне отражает тот случай о котором я говорю. Сменить один API на другой может быть очень сложным и дорогим удовольствием.


        Я скорее о очевидных, мешающих производительности и маштабируемости мелочах: например хранить картинки в SQL базе, а не на файловой системе или S3, или его подобии, использовать базу данных, но хранить настройки в конфиг файле (а потом применять pupet, для обновления этого конфига :D), хранить одну и ту же информацию (настройку) в трех четырех разных конфигах, использовать JQuery ради одной мелкой фичи, раздражая пользователя долгой загрузкой, не делать индексы на таблице "ведь она никогда не вырастет!" и т.д. Такие мелкие "оптимизации", если их не провести перерастают в огромную проблему, поэтому их надо решать как можно быстрее. Как только макет доказал свою работоспособность от этих проблем надо избавляться, а не ждать когда это станет заметно.


        Как мне кажется точный список этих инженерных особенностей приходит только с опытом. А умение заранее увидеть в коде узкие места является очень ценным скилом, который позволяет экономить огромные суммы денег.


        1. mayorovp
          14.03.2017 14:36
          +2

          Кстати, а что не так с хранением картинок в SQL базе?


          1. acmnu
            14.03.2017 14:51

            Очень плохо масштабируется: большой объем, зачастую низкий рейт использования, рост времени бэкапа и восстановления из него. Дело в том, что базу зачастую нельзя восстановить куском, она либо целая и работает, либо не работает вся. А главное в этом нет смысла, ибо задачи выборки картинки по её содержимому обычно не стоит (в отличии от метаинформации, которую стоит хранить в базе). Если картинка потом отдается на веб, то её лучше сразу хранить в неком пригодном для запроса из браузера виде, например в CDN сети.


            https://habrahabr.ru/company/ruvds/blog/318048/


            1. mayorovp
              14.03.2017 15:02
              +3

              Но с другой стороны, храня картинку в базе, мы сразу же получаем:


              1. Транзакционность и согласованность с другими данными! Убирается сразу же целый пласт проблем.


              2. Бэкапы. Софт для инкрементальных бэкапов файлов надо еще отдельно найти, (купить), поставить и настроить. Для СУБД бэкапы настраиваются более очевидным способом.


              3. Разграничение доступа. К конфиденциальному файлу на CDN не так-то и просто ограничить доступ, самое простое решение — генерировать криптостойкое имя файла и закрывать его от индексирования поисковиками, и все равно специалисты по безопасности будут над таким решением смеяться. Более сложные решения завязаны на конкретные CDN...


                Картинка, лежащая в БД, отдается сервером приложений — и там-то авторизацию прикрутить не проблема.



              1. acmnu
                14.03.2017 16:40

                Да, такие проблемы есть, но тут надо решать: сложнее писать или сложнее эксплуатировать. Я, как админ, даже термин специальный придумал: "написано программистами", т.е. невозможно экслуатировать легко, без проблем и за недорого.


                1. mayorovp
                  14.03.2017 16:46
                  +1

                  Вы забываете, что время, сэкономленное на решении всех этих проблем, может быть направлено на разные вещи. В том числе на упрощение эксплуатации.


                  1. acmnu
                    14.03.2017 16:52
                    -1

                    Миф о высокой стоимости времени разработчика очень раздут. Оборудование обеспечивающее действительно большую производительность стоит очень дорого.


                    1. mayorovp
                      14.03.2017 16:55

                      Не дороже чем время.


                      1. acmnu
                        14.03.2017 17:02
                        -1

                        Миллион баксов?


                        1. alexeykuzmin0
                          15.03.2017 16:14
                          +1

                          Я так понимаю, для западной компании, $1mln — это где-то 3-5 человеко-лет оплаты труда программиста. Так что если разработка занимает больше — лучше купить оборудование.


              1. kotomyava
                14.03.2017 17:52
                +1

                2. У вас есть решение для инкрементального бекапа какой-либо базы проще, чем какой-нибудь rsnapshot? Например? Или вы решили сравнить создание полной копии базы с созданием инкриментальной копии файловой системы?

                3. Как связаны CDN, конфеденциальные файлы, и хранение файлов в базе? Три разных вещи в одном странном предложении.

                По последнему, вот вам куда более разумное решение:
                Картинка лежащая в файловой системе отдаётся веб сервером, с помощью x-accel-redirect какого-нибудь, после авторизации, или ещё чего-либо обрабатываемого приложением.
                Быстро, и масштабируется куда проще чем БД для хранения картинок.


                1. mayorovp
                  14.03.2017 18:07

                  2. Про rsnapshot не слышал. У MS SQL Server есть штатный механизм бэкапа.

                  3. Я же писал. Из базы файл достается сервером приложений и доступ к нему проверяется не сложнее чем к любой другой странице.

                  Файлы отдаются веб-сервером, который более ограничен в вопросах авторизации.

                  Про CDN я писал потому что выше мне его для файлов советовали. И так с авторизацией еще сложнее.

                  Не спорю, все эти проблемы — решаемые. Но на их решение требуется время, которого всегда не хватает.


                  1. VolCh
                    14.03.2017 18:26

                    Файл так же может доставаться сервером приложений с диска и доступ к нему проверяется не сложнее чем к любой другой странице. Кстати ещё один плюс для хранения картинок в памяти — файл может легко отдаваться потоком прямо клиенту, без предварительного чтения всего в память, про СУБД же про такие механизмы не слышал, чтобы конкретное поле запроса отдавалось потоком. А это могут быть гигабайты от одного показа странички с десятком-другим картинок по 100 метров. Их сначала надо выбрать в память СУБД, потом передать в память апп-сервера. И даже если СУБД как-то оптимизирует процесс отдачи блобов, то вряд ли легко получится стримить их на веб-сервер через апп-сервер.


                    1. lair
                      14.03.2017 18:46

                      про СУБД же про такие механизмы не слышал, чтобы конкретное поле запроса отдавалось потоком

                      MS SQL — FILESTREAM.


                      1. VolCh
                        14.03.2017 21:32

                        Не очень хорошо знаю современную продукцию этой фирмы, но разве это не о способе хранения блобов? Разве обычным селектом не блоб будет отдаваться, всё равно?


                        1. mayorovp
                          14.03.2017 21:35

                          Обычный SELECT отдаст блоб. Но если в запросе использовать функцию PathName — она вернет сетевой путь к файлу.


                          1. VolCh
                            14.03.2017 21:58

                            Интересный вариант, совмещающий транзакционную целостность(совмещающий?) и файловый доступ к блобам. По сути у меня похожая схема по умолчанию, просто и записывается, не блоб, а путь к файлу. Естественно, целостность своими силами обеспечиваю, особо не утруждаясь.


                        1. lair
                          14.03.2017 22:57

                          Обычным селектом отдастся блоб, но есть несколько вариантов получить напрямую поток.


                    1. mayorovp
                      14.03.2017 18:55

                      Я настолько часто встречал совет "да храни ты все в файлах и раздавай напрямую веб-сервером" — что и забыл что файлы можно считывать сервером приложений :) Да, признаю, такой "переходный" вариант имеет право на жизнь.


                      Тем не менее, вы согласны с тем, что хранение картинок в файлах — это именно оптимизация, и она может оказаться преждевременной (если, к примеру, аудитория веб-приложения — 10 однопальцевых операторов)?


                      1. VolCh
                        14.03.2017 21:54

                        Не знаю, что тут считать оптимизацией, а, главное, оптимизацией чего :), особенно если приходят на входе не просто картинки, а уже записанные на ФС файлы.


                        Вы недооцениваете операторов, особенно однопальцевых :) Терабайт за год могут забить не напрягаясь.


          1. VolCh
            14.03.2017 14:53
            -1

            Очевидное — база раздувается, усложняется её обслуживание (те же бэкапы). Особенно заметно, если под базу ради быстродействия выделяются дорогие быстрые диски — разница по цене между, например, сотней гигов и терабайтов сильно заметной может быть. А к хранению картинок обычно требования не такие жёсткие, как к, например, финансовому балансу пользователя.


            1. mayorovp
              14.03.2017 15:05
              +2

              Картинкой может быть и скан квитанции. С тем самым финансовым балансом пользователя...


              1. VolCh
                14.03.2017 15:44

                Если есть жёсткие требования к согласованности картинок и остальных данных, то вариант с хранением их в базе приходится рассматривать, увы. Но в целом, обычно, по моему опыту, складывание их в базу по умолчанию приводит к бОльшим проблемам со временем, чем в ФС. Вернее не конкретно в ФС, а в отдельное от более важных данных хранилище. Одна база с основными данными и другая с картинками, возможно на разных серверах — нормальный вариант, если накладные расходы устраивают.


              1. acmnu
                14.03.2017 16:50
                +2

                Никакой проблемы со сканом нет. Важен факт его наличия, который можно отметить в базе, а на картинку можно сказать, что временная проблема, щас все будет, админу уже прописали люлей.


                Как раз сила здесь в отсутствии согласованности. Сила базы (не говоря даже о sql) в том, что она хранит все согласовано, поэтому она так хороша для финансовой информации (приход, расход, движения денег по счетам). Я понимаю, что можно вообразить ситуацию, когда нужны согласованные действия с картинкой, но я такого не видел, а вот запихивания не очень важных, вспомогательных вещей (типа квитанций) в базу, это сколько угодно.


                Мне пришлось эксплуатировать базу данных размером 10T, в которой на картинки проходилось 99%. Это был ад. И очень, просто ну очень дорогой ад. Чтобы уложится в норматив по бэкапу и восстановлени туда надо был подпихивать очень дорогой сторадж (одной почкой разработчика тут бы не обошлось).


                1. mayorovp
                  14.03.2017 16:54

                  Пожалуйста, прочитайте мой комментарий еще раз. Проблема скана квитанции — вовсе не в согласованности...


                  1. acmnu
                    14.03.2017 17:03

                    Ну значит я это совершенно не понял.


                    1. mayorovp
                      14.03.2017 17:06

                      Я отвечал на вот это:


                      А к хранению картинок обычно требования не такие жёсткие, как к, например, финансовому балансу пользователя.

                      Скан квитанции — это картинка, которая содержит конфиденциальные данные пользователя. В частности, баланс его лицевого счета на определенную дату.


                      Соответственно, и требования к защите тут "финансовые", а не "картиночные". В частности, заливка скана квитанции на CDN почти наверняка нарушит уйму требований регулирующих органов.


                      1. acmnu
                        14.03.2017 17:12

                        Ну CDN, конечно не для скана квитанции. Я даже не вижу смысла это обсуждать. Да acl поддерживающая прослойка нужна, куда же без неё, но это очень простой к реализации вопрос.


                        1. mayorovp
                          14.03.2017 17:22

                          Это вопрос, который надо решать. И который требует времени. А время — невосполнимый ресурс, который нельзя купить.


                      1. VolCh
                        14.03.2017 17:56
                        +1

                        Я не конфиденциальность данных имел в виду, а именно транзакционную целостность. Скажем, что если оплата на 1000 рублей есть в базе, то обязательно должен быть скан квитанции на оплату. Конфиденциальность хранения картинок в базе не требует, даже если требуется сильная авторизация. Причём сама авторизация будет одной и той же в обоих случаях, что в базе, что ещё где хранить.


    1. bashnesnos
      14.03.2017 13:44
      +1

      Согласен, но всё же стараюсь исходить из презумпции невиновности компетентности в первую очередь, поскольку программисты это в первую очередь люди и уже потом инженеры.

      Некомпетентность компенсируются мощью поисковых машин при наличии сомнений и желания, чаще этим запретом манипулируют менеджеры, а не инженеры.


  1. varnav
    14.03.2017 13:36
    -1

    Исследования показывают что для веб-приложений, ориентированных на внешних пользователей, нет такого показателя как «работает достаточно быстро» — любое увеличение быстродействия делает пользователя более довольным, а значит хорошо для бизнеса.

    Как быть тогда?


    1. mayorovp
      14.03.2017 13:58

      Странные какие-то исследования...


      1. varnav
        14.03.2017 14:05

        Разумеется речь идёт об оптимизациях, которые пользователь может заметить.

        image

        https://blog.kissmetrics.com/speed-is-a-killer/


        1. mayorovp
          14.03.2017 14:27

          Тем не менее, порог "работает достаточно быстро" — есть.


          Так, мировой рекорд скорости печати — 750 знаков в минуту — означает что задержка отклика в 80 миллисекунд даже при самом быстром наборе текста будет означать запаздывание всего в 1 символ. Половина от этого значения, 40 миллисекунд, заметна не будет уже совсем. Другие же виды деятельности налагают на время отклика еще меньше ограничений.


          1. varnav
            14.03.2017 14:42

            Разумеется речь идёт об оптимизациях, которые пользователь может заметить.


            1. mayorovp
              14.03.2017 14:44

              Изначально вы писали иное:


              Исследования показывают что для веб-приложений, ориентированных на внешних пользователей, нет такого показателя как «работает достаточно быстро» — любое увеличение быстродействия делает пользователя более довольным, а значит хорошо для бизнеса.


              1. varnav
                14.03.2017 15:06

                разумеется тут не имеется в виду уменьшение отклика с 900 ms до 899 ms


                1. VolCh
                  14.03.2017 15:46
                  +2

                  Вот это уменьшение как раз может сделать пользователя более довольным, поскольку задержку он в принципе заметит, а какая миллисекунда станет последней каплей никто не знает.


    1. bashnesnos
      14.03.2017 13:59

      Это больше вопрос совмещения желания и возможностей — т.е. определения требований к системе и оценки стоимости их реализации. Вопрос смежный, но мне кажется отдельный.

      Несколько штрихов:
      У внешнего пользователя, т.е. у человека есть границы восприятия, быстрее которых нет смысла оптимизировать (например https://www.nngroup.com/articles/response-times-3-important-limits/). Границы меняются с адаптацией человека к технологиями и эволюцией человека, но всё же они есть — т.е. не каждое увеличение быстродействия будет замечено.

      У бизнеса ориентированного на пользователя тоже нет смысла улучшать бесконечно, потому что у продукта который он предоставляет пользователю есть 3 состояния качества — лучше чем у конкурента, хуже чем у конкурента и так же как у конкурента. Если уже лучше — то зачем тратить деньги кроме пиара, если хуже — то вопросов нет, если так же, но есть другие преимущества — то тоже особо нет смысла.

      И конечно же у каждого бизнеса разные возможности, поскольку улучшение от 15 до 10 секунд стоит одних денег, от 10 до 3 секунд других денег и от 3 до 1 секунд — третьих денег.


      1. varnav
        14.03.2017 14:03

        У бизнеса ориентированного на пользователя тоже нет смысла улучшать бесконечно, потому что у продукта который он предоставляет пользователю есть 3 состояния качества — лучше чем у конкурента, хуже чем у конкурента и так же как у конкурента

        Есть ещё одно, и очень важное — настолько хорош, что им начинают пользоваться даже те, кто раньше не пользовались.


        1. bashnesnos
          14.03.2017 14:30

          Да в общем-то это то же самое «лучше чем у конкурента», просто очень хорошо распиаренное и переданное из уст в уста. Если это политика брэнда и есть бюджет — то это просто прекрасно.

          Но поскольку необходимы результаты, а не бесконечное стремление к идеалу — даже в таких условиях будут какие-то необходимые и достаточные для внедрения на прод требования по производительности, на которые надо ориентироваться.


    1. VolCh
      14.03.2017 14:19

      Оценить стоимость оптимизации (или хотя бы оценить оценку стоимости оптимизации :) и планируемое "хорошо для бизнеса". Не забыть про то, что может текущие задачи на новую функциональность и багфиксы принесут больше денег чем трата ресурсов на оптимизацию.


      Вообще, с точки зрения обычного (с ограниченными ресурсами) бизнеса есть три метрики необходимости каких-то движений, будь то открытие нового завода или замены одной сортировки на другую:


      • ресурсы, которые надо на это движение потратить
      • прибыль, которую это движение принесет (частая подметрика — срок окупаемости)
      • прибыль, которую принесут другие движения, на которые можно потратить эти ресурсы (от направления разработчиков на багфиксинг до разгона разработчиков и покупки коробки, а то и вообще закрытия бизнеса и покупки акций Теслы)


    1. Germanets
      14.03.2017 14:42

      любое увеличение быстродействия делает пользователя более довольным, а значит хорошо для бизнеса.
      — Очень уж светлый и радужный вариант, который на самом деле под вопросом, потому как «довольный пользователь» — совсем не значит «прибыльный пользователь».
      В качестве контрпримера могу назвать случай, при котором снижение быстродействия может улучшить дела бизнеса: увеличение времени отклика страниц пополнения счёта на сайте увеличило сумму разового пополнения баланса — то есть средства раньше переходили от клиента к бизнесу — получателю.
      Пример читал скорее всего на хабре, но ссылку на статью найти не могу, общая суть статьи — пытаемся увеличить скорость загрузки страниц на сайте и посмотреть — что же будет.


  1. varnav
    14.03.2017 13:52

    Кроме того, если не закладывать запас заранее — можно получить проблемы в будущем.

    Что проще и менее затратно:
    1. Выделить небольшой диск под БД.
    2. При росте БД докупить диск побольше, смигрировать БД на неё.
    или
    1. Сразу выделить диск с запасом.

    Или более жёсткий пример, но тут не про ПО:
    1. Построить сеть на 100 мегабит
    2. Когда станет не хватать, переделать под гигабит.


    1. lair
      14.03.2017 14:03
      +4

      … так вот, преждевременная оптимизация в вашем примере — это сразу прокладывать оптику вместо меди.


  1. alxt
    14.03.2017 14:14
    +5

    Для понимания, какая «преждевременная» оптимизация есть зло, какая благо- надо посмотреть лекцию Шипилёва с joker-2016 (да, доступна пока только тем, кто покупал билет, но будет вроде и публичной) — она не про java, по сути.

    Там хорошо поделены все они на

    • зелёную зону — упрощаем код, делая его лучше как с точки зрения читаемости, так и с точки зрения перформанса за счёт использования хороших алгоритмов из стандартных библиотек и т.п.
    • жёлтую зону — когда пишется понятный, но многословный код для повышения производительности
    • красную зону — грязные хаки, использование непубличного API и обход багов платформы.


    • Если оптимизация из зелёной зоны- она хороша всегда. И никогда не будет преждевременной. Убрать лишние абстракции, странные наследования, использовать оптимизированную библиотеку вместо самописного костыля (или просто заменить библиотеку от apache на аналог от google) и т.д. и т.п.

      Жёлтой- только если иначе нельзя, когда «зелёная» не помогла, а проблемы остались. Это может быть преждевременно.

      Красная- «если Вы это читаете, значит Вам этого делать нельзя». Это всегда плохо. Но редко нужно (чем чаще- тем хуже платформа).


    1. evkin
      14.03.2017 21:49

      В доступе есть презентация этого доклада — http://assets.contentful.com/oxjq45e8ilak/7K1D4OReesK0mmyM6sQKUK/6b3d90c447c9ee1de83702acea0a7d05/joker-Oct2016-perf-keynote.pdf


  1. workless
    14.03.2017 22:53
    +2

    Разберем «Разберём простой пример»

    Допустим, что нам нужно написать программу, которая должна обработать 100 записей и уложиться в 2 секунды. В ходе разработки мы придумали некий алгоритм, временная сложность которого O(n^2).

    У вас дальше неправильно, правильно примерно так:

    У вас есть 2 сек\100 записей = 2000/100 = 20 мсек в среднем на обработку одной записи.
    Но если количество записей для обработки увеличится в 2 раза, то время на обработку увеличится в 4 раза.
    Количество записей увеличится в 10 — время в 100 раз.

    Сложность говорит о росте времени работы алгоритмов при росте количества элементов, но ничего не говорит про время обработки.

    Если один элемент обрабатывается за 10 секунд — это ничего не значит.
    Но:
    Если один элемент обрабатывается за 10 секунд, и 20 элементов за 10 секунд, то это O(1)
    Если один элемент обрабатывается за 10 секунд, а 20 элементов за 200 секунд, то это O(n)
    Если один элемент обрабатывается за 10 секунд, а 20 элементов за 4000 секунд, то это O(n^2)


    1. bashnesnos
      15.03.2017 10:10

      Спасибо за комментарий, не вижу противоречия с тем, что я написал.

      Вы подтверждаете, что сложность описывает связь между количеством элементов, временем обработки одного элемента и временем обработки всех элементов. Задача, которую я рассмотриваю в этой статье — обратная. Т.е. исходя из ограничений на время обработки всех элементов, и зная количество элементов определить ограничение на время обработки одного элемента. Вы же не будете отрицать, что 4000/20^2=10?

      Сложность говорит не только о росте, поскольку время обработки алгоритма O(n) и O(n^2) всё-таки сильно отличается при одном и том же значении n — как раз по той причине, что нужно сделать выполнить больше операций над одним и тем же количеством элементов.


      1. workless
        15.03.2017 12:39
        +2

        У нас не противоречие в утверждения противоречие. У вас ошибка.
        Сложность n^2, 2 секунды и 100 элементов дает нам только время на обработку «20 мсек». Причем тут 0,2 мсек.

        Даже если сложность n!, все равно при «2 секунды и 100 элементов» у вас «20 мсек» на запись.


        1. bashnesnos
          15.03.2017 15:03

          2 секунды и 100 элементов даёт 20 миллисек на 1 элемент в среднем, но если для каждого элемента надо дополнительно обойти те же 100 элементов в случае n^2 мы получаем 0,2 мсек на одну операцию.

          Сколько будет выполнений внутреннего тела цикла в примере ниже? 100 или 10000?

          int count = 0;
          int n = 100;
          for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                      count++;
                }
          }
          


          1. workless
            15.03.2017 16:25

            Простите, но у вас в голове каша.
            Вы к сложности алгоритма притягиваете еще какие-то дополнительные обходы.

            Лучше перестану отвечать, у меня будет «бомбить и пригорать».
            А вы останетесь при своем мнении.


            1. bashnesnos
              15.03.2017 19:06

              Простите, но я вам отвечал по существу. Причём здесь каша, когда я вам привожу конкретные примеры.

              Действительно, стоит прекратить дискуссию, раз вы не готовы аргументировать свою позицию и искать точки соприкосновения.


              1. workless
                15.03.2017 21:43

                В вашем примере (комментарием выше) количество элементов 100.
                Внутренний цикл имеет отношение к сложности, а не к количеству элементов.

                Почитайте про сложность, и не додумывайте в стиле «я так думаю\мне кажется».


                1. bashnesnos
                  16.03.2017 09:36

                  Я с вами не спорю про сложность и количество элементов. Давайте отойдём от количества элементов, видимо загвоздка в этом.

                  В моём примере выше выполнений цикла 10000, и если нам нужно чтобы весь цикл выполнился за 2 секунды на одно выполнение цикла в среднем сколько получится?


                  1. workless
                    16.03.2017 10:28

                    Зачем тогда вы сами начали говорить про сложность?


                    1. bashnesnos
                      17.03.2017 11:10
                      -1

                      Раз уж мы разобрались откуда берётся 0,2 мсек вернёмся к сложности.

                      Например, википедия:

                      Временная сложность алгоритма (в худшем случае) — это функция от размера входных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера.


                      Т.е. если мы подставим в функцию временной сложности размер входных данных (в рассмотренном мной случае он известен из требований), то получим максимальное количество операций (в худшем случае). Тут сложность заканчивается. Далее, зная требуемое время выполения и кол-во операций можно посчитать требуемое время выполнения одной операции в среднем.


                      1. workless
                        17.03.2017 12:06

                        Вы вообще понимаете что хочу донести?

                        Допустим, что нам нужно написать программу, которая должна обработать 100 записей и уложиться в 2 секунды. В ходе разработки мы придумали некий алгоритм, временная сложность которого O(n^2).

                        В таком случае у нас есть 2/100^2=2*10^-4 секунд (0,2 миллисекунд или 200 микросекунд) в среднем для обработки каждой записи


                        а должно быть так

                        В таком случае у вас есть 2/100=20 миллисекунд в среднем для обработки каждой записи

                        Если у вас массив в 100 элементов и у вас O(n^2), то это не значит что вы должны обработать и учитывать время на 10.000 элементов. Это значит при изменении количества элементов (которых изначально было *100*) время будет ограничиваться сверху как квадрат отношения количества изначальных элементов.

                        Станет не 100, а 300 элементов. Алгоритм может начать укладываться в 18 секунд (2*(300\100)^2)

                        Все просто же )

                        Сложность нужна для того что могли оценить «так, вот на таком количестве скорость ок, но в определенный момент» скорость резко упадет.

                        Для примера напишите программу на c# которая будет к строке добавлять тысяч 50.000 слов.

                        что-то вроде

                        string s = "init string";
                        
                        for (int i = 0; i < 50000; i++)
                        {
                          s = s + i.ToString();
                        }
                        


                        Этот пример «плохой». Но показывает сложность конкатенации иммутабельных строк и необходимость StringBuilder-а

                        Т.е. при количестве добавляемых чисел, например, до 100 все будет ок. Но в определенный момент скорочть резко упадет. Из-за аллокации памяти под новую строку и копирование данных туда-сюда.

                        посмотрите
                        https://habrahabr.ru/post/195996/
                        https://habrahabr.ru/post/104219/
                        https://habrahabr.ru/post/188010/


                        1. bashnesnos
                          18.03.2017 14:35

                          Мы с вами благополучно прошли по кругу :-)

                          Я согласен и не спорил с вами по поводу

                          Если у вас массив в 100 элементов и у вас O(n^2), то это не значит что вы должны обработать и учитывать время на 10.000 элементов


                          Я согласен, что
                          Сложность нужна для того что могли оценить «так, вот на таком количестве скорость ок, но в определенный момент» скорость резко упадет.

                          На нём в общем-то всё и завязано в статье — т.е. на выяснении того, что на требуемом нам количестве скорость ок, или не ок.

                          Я пытался донести, что подразумеваю под «обработкой записи» наиболее практический аспект обработки записи — «элементарную операцию» (тут можно отдельно закопаться), количество которых можно рассчитать с помощью функции сложности.

                          Я намеренно упростил этот момент, и я не вижу смысла усложнять его обратно введением «элементарной операции» вместо «обработки записи».
                          Думаю стоит добавить отдельную оговорку про среднее время на обработку записи в рассматриваемом мной контексте.

                          В таком случае вопрос будет исчерпан?


                        1. bashnesnos
                          18.03.2017 14:42

                          P.S. обратите внимание по вашей ссылке https://habrahabr.ru/post/195996/ есть упоминание того, что я рассматриваю в данной статье

                          Практическая рекомендация: на соревнованиях алгоритмы часто реализуются на С++. Как только вы проанализировали сложность вашего алгоритма, так сразу можете получить и грубую оценку того, как быстро он будет работать, приняв, что в секунду выполняется 1 000 000 команд. Их количество считается из полученной вами функции асимптотической оценки, описывающей алгоритм. Например, вычисление по алгоритму с ?( n ) займёт около секунды при n = 1 000 000.


                        1. michael_vostrikov
                          18.03.2017 15:54

                          Но в определенный момент скорость резко упадет. Из-за аллокации памяти под новую строку и копирование данных туда-сюда.

                          Я вот не очень разбираюсь в сложностях, но мне почему-то кажется, что пространственная аллокация памяти с временной сложностью самого алгоритма никак не связана. А скорость не "резко упадет", а по вполне определенному закону. Который и написан в скобочках. И который показывает количество элементарных операций, которые, собственно, и занимают время.


  1. bashnesnos
    15.03.2017 10:10

    Удалил свой комментарий, поскольку ответил не в ту ветку.