Приложение А. Анализ алгоритмов

Оригинал: Appendix A Analysis of Algorithms

Переводчик: Wizardforcel

Лицензия: CC BY-NC-SA 4.0

Гордо использует Google Translate

Частично основано на "Think Python 2e": Глава 21 "Анализ алгоритмов"

Анализ алгоритмов (Analysis of algorithms) — это раздел компьютерной науки, который сосредоточен на исследовании производительности алгоритмов, особенно их времени выполнения и затрат ресурсов. Подробнее см. http://en.wikipedia.org/wiki/Analysis_of_algorithms.

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

Во время президентской кампании США 2008 года, когда кандидат Барак Обама посетил Google, его попросили провести мгновенный анализ. CEO Эрик Шмидт шутливо спросил его "о наиболее эффективном методе сортировки миллиона 32-битных целых чисел". Очевидно, кто-то заранее сообщил Обаме, так как он быстро ответил: "По моему мнению, мы не должны использовать пузырьковую сортировку." Подробнее см. http://www.youtube.com/watch?v=k4RRi_ntQc8.Это правда: пузырьковая сортировка проста концептуально, но очень медленна при работе с большими наборами данных. Ответ на вопрос Шмидта может быть "сортировка радикса" (http://en.wikipedia.org/wiki/Radix_sort).> [1] Однако, если вас спросят этот вопрос во время собеседования, я считаю лучшим ответом следующий: "Наиболее быстрый способ отсортировать миллион целых чисел — использовать встроенные функции сортировки вашего языка программирования. Они оптимизированы для большинства применений. Но если моя программа окажется слишком медленной в конце концов, я буду использовать профилировщик для выявления мест, где уходит больше всего времени. Если использование более быстрого алгоритма значительно повысило бы производительность, я попробую найти хорошую реализацию сортировки радикса."

Цель анализа алгоритмов состоит в том, чтобы провести значимое сравнение между различными алгоритмами, однако существуют некоторые проблемы:* Относительная производительность алгоритма зависит от характеристик аппаратной платформы, поэтому один алгоритм может работать быстрее на машине A, а другой — на машине B. Общим подходом к решению этой проблемы является указание модели машины (machine model) и анализ количества шагов или операций, необходимых для выполнения алгоритма в данной модели.* Относительная производительность также может зависеть от деталей набора данных. Например, если данные уже частично отсортированы, некоторые сортировочные алгоритмы могут работать быстрее; при этом другие алгоритмы будут работать медленнее. Общий метод решения этой проблемы заключается в анализе наихудшего случая. Иногда полезно анализировать средний случай, но это обычно сложнее, и трудно понять, какие именно наборы данных следует использовать для вычисления среднего значения.* Относительная производительность также зависит от размера задачи. Алгоритм сортировки, который работает быстро для небольших списков, может работать медленнее для длинных списков. Обычным способом решения этой проблемы является представление времени выполнения (или количества операций) как функции размера задачи и разделение этих функций на различные категории в зависимости от скорости увеличения с ростом размера задачи. Преимуществом такого сравнения является возможность простого разделения алгоритмов на категории. Например, если я знаю, что время выполнения алгоритма А пропорционально размеру входных данных ( n ), а времени выполнения алгоритма Б — пропорционально ( n^2 ), то можно считать, что А быстрее Б, хотя бы при достаточно больших значениях ( n ).

Этот анализ также имеет некоторые проблемы, которые мы рассмотрим позже.

A.1 Уровень роста

Предположим, вы уже проанализировали два алгоритма и можете выразить время их выполнения через размер входных данных:

Если алгоритм А решает задачу размером ( n ) за ( 100n + 1 ) шагов, а алгоритм Б — за ( n^2 + n + 1 ) шагов.

Ниже представлены таблицы времени выполнения этих алгоритмов для различных размеров входных данных:

Основной причиной этого является то, что любая функция, содержащая член ( n^2 ), будет расти быстрее любой функции с первым членом ( n ) при достаточно больших значениях ( n ). Первый член (leading term) — это член с наибольшим показателем степени.

