Четвертая глава: LinkedList

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

4.1 Методы MyLinkedList: разделение на категории

Здесь представлен мой метод indexOf для поиска индекса объекта в списке. Перед тем как читать описание метода, рекомендуется ознакомиться с ним самостоятельно и попытаться определить его сложность.

public int indexOf(Object target) {
    Node node = head;
    for (int i=0; i<size; i++) {
        if (equals(target, node.data)) {
            return i;
        }
        node = node.next;
    }
    return -1;
}

Изначально переменная node указывает на head, поэтому они оба ссылаются на один и тот же Node. Переменная цикла i изменяется от 0 до size-1. В каждом цикле мы используем equals, чтобы проверить, нашли ли мы цель. Если это так, мы немедленно возвращаем значение i. В противном случае мы перемещаемся к следующему узлу в списке. Обычно мы проверяем, что следующий узел не равен null, но здесь это безопасно, потому что когда мы достигаем конца списка, цикл завершается (при условии, что size соответствует фактическому количеству узлов в списке). Если мы проходим по всему циклу, не находя цели, мы возвращаем -1. Какова сложность этого метода?

• Каждый раз в цикле мы вызываем equals, который является операцией с постоянным временем (она может зависеть от размера target или data, но не от размера списка). Другие операции в цикле также имеют постоянное время.
• Цикл может выполняться n раз, поскольку в худшем случае нам может потребоваться пройти по всему списку. Таким образом, сложность этого метода пропорциональна длине списка. Далее следует реализация моего метода add с двумя параметрами. Опять же, вы должны попытаться разделить его на категории, а затем прочитать описание.

public void add(int index, E element) {
    if (index == 0) {
        head = new Node(element, head);
    } else {
        Node node = getNode(index-1);
        node.next = new Node(element, node.next);
    }
    size++;
}

Если index равен 0, мы добавляем новый узел в начало списка, поэтому мы рассматриваем этот случай отдельно. В противном случае нам нужно пройти по списку, чтобы найти элемент с индексом index-1. Мы используем вспомогательный метод getNode:

private Node getNode(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    Node node = head;
    for (int i=0; i<index; i++) {
        node = node.next;
    }
    return node;
}

getNode проверяет, находится ли индекс за пределами диапазона; если это так, он генерирует исключение. В противном случае он проходит по списку и возвращает запрошенный узел. Возвращаясь к методу add, после нахождения подходящего узла я создаю новый узел и вставляю его между node и node.next. Возможно, рисование этой операции поможет вам лучше понять её. Какова сложность метода add?

• Метод getNode аналогичен методу indexOf по той же причине и имеет линейную сложность.
• В методе add всё, что происходит до и после вызова getNode, выполняется за постоянное время. Следовательно, метод add имеет линейную сложность. Наконец, рассмотрим метод remove:

public E remove(int index) {
    E element = get(index);
    if (index == 0) {
        head = head.next;
    } else {
        Node node = getNode(index-1);
        node.next = node.next.next;
    }
    size--;
    return element;
}

Метод remove использует метод get для поиска и сохранения элемента по индексу index. Затем он удаляет содержащий его узел. Если индекс равен 0, мы снова обрабатываем этот особый случай. В противном случае мы находим узел index-1 и модифицируем его, пропуская node.next и напрямую связывая его с node.next.next. Это эффективно удаляет node.next из списка, и он может быть собран сборщиком мусора. Наконец, мы уменьшаем размер и возвращаем элемент, который мы искали в начале. Какова сложность метода remove? Всё в методе remove, кроме методов get и getNode, имеет постоянное время выполнения. Следовательно, метод remove также имеет линейную сложность. Когда люди видят две линейные операции, они иногда думают, что результат будет квадратичным, но это верно только в том случае, если одна операция вложена в другую. Если вы вызываете одну операцию после другой, их времена выполнения складываются. Если обе операции O(n), то общее время также равно O(n).

4.2 Сравнение MyArrayList и MyLinkedList

