Глава 5. Двусвязный список

В этой главе рассматривается предыдущая задача и вводится ещё одна реализация интерфейса List — двусвязный список.

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

Во время предыдущей задачи мы использовали Profiler.java для измерения времени выполнения различных операций над ArrayList и LinkedList при разных масштабах задач. Мы построили график зависимости времени выполнения от масштаба задачи на логарифмической шкале и оценили наклон полученной кривой, который отражает основную экспоненту отношения между временем выполнения и масштабом задачи.

Например, когда мы добавляли элементы в конец ArrayList с помощью метода add, мы обнаружили, что общее время выполнения n добавлений пропорционально n. То есть оценка наклона близка к 1. Мы пришли к выводу, что выполнение n добавлений имеет сложность O(n), поэтому среднее время добавления одного элемента является постоянным, или O(1), что соответствует нашим ожиданиям на основе анализа алгоритма.

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

Это решение можно найти в каталоге solution репозитория.

public static void profileArrayListAddBeginning() {
    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(0, "a string");
            }
        }
    };
    int startN = 4000;
    int endMillis = 10000;
    runProfiler("ArrayList add beginning", timeable, startN, endMillis);
}

Этот метод практически идентичен profileArrayListAddEnd. Единственное отличие заключается в методе timeMe, который использует двухпараметрическую версию метода add для вставки нового элемента по индексу 0. Также мы увеличили endMillis, чтобы получить дополнительную точку данных.

Результаты времени (слева — масштаб задачи, справа — время в миллисекундах):

График 5.1 показывает зависимость времени выполнения от масштаба задачи.

График 5.1: Анализ результатов: зависимость времени выполнения добавления n элементов в начало ArrayList от масштаба задачи

Обратите внимание, что линия на графике не означает, что алгоритм является линейным. Напротив, если для любого показателя k время выполнения пропорционально n^k, мы ожидаем увидеть линию с наклоном k. В этом случае мы ожидаем, что общая сложность n добавлений пропорциональна n^2, поэтому мы ожидаем линию с наклоном 2. Фактически, оценка наклона составляет 1,992, что очень близко. Вероятно, только ложные данные могут быть настолько хорошими.

5.2 Анализ производительности методов LinkedList

Ранее в задаче вы также анализировали производительность добавления новых элементов в начало LinkedList. Согласно нашему анализу, мы ожидали, что каждый вызов add займёт некоторое время, так как в связанном списке нам не нужно перемещать существующие элементы; мы можем добавить новый узел в начало. Поэтому мы ожидали, что общая сложность n добавлений будет линейной.

Вот решение:

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

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

        public void timeMe(int n) {
            for (int i=0; i<n; i++) {
                list.add(0, "a string");
            }
        }
    };
    int startN = 128000;
    int endMillis = 2000;
    runProfiler("LinkedList add beginning", timeable, startN, endMillis);
}

Мы внесли лишь несколько изменений, заменив ArrayList на LinkedList и скорректировав startN и endMillis для получения хорошего диапазона данных. Результаты измерений более разбросаны, чем в предыдущей партии данных; результаты следующие:

График 5.2 показывает эти результаты графически.

График 5.2: Анализ результатов: зависимость времени выполнения добавления n элементов в начало LinkedList от масштаба задачи

Линия не совсем прямая, и наклон не точно равен 1, а оценка наименьших квадратов составляет 1,23. Однако результаты показывают, что общая сложность n добавлений, по крайней мере, приблизительно равна O(n), поэтому каждое добавление занимает постоянное время.

5.3 Добавление в конец LinkedList

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

Однако это не так. Вот код:

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

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

        public void timeMe(int n) {
            for (int i=0; i<n; i++) {
                list.add("a string");
            }
        }
    };
    int startN = 64000;
    int endMillis = 1000;
    runProfiler("LinkedList add end", timeable, startN, endMillis);
}

Здесь приведены результаты:

График 5.3 показывает эти результаты графически.

График 5.3: Анализ результатов: зависимость времени выполнения добавления n элементов в конец LinkedList от масштаба задачи

Опять же, измеренные значения сильно разбросаны, линия не полностью прямая, но оценка наклона составляет 1,19, что близко к добавлению элементов в начале, а не очень близко к 2, как ожидалось на основе анализа. На самом деле он близок к 1, что указывает на то, что добавление элементов в конце является постоянной операцией. Как это возможно?

5.4 Двусвязный список

Мой список реализован как MyLinkedList, используя односвязный список; то есть каждый элемент содержит ссылку на следующий элемент, и сам объект MyArrayList имеет ссылку на первый узел.

Однако, если вы прочитаете документацию LinkedList по адресу http://thinkdast.com/linked, там говорится:

Реализация интерфейсов List и Deque с использованием двусвязного списка. [...] Все операции могут выполняться аналогично двунаправленному списку, обходя список с того конца, который ближе к указанному индексу.

Если вы не знакомы с двусвязными списками, вы можете прочитать больше информации на http://thinkdast.com/doublelist, но вкратце:

• Каждый узел содержит ссылки на следующий и предыдущий узлы. Объект LinkedList содержит ссылки на первый и последний элементы списка.

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

В таблице ниже приведены ожидаемые характеристики производительности ArrayList, MyLinkedList (односвязный список) и LinkedList (двусвязный список):

5.5 Выбор структуры

Для вставки и удаления элементов в начале списка реализация двусвязного списка превосходит ArrayList. Для вставки и удаления в конце списка обе структуры работают одинаково хорошо. Поэтому единственное преимущество ArrayList — это операции get и set, которые в списках требуют линейного времени, даже для двусвязных списков.

Если вы знаете, что время выполнения вашего приложения зависит от времени, необходимого для операций get и set элементов, то ArrayList может быть лучшим выбором. Если время выполнения зависит от добавления и удаления элементов в начало или конец списка, то LinkedList может оказаться более подходящим.

Однако помните, что эти рекомендации основаны на предположении о большом масштабе задачи. Есть и другие факторы, которые следует учитывать:

• Если эти операции не занимают большую часть времени выполнения вашего приложения — то есть если ваше приложение тратит большую часть времени на выполнение других операций — тогда выбор реализации List не так важен.
• Если список, который вы обрабатываете, не очень большой, вы можете не получить ожидаемой производительности. Для небольших задач квадратичный алгоритм может работать быстрее, чем линейный, или линейный может быть быстрее, чем постоянный. Однако для небольших задач разница может быть несущественной.
• Кроме того, не забывайте о пространстве. До сих пор мы сосредоточились на времени выполнения, но разные реализации требуют разного пространства. В ArrayList элементы хранятся последовательно в одном блоке памяти, поэтому пространство используется эффективно, и компьютерное оборудование обычно работает быстрее с последовательными блоками. В списке каждый элемент требует узла с одним или двумя ссылками. Ссылки занимают место (иногда даже больше, чем данные!), и узлы разбросаны по памяти, что может снизить эффективность оборудования.

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

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

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