Для алгоритма A первый член имеет большой коэффициент 100, поэтому для малых значений ( n ) алгоритм B работает лучше. Но игнорируя этот коэффициент, всегда найдется некоторое значение ( n ), при котором ( a n^2 > b n ), где ( a ) и ( b ) могут принимать любые значения.

Аналогичные выводы справедливы и для остальных членов. Даже если время выполнения алгоритма A равно ( n + 1000000 ), для достаточно больших значений ( n ) он всё равно будет работать лучше, чем алгоритм B.

Общие правила говорят, что алгоритмы с меньшим первым членом считаются лучшими для больших размеров входных данных. Однако существует так называемая "точка пересечения" (crossover point), ниже которой другой алгоритм может быть предпочтительнее. Расположение этой точки зависит от деталей алгоритма, входных данных и аппаратуры, поэтому она обычно игнорируется при анализе алгоритмов. Однако это не значит, что её следует забывать.Если два алгоритма имеют одинаковый первый член, сложно сказать, какой из них лучше; ответ зависит от конкретных условий. Поэтому для анализа алгоритмов функции с одинаковым первым членом считаются эквивалентными, даже если они имеют различные коэффициенты.

Уровень роста (order of growth) — это множество функций, чьё поведение роста считается эквивалентным. Например, функции ( 2n ), ( 100n ) и ( n + 1 ) принадлежат одному уровню роста и могут быть записаны как ( O(n) ) с использованием нотации Big-Oh. Это часто называют линейным уровнем (linear), поскольку каждая функция в этом множестве увеличивается линейно относительно ( n ). Функция с первой степенью ( n^2 ) принадлежит ( O(n^2) ); они называются квадратичной (quadratic).

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

Посетите http://en.wikipedia.org/wiki/Big_O_notation , прочитайте статью Википедии о символе O большое и ответьте на следующие вопросы:

1. Какой уровень роста имеет n^3 + n^2? Каков уровень роста для 1000000 n^3 + n^2 и n^3 + 1000000 n^2?
2. Какой уровень роста имеет (n^2 + n) * (n + 1)? При начальном расчете помните, что вам нужно учитывать только первую степень.
3. Если уровень роста f равен O(g), как можно описать af + b для неопределенной функции g?
4. Если уровень роста f1 и f2 равен O(g), какой будет уровень роста для f1 + f2?
5. Если уровень роста f1 равен O(g), а уровень роста f2 равен O(h), какой будет уровень роста для f1 + f2?
6. Если уровень роста f1 равен O(g), а уровень роста f2 равен O(h), какой будет уровень роста для f1 * f2?

Программисты, заботящиеся о производительности, часто находят такой анализ трудным для восприятия. Они имеют право на это мнение: иногда коэффициенты и второстепенные члены могут иметь огромное значение. Иногда детали аппаратуры, языка программирования и характеристики входных данных могут оказывать значительное влияние. Для малых задач асимптотическое поведение может не иметь большого значения.Однако, если вы помните эти примечания, анализ алгоритмов является полезным инструментом. По крайней мере для больших задач, "наилучший" алгоритм обычно лучше, и иногда намного лучше. Различия между двумя алгоритмами одного уровня роста обычно являются константным множителем, но различия между хорошим и плохим алгоритмами бесконечно велики!## А.2 Анализ базовых операций в Python

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

Уровень роста операций индексирования — чтения или записи элементов в последовательностях или словарях — также является константным и не зависит от размера данных.

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

total = 0
for x in t:
    total += x

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

По опыту известно, что если уровень роста операций внутри цикла равен O(n^a), то общая сложность цикла будет O(n^(a+1)). Исключение составляют случаи, когда цикл завершается после выполнения фиксированного числа итераций. В таких случаях сложность цикла остается O(n^a), независимо от значения k.Умножение на k не меняет уровня роста, равно как и деление. Таким образом, если уровень роста операций внутри цикла равен O(n^a), и цикл выполняется n/k раз, то общая сложность цикла будет O(n^(a+1)), даже при значительном k.

Большинство операций со строками и кортежами имеют линейную сложность, кроме индексации и len, которые постоянны. Встроенные функции min и max также линейны. Операция среза пропорциональна длине выходных данных, но не зависит от размера входных данных.