Таблица ниже суммирует различия между MyArrayList и MyLinkedList, где 1 означает O(1) или постоянное время, а n означает O(n) или линейное время.

MyArrayList имеет преимущество в операциях вставки в конец, удаления в конце, получения и установки. MyLinkedList имеет преимущество в операциях вставки в начало и перемещения в начало. Для других операций сложность обоих реализаций одинакова. Какая реализация лучше? Это зависит от того, какие операции вы, скорее всего, будете использовать. Именно поэтому Java предоставляет несколько реализаций, так как это зависит от ваших потребностей.

4.3 Анализ производительности

Для следующего упражнения я предоставляю класс Profiler, содержащий код, который использует серию проблем для измерения времени выполнения методов и построения результатов. Вы будете использовать Profiler для анализа производительности методов add для реализаций ArrayList и LinkedList в Java. Вот пример того, как использовать анализатор:

public static void profileArrayListAddEnd() {
    Timeable timeable = new Timeable() {
        List<String> list;

        public void setup(int n) {
            list = new ArrayList<String>();
        }

        public void timeMe(int n) {
            for (int i=0; i<n; i++) {
                list.add("a string");
            }
        }
    };

    String title = "ArrayList add end";
    Profiler profiler = new Profiler(title, timeable);

    int startN = 4000;
    int endMillis = 1000;
    XYSeries series = profiler.timingLoop(startN, endMillis);
    profiler.plotResults(series);
}

Этот метод измеряет время, необходимое для добавления новых элементов в конец ArrayList. Я объясню код, а затем покажу результаты. Чтобы использовать Profiler, нам нужно создать объект Timeable, который предоставляет два метода: setup и timeMe. Метод setup выполняет любую работу, необходимую перед началом отсчёта времени; здесь он создаёт пустой список. Затем метод timeMe выполняет операцию, которую мы пытаемся измерить; здесь он добавляет n элементов в список. Создание timeable — это код анонимного класса, который используется для определения новой реализации интерфейса Timeable и одновременного создания экземпляра нового класса. Если вы не знакомы с анонимными классами, вы можете прочитать об этом здесь: http://thinkdast.com/anonclass.

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

Следующим шагом будет создание объекта Profiler, передача объекта Timeable и заголовка в качестве параметров.

Profiler предоставляет метод timingLoop, который использует экземпляр переменной Timeable, хранящийся в памяти. Он многократно вызывает метод timeMe объекта Timeable, используя серию значений n. Метод timingLoop принимает два параметра:

• startN — значение n, с которого должен начинаться цикл отсчёта.
• endMillis — порог в миллисекундах. По мере увеличения масштаба проблемы время выполнения увеличивается; когда время выполнения превышает этот порог, timingLoop останавливается.

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

Этот код находится в файле ProfileListAdd.java, и вы будете запускать его в следующем упражнении. Когда я запускаю его, я получаю следующий вывод:

4000, 3
8000, 0
16000, 1
32000, 2
64000, 3
128000, 6
256000, 18
512000, 30
1024000, 88
2048000, 185
4096000, 242
8192000, 544
16384000, 1325

Первый столбец — масштаб проблемы, n; второй столбец — время выполнения в миллисекундах. Первые несколько измерений очень шумные; лучше всего установить startN примерно на 64 000.

Результат timingLoop представляет собой XYSeries, содержащий эти данные. Если вы передадите эту последовательность в plotResults, она создаст график, подобный показанному на рисунке 4.1.

Рисунок 4.1 Анализ результатов: время выполнения добавления n элементов в конец ArrayList и масштаб проблемы.

В следующем разделе объясняется, как интерпретировать результаты.

4.4 Интерпретация результатов

Основываясь на нашем понимании того, как работает ArrayList, мы ожидаем, что при добавлении элементов в конец метод add будет занимать постоянное время. Поэтому общее время добавления n элементов должно быть линейным.

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

runtime = a + b * n

