Comments 25
А как вы узнали что это log(1024) а не 1024^2*0.000001?
В данном примере я действительно принял это на веру, потому что знаю реализацию map. Просто опытные данные совпали с моими ожиданиями и этого было достаточно.
Если же нужно убедиться, что мы все посчитали правильно, то, можно, например, модифицировать Mock-объект из статьи таким образом, что он будет отдельно учитывать информацию по каждому объекту. Тогда можно получить гораздо больше информации — минимальное, максимальное, среднее количество операций.
Если же нужно убедиться, что мы все посчитали правильно, то, можно, например, модифицировать Mock-объект из статьи таким образом, что он будет отдельно учитывать информацию по каждому объекту. Тогда можно получить гораздо больше информации — минимальное, максимальное, среднее количество операций.
А еще можно прогнать с разными размерами данных и убедиться, что зависимость NlogN лучше всего описывает полученные результаты
Да, это тоже один из возможных вариантов. Только он может оказаться гораздо сложнее из-за
Речь же идет о порядках и значение множителя C нам неизвестно, при этом может оказаться достаточно большим.
Вообщем придется заботиться о достаточно большом наборе данных, чтобы убедиться, что C нам не портит картину.
А это уже медленно и много возни.
убедиться, что зависимость NlogN лучше всего описывает полученные результаты
Речь же идет о порядках и значение множителя C нам неизвестно, при этом может оказаться достаточно большим.
Вообщем придется заботиться о достаточно большом наборе данных, чтобы убедиться, что C нам не портит картину.
А это уже медленно и много возни.
Медленно? Это же все равно не будет проводиться при каждой сборке. А потратить пару минут в ночной тест — не такая уж большая проблема.
А выяснить, какая зависимость имеет место, можно только так, разве нет?
А выяснить, какая зависимость имеет место, можно только так, разве нет?
Медленно? Это же все равно не будет проводиться при каждой сборке. А потратить пару минут в ночной тест — не такая уж большая проблема.
Пожалуй, это не самое критичное. Гораздо важнее, что разработка такого теста сама по себе сложная и трудоемкая задача.
А выяснить, какая зависимость имеет место, можно только так, разве нет?
Да, если сейчас надо разобраться почему работает медленно, как в примерах в статье.
Но если говорить это тесте, важнее не пропустить ситуацию, когда сложность алгоритма резко увеличивается, а для этого можно использовать для конкретного набора данных заранее вычисленные эталонные значения.
А почему Вы считаете именно операции, а не затраченное время, что, во-первых, выглядит логичнее, а во-вторых, широко используется в олимпиадном программировании?
Я пару раз занимался подобным, когда анализировал сложность придуманных алгоритмов (к задачам соревнованияй типа ACM ICPC и прочим), про которые сходу не было понятно, какую они имеют асимптотику.
Ваша цель — понять асимптотику, которая описывает время работы алгоритма в зависимости от размера входных данных. Фактически, вы анализируете поведение функции F(n) в зависимости от n. Совершенно непонятно, что же вы тогда смотрите на одну-единственную точку n = 1000/1024?
Нас-то интересует, как себя функция ведёт на всей числовой прямой, в частности, хорошей идеей будет посмотреть, во сколько раз увеличивается сложность, при увеличении n в полтора, два, три раза. Например, если F(2n) / F(n) будет в среднем близко к 4, то функция времени работы асимптотически, скорее всего, лежит в O(n^2). Верно даже более сильное утверждение, что она, скорее всего, будет в Theta(n^2). Поняв таким образом, какая степень n при старшем множителе асимптотики, можно уже анализировать, какой там стоит множитель рядом с ней, т. е. отличать Theta(n), Theta(n log n), Theta (n (log n) ^ 2), Theta (n sqrt(n)) и подобные, просто поделив f(n) на n в нужной степени, и проанализировав этот самый хвост аналогично.
Ваша цель — понять асимптотику, которая описывает время работы алгоритма в зависимости от размера входных данных. Фактически, вы анализируете поведение функции F(n) в зависимости от n. Совершенно непонятно, что же вы тогда смотрите на одну-единственную точку n = 1000/1024?
Нас-то интересует, как себя функция ведёт на всей числовой прямой, в частности, хорошей идеей будет посмотреть, во сколько раз увеличивается сложность, при увеличении n в полтора, два, три раза. Например, если F(2n) / F(n) будет в среднем близко к 4, то функция времени работы асимптотически, скорее всего, лежит в O(n^2). Верно даже более сильное утверждение, что она, скорее всего, будет в Theta(n^2). Поняв таким образом, какая степень n при старшем множителе асимптотики, можно уже анализировать, какой там стоит множитель рядом с ней, т. е. отличать Theta(n), Theta(n log n), Theta (n (log n) ^ 2), Theta (n sqrt(n)) и подобные, просто поделив f(n) на n в нужной степени, и проанализировав этот самый хвост аналогично.
Ваша цель — понять асимптотику, которая описывает время работы алгоритма в зависимости от размера входных данных. Фактически, вы анализируете поведение функции F(n) в зависимости от n. Совершенно непонятно, что же вы тогда смотрите на одну-единственную точку n = 1000/1024?
Цель статьи была показать, как использовать идею с Mock-объектами, для тестирования алгоритмической сложности. Суть идеи в том, что не вмешиваясь в код алгоритма и даже не имея доступа к нему, организовать подсчет операций для дальнейшего анализа. Именно поэтому в моем примере я указал одну точку — цели я своей достиг.
Нас-то интересует, как себя функция ведёт на всей числовой прямой, в частности, хорошей идеей будет посмотреть, во сколько раз увеличивается сложность, при увеличении n в полтора, два, три раза. Например, если F(2n) / F(n) будет в среднем близко к 4, то функция времени работы асимптотически, скорее всего, лежит в O(n^2). Верно даже более сильное утверждение, что она, скорее всего, будет в Theta(n^2). Поняв таким образом, какая степень n при старшем множителе асимптотики, можно уже анализировать, какой там стоит множитель рядом с ней, т. е. отличать Theta(n), Theta(n log n), Theta (n (log n) ^ 2), Theta (n sqrt(n)) и подобные, просто поделив f(n) на n в нужной степени, и проанализировав этот самый хвост аналогично.
Думаю, что это стоит делать только в самом сложном и критичном случае, а так, как я уже писал в одном из комментариев —
Но если говорить это тесте, важнее не пропустить ситуацию, когда сложность алгоритма резко увеличивается, а для этого можно использовать для конкретного набора данных заранее вычисленные эталонные значения.
В случае с тестами задачу можно упростить:
1. Если мы заранее знаем, что нам не подойдет функция хуже, чем квадратичная, то нам уже не нужно точно вычислять асимптотику — достаточно убедиться, что больше, чем n^2.
2. Не всегда важна именно асимптотика, бывает что важно поведение функции на начальном отрезке (n — натуральные числа). Потому что бывают задачи с ограничениями на размер входных данных. Например, как в моих первых двух примерах. И там бывает, что алгоритм 20*x^2 работает хуже, чем x^3.
В таком случае вы пишете не «тест на алгоритмическую сложность» а обычный тест на скорость выполнения…
Точнее, у вас не алгоритмическая сложность оценивается, а просто количество операций. Вдруг будет какое-нибудь сбалансированное дерево, но длины могут быть порядка 997*logN. Тогда получается, если вы проверите для N = 1000, у вас стоимость поиска будет порядка 997 и вы решите что это линейная сложность?
Точнее, у вас не алгоритмическая сложность оценивается, а просто количество операций. Вдруг будет какое-нибудь сбалансированное дерево, но длины могут быть порядка 997*logN. Тогда получается, если вы проверите для N = 1000, у вас стоимость поиска будет порядка 997 и вы решите что это линейная сложность?
Определение сложности я привел в комментарии.
То, о чем Вы говорите, это асимптотическая оценка сложности Теория алгоритмов, стр. 18.
Видимо, я как-то неправильно назвал статью, чем и вызвал недопонимание.
По определению вычислительная сложность — это именно _функция_ зависимости объема работы от размера входных данных.
Вычислительная сложность — это функция, а вы просто вычисляете _значение_ этой функции в одной точке!
Предложение «При N = таком-то получаем количество операций K» — это не дает никакого представления о вычислительной сложности (равно как и алгоритмической, равно как и асимтотической оценки).
Предложение «При линейном увеличении N количество операций K растет как такая-то функция» — вот это найденная зависимость (т.е. найденная вычислительная сложность).
Вычислительная сложность — это функция, а вы просто вычисляете _значение_ этой функции в одной точке!
Предложение «При N = таком-то получаем количество операций K» — это не дает никакого представления о вычислительной сложности (равно как и алгоритмической, равно как и асимтотической оценки).
Предложение «При линейном увеличении N количество операций K растет как такая-то функция» — вот это найденная зависимость (т.е. найденная вычислительная сложность).
По определению вычислительная сложность — это именно _функция_ зависимости объема работы от размера входных данных.
Согласен с Вами, но разве я утверждал обратное? В комментариях 1, 2, 3 видно, что я говорю именно о функции.
Вычислительная сложность — это функция, а вы просто вычисляете _значение_ этой функции в одной точке!
Здесь я объяснил, почему именно в одной точке:
Цель статьи была показать, как использовать идею с Mock-объектами, для тестирования алгоритмической сложности. Суть идеи в том, что не вмешиваясь в код алгоритма и даже не имея доступа к нему, организовать подсчет операций для дальнейшего анализа. Именно поэтому в моем примере я указал одну точку — цели я своей достиг.
Вы пишите:
Предложение «При линейном увеличении N количество операций K растет как такая-то функция» — вот это найденная зависимость (т.е. найденная вычислительная сложность).
Но это не та задача, которую надо решать.
Очень часто есть проектный объем данных, на котором должна работать система. Поэтому часто более важно именно как ведет себя алгоритм на начальном отрезке от 1 до некоторого N, а не при n стремящимся к бесконечности.То есть асимптотическая оценка не так уж и важна. Например, в первом примере, который я привел в статье, у меня было 400 элементов. Зачем мне знать как будет себя вести та же система при n = 10000, 100000 и т.д.? Столько элементов на форме просто трудно себе представить!
Предположим, нас устроит, если сложность будет не хуже, чем 20*n^2. F(n) — наша неизвестная функция сложности. Вычисляем F(n) с помощью Mock-объекта на проектном объеме данных (это может быть и несколько точек) и сравниваем с эталонной функцией 20*n^2. Если вычисленное значение меньше, то тест пройден. Это позволяет вовремя отловить случайные изменение сложности используемого алгоритма.
Предположим, нас устроит, если сложность будет не хуже, чем 20*n^2. F(n) — наша неизвестная функция сложности. Вычисляем F(n) с помощью Mock-объекта на проектном объеме данных (это может быть и несколько точек) и сравниваем с эталонной функцией 20*n^2. Если вычисленное значение меньше, то тест пройден. Это позволяет вовремя отловить случайные изменение сложности используемого алгоритма.
Ясно, т.е. вы просто считаете количество операций при некоторых значениях. Если функции простые (типа полиномов, логарифмов) — все более-менее нормально. Но если функция более сложная, не монотонная? К примеру — возмем факторизацию числа, например. На 1024 она работает быстро, на 1000000000 — почти так же быстро. А вот на 1000000007 — будет работать ощутимо дольше =). Я уверен что можно придумать хитрый алгоритм хорошего быстрого контейнера, который работает сильно быстрее в особенных случаях (четности, степени двойки и т.д.). Оценить сложность алгоритмов такого класа вашим способом, видимо, не получится?
Кстати, мне кажется, что bool operator==(std::pair<const Mock, int> & p1, std::pair<const Mock, int> & p2) вам совсем не нужен: STL-евскому std::map должно хватать operator< для ключа (он у вас и так есть).
Ясно, т.е. вы просто считаете количество операций при некоторых значениях. Если функции простые (типа полиномов, логарифмов) — все более-менее нормально. Но если функция более сложная, не монотонная? К примеру — возмем факторизацию числа, например. На 1024 она работает быстро, на 1000000000 — почти так же быстро. А вот на 1000000007 — будет работать ощутимо дольше =). Я уверен что можно придумать хитрый алгоритм хорошего быстрого контейнера, который работает сильно быстрее в особенных случаях (четности, степени двойки и т.д.). Оценить сложность алгоритмов такого класа вашим способом, видимо, не получится?
Во-первых. Отложим в сторону сложность. Предположим, что у нас есть функция add(x, y) = x + y — обычная функция сложения. Нам нужно написать тесты для этой функции. Используя классы эквивалентности мы напишем ровно один тест, например, add(-2, 5) == 3. Совершенно понятно, что я могу написать функцию таким образом, что она будет работать неправильно, при этом указанный тест ошибку не покажет. Увы, но с этим надо смириться. Для успокоения используют метрики с покрытием кода. Но! даже 100 покрытие кода не гарантирует, что все ошибки будут найдены.
Во-вторых. У нас всегда есть только значения конечного числа точек. Следовательно возникает задача интерполяции, то есть восстановления функции по конечному числу точек на отрезке. Увы, но интерполировать функцию мы можем лишь только с некоторой долей погрешности. Потому что для любого сколь угодно малого отрезка существует даже очень хорошая — непрерывная сколь угодно дифференцируемая функция, для которой на этом отрезке будет «аномальный скачок». Так что возвращаясь к нашему случаю, пусть даже с натуральными числами, если мы перебрали N значений, то это еще не значит, что в N+1 точке функция поведет себя так, как мы ожидаем. Тест никогда не дает 100% гарантии на отсутствие ошибки Но задача теста и не в этом. Тест должен уменьшать вероятность существования ошибки или ее появления в будущем!
В-третьих. Можно не придумывать никакого хитрого алгоритма контейнера. Все проще, можно написать процедуру, которая на вход принимает массив целых чисел. При этом в зависимости от размера массива N она будет делать разные действия: при N < 1000 она сортирует массив пузырьковой сортировкой, при N >= 1000 сортирует массив быстрой сортировкой. Либо для четных один, а для нечетных — второй алгоритм. Но не забывайте про классы эквивалентности — в этом случае просто надо написать два теста.
Кстати, мне кажется, что bool operator==(std::pair<const Mock, int> & p1, std::pair<const Mock, int> & p2) вам совсем не нужен: STL-евскому std::map должно хватать operator< для ключа (он у вас и так есть).
Вы — правы. Поправил. Спасибо.
То о чем Вы здесь говорите, уже обсуждали в этой ветке.
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, выполняемой некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на носителе данных.
(Википедия)
В нашем случае речь идет о временной вычислительной сложности.
Алгоритмическая сложность = вычислительная сложность
(Википедия)
В нашем случае речь идет о временной вычислительной сложности.
Алгоритмическая сложность = вычислительная сложность
А почему вы считаете, что в копирующем конструкторе и в операторе присваивания всего одна операция записи? Интуитивно кажется, что здесь одна операция чтения и одна операция записи.
Также не понятно, почему в операторах сравнения вы считаете, что происходит одна операция чтения, хотя казалось бы должно быть две.
А вообще я бы считал количество операций записи и сравнения, потом, как хорошо отметил Zlobober, строил бы график F(n) для нескольких n.
Также не понятно, почему в операторах сравнения вы считаете, что происходит одна операция чтения, хотя казалось бы должно быть две.
А вообще я бы считал количество операций записи и сравнения, потом, как хорошо отметил Zlobober, строил бы график F(n) для нескольких n.
А почему вы считаете, что в копирующем конструкторе и в операторе присваивания всего одна операция записи? Интуитивно кажется, что здесь одна операция чтения и одна операция записи.
Также не понятно, почему в операторах сравнения вы считаете, что происходит одна операция чтения, хотя казалось бы должно быть две.
Да, Вы правы — моя ошибка. Спасибо.
А вообще я бы считал количество операций записи и сравнения, потом, как хорошо отметил Zlobober, строил бы график F(n) для нескольких n.
Иногда можно сделать проще — пример привел в комментарии.
Поправил в тексте.
Sign up to leave a comment.
Как написать автоматический тест на алгоритмическую сложность?