Сцепление строк имеет линейную сложность; его временная стоимость зависит от общей длины объектов.

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

Большинство методов списков имеют линейную сложность, но есть некоторые исключения:* В среднем добавление элемента в конец списка является операцией постоянного времени. Когда список превышает доступное пространство, он иногда копируется в новое место большего размера, но общее время выполнения n операций всё равно составляет O(n), поэтому среднее время каждой операции — O(1).

• Удаление элемента из конца списка является операцией постоянного времени.
• Сортировка имеет сложность O(n log n). Большинство операций со словарями и методы выполняются за константное время, но есть некоторые исключения:* Время выполнения метода update пропорционально размеру передаваемого в качестве аргумента словаря (не самого обновляемого словаря).
• Методы keys, values и items выполняются за константное время, так как они возвращают итераторы. Однако если вы будете циклически проходить через эти итераторы, то цикл будет линейным.

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

Упражнение 2

Посетите http://en.wikipedia.org/wiki/Sorting_algorithm, прочитайте статью Википедии о сортировочных алгоритмах и ответьте на следующие вопросы:1. Что такое сортировка сравнением? Какой лучший порядок роста в худшем случае для сортировки сравнением? Каков лучший порядок роста для других алгоритмов сортировки в худшем случае?

2. Каков порядок роста алгоритма пузырьковой сортировки? Почему Обама считает его "способом, который следует избегать"?

3. Каков порядок роста алгоритма сортировки radix? Какие предварительные условия нам потребуются до использования этого алгоритма?

4. Что означает стабильность сортировочного алгоритма? Почему это важно на практике?

5. Какой худший сортировочный алгоритм имеет имя (не просто "плохо")?

6. Какой сортировочный алгоритм используется в языке программирования C? Какой сортировочный алгоритм используется в Python? Эти алгоритмы стабильны? Вам может понадобиться поискать информацию в интернете, чтобы найти ответы.

7. Большинство неконсервативных алгоритмов сортировки являются линейными, поэтому почему Python использует сортировочный алгоритм с порядком роста O(n log n)?## А.3 Анализ алгоритмов поиска

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

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

Оператор in для последовательностей использует линейный поиск; методы строки find и count также используют линейный поиск.

Если элементы в последовательности отсортированы, можно использовать двоичный поиск, который имеет порядок роста O(log n). Алгоритм двоичного поиска аналогичен тому, как вы ищете слово в словаре (в данном контексте — реальном словаре, а не структуре данных). Вы не начинаете с начала и последовательно проверяете каждый элемент, а начинаете с середины и проверяете, находится ли ваше слово раньше или позже. Если оно находится раньше, вы продолжаете поиск в первой половине последовательности. В противном случае вы продолжаете поиск во второй половине. Таким образом, вы постоянно делите количество оставшихся элементов пополам.

Упражнение 3

Напишите функцию под названием bisection, которая принимает отсортированный список и значение цели, и возвращает индекс значения в списке (если он существует); если нет, то возвращает None.Или вы можете прочитать документацию модуля бинарного поиска и использовать его!

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

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

Другой более быстрой структурой данных называется хеш-таблицей (hash table) — она может найти результат за константное время и не зависит от того, отсортирована ли последовательность. Хеш-таблица используется в Python для реализации словарей, так что большинство операций со словарями, включая оператор in, выполняются за константное время.

А.4 Хеш-таблицы

Чтобы объяснить, как работают хеш-таблицы и почему они такие эффективные, мы начнем с реализации простого отображения (map) и постепенно будем улучшать его до хеш-таблицы.Мы используем Python для демонстрации этих реализаций, но в реальной жизни вам не придётся писать такой код на Python; достаточно будет использовать встроенные объекты словаря! Поэтому далее предположим, что объекты словаря не существуют, и вы хотите самостоятельно реализовать структуру данных, которая будет связывать ключи со значениями. Операции, которые вам нужно реализовать, включают:add(k, v):

Добавляет новый элемент, который ассоциируется с ключом k и значением v. В случае использования словаря d на Python эта операция записывается как d[k] = v.

get(k):

Находит и возвращает значение, связанное с указанным ключом. В случае использования словаря d на Python эта операция записывается как d[k] или d.get(k).

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

