Pull to refresh
7
0
Александр Семелит @bashnesnos

Программист широкого профиля

Send message
Мой коллега раскрывает основы тут www.youtube.com/watch?v=SUOtIhGjXoI, расшифровка на Хабре будет
Самое интересное :-) Просто такие статьи читают всякие CEO, это потом выливается в требования, а ожидания по срокам и стоимости не сформированы.

При внимательном изучении обнаружил «Осень 2014» и «Весна 2015». Т.е. 2-3 квартала. Это круто, конечно.
Вроде никого уже не надо убеждать, что сайт должен открываться быстро. На графиках очень не хватает данных, чего им стоило это увеличение в деньгах/разработчиках/времени.
Есть более подробное описание задачи, и систем на которых достигнуто ускорение в 10 тыс. раз?
P.S. обратите внимание по вашей ссылке https://habrahabr.ru/post/195996/ есть упоминание того, что я рассматриваю в данной статье
Практическая рекомендация: на соревнованиях алгоритмы часто реализуются на С++. Как только вы проанализировали сложность вашего алгоритма, так сразу можете получить и грубую оценку того, как быстро он будет работать, приняв, что в секунду выполняется 1 000 000 команд. Их количество считается из полученной вами функции асимптотической оценки, описывающей алгоритм. Например, вычисление по алгоритму с Θ( n ) займёт около секунды при n = 1 000 000.
Мы с вами благополучно прошли по кругу :-)

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


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

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

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

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

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

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


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

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

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

Действительно, стоит прекратить дискуссию, раз вы не готовы аргументировать свою позицию и искать точки соприкосновения.
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++;
      }
}
Спасибо за комментарий, не вижу противоречия с тем, что я написал.

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

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

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

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

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

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

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

Information

Rating
Does not participate
Location
Санкт-Петербург, Санкт-Петербург и область, Россия
Works in
Date of birth
Registered
Activity