где a — точка пересечения с осью y, а b — наклон.

С другой стороны, если add является линейным, то общее время для n добавлений будет квадратичным. Если мы построим время выполнения против масштаба проблемы, мы ожидаем увидеть параболу. Или, в математике, например:

runtime = a + b * n + c * n ** 2

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

Почему? Мы предполагаем, что время выполнения пропорционально n ** k, но мы не знаем, какое значение имеет показатель степени k. Мы можем записать отношение следующим образом:

runtime = a + b * n + ... + c * n ** k

Для больших значений n наиболее важным является член с наивысшей степенью, поэтому:

runtime ≈ c * n ** k

Где ≈ означает «примерно равно». Теперь, если мы возьмём логарифм обеих сторон этого уравнения:

log(runtime) ≈ log(c) + k * log(n)

Это уравнение означает, что если мы построим время выполнения относительно n на логарифмической шкале, мы ожидаем прямую линию с точкой пересечения log(c) и наклоном k. Нас не слишком волнует точка пересечения, но наклон указывает на степень роста: если k = 1, алгоритм линейный; если k = 2, он квадратичный.

Глядя на числа в предыдущем разделе, вы можете оценить наклон на глаз. Однако, когда вы вызываете plotResults, он вычисляет наилучшее соответствие данным методом наименьших квадратов и печатает оценочный наклон. В этом примере:

Estimated slope = 1.06194352346708

Он близок к 1, и это указывает на то, что общее время добавления n элементов является линейным, так что каждое добавление занимает постоянное время, как и ожидалось.

Важный момент: если вы видите такую прямую линию на графике, это не обязательно означает, что алгоритм является линейным. Если для любого показателя степени k время выполнения пропорционально n ** k, мы ожидаем линию наклона k. Если наклон близок к 1, это указывает на линейный алгоритм. Если он близок к 2, это может быть квадратично.

4.5 Упражнение 4

В репозитории этой книги вы найдёте необходимые исходные файлы для этого упражнения:

• Profiler.java содержит реализацию класса Profiler. Вы будете использовать этот класс, но вам не нужно знать, как он работает. Но вы можете читать исходный код в любое время.
• Файл ProfileListAdd.java включает в себя начальный код для этого упражнения, включая пример, который измеряет ArrayList.add. Вы измените этот файл для измерения некоторых других методов.

Кроме того, в каталоге code вы найдёте файл сборки Ant build.xml.

Запустите ant ProfileListAdd, чтобы запустить ProfileListAdd.java. Вы должны получить результат, похожий на рисунок 4.1, но вам, возможно, придётся настроить startN или endMillis. Оценочный наклон должен быть близок к 1, указывая на то, что требуемое время для выполнения n операций добавления пропорционально n, то есть оно O(n).

Вы обнаружите пустой метод profileArrayListAddBeginning в ProfileListAdd.java. Используйте код тестирования ArrayList.add, чтобы заполнить тело этого метода, всегда помещая новые элементы в начало. Если вы начнёте с копии profileArrayListAddEnd, вам нужно внести лишь несколько изменений. Добавьте строку в main, чтобы вызвать этот метод.

Снова запустите ant ProfileListAdd и объясните результаты. Основываясь на нашем понимании работы ArrayList, мы ожидаем, что каждая операция добавления будет линейной, поэтому общее время для n добавлений должно быть квадратичным. Если это так, линия наклона на логарифмической шкале должна быть близка к 2. Верно ли это?

Теперь давайте сравним это с LinkedList. Когда мы помещаем новые элементы в начало, заполняем profileLinkedListAddBeginning и используем его для разделения LinkedList.add. Чего вы ожидаете от производительности? Соответствуют ли результаты вашим ожиданиям?

Наконец, заполните тело profileLinkedListAddEnd и используйте его для разделения LinkedList.add. Чего вы ожидаете от производительности? Соответствуют ли результаты вашим ожиданиям?

Я представлю результаты и отвечу на эти вопросы в следующей главе.