class LinearMap:

    def __init__(self):
        self.items = []

    def add(self, k, v):
        self.items.append((k, v))

    def get(self, k):
        for key, val in self.items:
            if key == k:
                return val
        raise KeyError

add добавляет новую пару "ключ-значение" в список элементов, что происходит за постоянное время.

get использует цикл for для поиска данного списка: если он находит нужный ключ, он возвращает соответствующее значение; в противном случае вызывает ошибку KeyError. Таким образом, get является линейным. Другой подход заключается в том, чтобы сохранять список с отсортированными ключами. В таком случае метод get может использовать двоичный поиск со сложностью O(log n). Однако вставка нового элемента посередине списка будет иметь линейную сложность, поэтому это может не быть лучшим выбором.Есть также другие структуры данных, которые могут обеспечивать операции add и get за время O(log n), но это всё равно хуже константной сложности. Поэтому продолжаем исследование.

Одним из способов улучшения LinearMap является разделение списка пар "ключ-значение" на меньшие списки. Ниже приведён пример реализации такой структуры данных, которая называется BetterMap и состоит из 100 объектов LinearMap.

class BetterMap:

    def __init__(self, n=100):
        self.maps = []
        for i in range(n):
            self.maps.append(LinearMap())

    def find_map(self, k):
        index = hash(k) % len(self.maps)
        return self.maps[index]

    def add(self, k, v):
        m = self.find_map(k)
        m.add(k, v)

    def get(self, k):
        m = self.find_map(k)
        return m.get(k)

Метод __init__ создаёт список из n объектов LinearMap.

Методы add и get используют метод find_map для определения, в какой из этих списков следует добавить новую пару или выполнить поиск.

Метод find_map использует встроенный метод hash, который принимает почти любой объект Python и возвращает целое число. Ограничением этой реализации является то, что она работает только с хэшируемыми ключами. Нехэшируемые типы данных, такие как списки и словари, не могут использоваться в качестве ключей.

Хэшируемые объекты, считающиеся равными, должны возвращать одинаковое значение хэша, хотя обратное утверждение не всегда верно: два разных объекта могут возвращать одинаковое значение хэша.Метод find_map использует оператор взятия остатка для ограничения значения хэша между 0 и len(self.maps), таким образом получая допустимый индекс этого списка. Конечно, это означает, что многие различные значения хэша будут преобразованы в один и тот же индекс. Однако, если функция хэширования распределена достаточно равномерно (что и было её целью при проектировании), мы можем ожидать, что каждый LinearMap будет содержать около n/100 элементов.

Учитывая, что временная сложность метода LinearMap.get пропорциональна количеству элементов, можно ожидать, что BetterMap будет работать в 100 раз быстрее, чем LinearMap. Тем не менее, временная сложность остаётся линейной, но коэффициент пропорциональности значительно меньше. Это хорошо, но всё ещё хуже, чем у хэш-таблиц. Вот что делает хэш-таблицу быстрее: если вы можете гарантировать, что максимальная длина LinearMap ограничена верхним пределом, то временная сложность метода LinearMap.get будет константной. Вам просто нужно отслеживать количество элементов и увеличивать размер хеш-таблицы, добавляя больше LinearMap, когда количество элементов в каждом LinearMap превышает пороговое значение. Вот реализация хеш-таблицы:

class HashMap:

    def __init__(self):
        self.maps = BetterMap(2)
        self.num = 0

    def get(self, k):
        return self.maps.get(k)

    def add(self, k, v):
        if self.num == len(self.maps.maps):
            self.resize()
```        self.maps.add(k, v)
        self.num += 1

    def resize(self):
        new_maps = BetterMap(self.num * 2)

        for m in self.maps.maps:
            for k, v in m.items():
                new_maps.add(k, v)

        self.maps = new_maps

Каждая HashMap включает в себе объект BetterMap. Конструктор начинается с двух объектов LinearMap, а также инициализирует счётчик num, который отслеживает количество элементов.

Метод get просто делегирует запрос к объекту BetterMap. Основные операции происходят внутри метода add, который проверяет количество элементов и размер объекта BetterMap: если они равны, среднее количество элементов в каждом LinearMap равно одному, поэтому вызывается метод resize.

Метод resize создаёт новый объект BetterMap, размер которого в два раза больше старого, затем перехеширует все элементы из старой таблицы в новую.

Перехеширование необходимо, так как изменение количества LinearMap меняет знаменатель операции взятия остатка в методе find_map. Это значит, что некоторые объекты, которые были помещены в одинаковый LinearMap, теперь будут разделены (то есть то, что мы и хотели достичь).Перехеширование является линейной операцией, следовательно, метод resize также является линейным, что может показаться непригодным, но помните, что мы не всегда должны выполнять перезагрузку, поэтому метод add обычно работает за конstantное время, хотя иногда он выполняется за линейное время. Общее количество работы при выполнении метода add n раз пропорционально n, следовательно, среднее время выполнения метода add — это константа!

Здесь исправлено слово "конstantное" на "константное".Чтобы понять, как это работает, рассмотрим пример, когда мы начинаем с пустой HashTable и добавляем серию элементов. Мы начинаем с двух LinearMap, поэтому первые два добавления очень быстрые (не требуют перезагрузки). Предположим, что каждое добавление занимает единицу работы. Третье добавление требует перезагрузки, поэтому нам нужно перехешировать первые два элемента (это считается двумя дополнительными единицами работы) и добавить третий элемент (ещё одна единица работы). Четвертое добавление занимает одну единицу работы, поэтому всего четыре добавления потребуют шесть единиц работы.

Пятый добавочный вызов будет стоить пяти единиц работы, но последующие три вызова каждый будут стоить одной единицы работы, поэтому первые восемь добавлений в сумме потребуют четырнадцати единиц работы. Следующий add занимает 9 единиц, но после этого до следующего увеличения размера можно добавить ещё семь, так что первые 16 операций add в сумме требуют 30 единиц.После 32 операций add общее количество затраченных единиц равно 62, надеюсь, вы начинаете замечать закономерность. После n операций add, где n является четным числом, общие затраты составляют 2n - 2 единицы, поэтому среднее время выполнения каждой операции add составляет менее двух единиц. Это лучший случай, когда n является четным числом. Для других значений n средняя стоимость немного выше, но это не важно. Важно то, что уровень роста имеет порядок O(1).Нижеприведённая диаграмма наглядно демонстрирует принцип работы. Каждый блок представляет собой единицу работы. Каждый столбец показывает количество единиц, необходимых для каждого add, расположенные слева направо: первые два add занимают одну единицу, третий занимает три единицы и так далее.

Рисунок А.1: Стоимость операции add в хэш-таблице

Дополнительная работа при перехешировании проявляется как серия всё более высоких башен, расстояние между которыми постоянно увеличивается. Теперь, если вы "перевернёте" эти башни, распределяя стоимость увеличения размера равномерно среди всех add, вы можете видеть на графике, что общая стоимость n операций add составляет 2n - 2.

Одним из важнейших аспектов данного алгоритма является то, что при увеличении размера HashTable используется геометрический рост; другими словами, мы используем постоянное число, умноженное на текущий размер таблицы. Если бы вы использовали арифметический рост — увеличивали бы размер на фиксированное количество — среднее время выполнения каждой операции add было бы линейным.

Вы можете скачать реализацию HashMap с http://thinkpython2.com/code/Map.py. Вам нет необходимости использовать её; если вам нужна структура данных типа отображение, просто используйте словарь Python.Упражнение 4

Моя реализация HashMap прямо обращается к свойствам BetterMap, что указывает на плохую объектно-ориентированную структуру.

• Специальный метод __len__ вызывается внутренней функцией len. Напишите метод __len__ для BetterMap и используйте его в add.
• Используйте генератор для написания iteritems для BetterMap и используйте его в resize.

Упражнение 5

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

Напишите реализацию интерфейса карты TreeMap, которая использует красно-черное дерево для выполнения операций add и log за время, логарифмическое относительно количества элементов.## А.5 Суммирование списков

Предположим, что у вас есть набор списков, и вы хотите объединить их в один список. В Python существует три способа выполнить эту операцию:

Вы можете использовать оператор +=:

total = []
for x in t:
    total += x

Или метод extend():

total = []
for x in t:
    total.extend(x)

Или встроенный метод sum():

total = sum(t, [])

Второй аргумент функции sum() является начальным значением суммы.Без знания того, как реализованы +=, extend(), и sum(), сложно анализировать их производительность. Например, если total += x создаёт новый список каждый раз, то цикл будет иметь квадратичную сложность; но если он модифицирует текущий список, это будет линейной сложностью.Чтобы найти ответ, мы можем проанализировать исходный код, однако, давайте попробуем понять это с помощью замера времени выполнения.

Простейший способ измерения времени выполнения программы — использование функции time из модуля os. Эта функция возвращает кортеж из плавающих чисел, представляющий время, затраченное процессом (подробнее см. Документацию). Я использовал функцию etime(), которая возвращает сумму "времени пользователя" и "системного времени", обычно это то, что нас интересует в контексте производительности:

import os

def etime():
    """Узнать, сколько времени потока было затрачено на выполнение этой функции,
    и вернуть его сумму."""
    
    user, sys, chuser, chsys, real = os.times()
    return user + sys

Для измерения времени выполнения одной функции можно дважды вызвать etime() и вычесть одно значение от другого:

start = etime()

# поместите код, который вы хотите измерить здесь

end = etime()
elapsed = end - start

Или, если вы используете IPython, вы можете воспользоваться командой timeit. Подробнее см. ipython.scipy.org.

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

[ t = a \cdot n^2 + b \cdot n + c ]

Где ( a ), ( b ) и ( c ) — это неизвестные коэффициенты. Если взять логарифм от обоих сторон, получим:

[ \log(t) \approx \log(a) + 2 \log(n) ]Для больших значений n второстепенные члены становятся незначительными, и этот приближенный вид становится очень хорошим. Поэтому, если мы построим график t относительно n на двойном логарифмическом масштабе, мы ожидаем прямую линию со значением наклона равным 2.

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

Я написал три функции для объединения списков: sum_plus использует +=; sum_extend использует list.extend; sum_sum использует sum(). Я замерил время выполнения этих функций для различных значений n и построил графики на двойном логарифмическом масштабе. Ниже представлены результаты.

Рисунок а.2: Время выполнения и n, пунктирная линия имеет наклон 1.

Рисунок а.3: Время выполнения и n, пунктирная линия имеет наклон 2.

На рисунке а.2 я использовал прямую с наклоном 1 для аппроксимации кривой. Эта линия хорошо аппроксимирует данные, поэтому мы делаем вывод, что эти реализации являются линейными. Реализация += работает быстрее, так как каждый раз при цикле требуется время для поиска метода extend.

На рисунке а.3 линия с наклоном 2 аппроксимирует данные, поэтому реализация sum является квадратичной.

А.6 pyplotДля создания графиков в этом разделе я использовал pyplot, который является частью библиотеки matplotlib. Если ваша установка Python не включает matplotlib, вам может потребоваться его установить; либо вы можете использовать другую библиотеку для отображения графиков.```py

import matplotlib.pyplot as pyplot

pyplot.plot(xs, ys) scale = 'log' pyplot.xscale(scale) pyplot.yscale(scale) pyplot.title('') pyplot.xlabel('n') pyplot.ylabel('время выполнения (с)') pyplot.show()

Импортированные строки позволяют использовать `matplotlib.pyplot` с более коротким именем `pyplot`.

Функция `plot` принимает список значений `x` и список значений `y` и строит график. Длина списков должна быть одинаковой. Функции `xscale` и `yscale` устанавливают линейные или логарифмические оси.

`title`, `xlabel` и `ylabel` имеют очевидное значение. Наконец, `show` отображает график на экране. Вы также можете использовать `savefig` для сохранения графика в файле.

Документация по `pyplot` доступна по адресу <http://matplotlib.sourceforge.net/>.

Упражнение 6

Проверьте производительность `LinearMap`, `BetterMap` и `HashMap`; попробуйте описать уровень их роста.

Вы можете скачать мои реализации карт из <https://thinkcomplex.com/Map.py> и код, используемый мной в этом разделе, из <https://thinkcomplex.com/listsum.py>.

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