Алгоритмы и структуры данных в Java

Разработка программного обеспечения всегда связана с обработкой или хранением информации. Эту информацию мы обрабатываем, изменяем, либо храним в памяти.

Как инженеры, мы, чаще всего, используем термин “данные”, вместо информации.

Для хранения данных используются структуры данных, а для их обработки – алгоритмы. Независимо от языка программирования, предметной области, мы всегда сталкиваемся с этими двумя сущностями (структуры данных и алгоритмы).

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

Цель данной статьи – дать базовое понимание того, что такое структуры данных и что такое алгоритм. Мы рассмотрим, способ сравнения алгоритмов по времени и по используемой памяти.

Структуры данных

Для начала обратимся к определению структуры данных:

Структура данных (англ. data structure) — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике.

Как мы видим, всё это крайне абстрактно и нам хотелось бы больше конкретики.

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

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

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

Таким образом мы приходим к такому понятию как алгоритм.

Алгоритм

Обратившись к википедии, мы увидим следующее определение:

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

Но, с точки зрения разработки ПО, мы получаем дополнительные требования к алгоритму:

• Имеет конечное число шагов
• Содержит чёткие и понятные инструкции
• Выдаёт результат

Для описания алгоритма существует 2 общепринятых похода:

1. Блок-схема
2. Псевдокод

Блок-схема

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

Существует много символов, которые могут быть использованы при создании блок-схем, но, ключевые и наиболее часто используемые указаны ниже:

Рассмотрим пример построения блок-схемы для линейного поиска.

Т.е. мы имеем массив целых чисел и хотим найти в нём элемент по значению. Для этого мы перебираем массив и сравниваем каждый элемент с искомым значением.

Если элемент найден мы возвращаем его индекс, если не найден – сообщаем об этом.

Стоит отметить, что блок-схемы удобны для описания алгоритмов, но, не стоит применять их для описания работы большой системы в целом. Для этих целей куда лучше подходит UML (Unified Modeling Language — унифицированный язык моделирования).

Теперь попробуем описать данный алгоритм с помощью псевдокода.

Псевдокод

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

Описание задачи остаётся прежним.

METHOD linearSearch(integerArray, searchItem):
START METHOD
FOR index FROM 0 -> length(integerArray):
IF integerArray[index] == searchItem
THEN RETURN index
END IF
END LOOP

RETURN -1
END METHOD

Как мы видим, псевдокод крайне похож на обычный язык и не подходит для компиляции.

Тем не менее, разработчик, который его читает, с лёгкостью сможет понять, что именно необходимо реализовать.

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

Алгоритмы поиска

Для базового изучения алгоритмов крайне подходит такая структура данных как массив.

Массив – структура данных в виде набора компонентов (элементов массива), расположенных в памяти непосредственно друг за другом, что позволяет обращаться к элементам по числовому индексу.

Наиболее примитивный алгоритм поиска – линейный поиск (псевдокод которого мы рассматривали выше).

Рассмотрим пример:

class LinearSearchDemo {
    public static void main(String args[]) {
        int[] integerArray = {800, 345, 977, 40, 12, -183, 234, 15};
        int elementToFind = 234;
        System.out.println("Element " + elementToFind + " found, index: " + linerSearch(integerArray, elementToFind));
    }

    public static int linerSearch(int[] integerArray, int key) {
        int arraySize = integerArray.length;
        for (int i = 0; i < arraySize; i++) {
            if (integerArray[i] == key) {
                return i;
            }
        }
        return -1;
    }
}

В данном случае происходит следующее:

1. В методе linearSearch мы принимаем массив и искомое значение
2. Циклом начинаем перебирать элементы массива
3. Сравниваем 234 и 800 – получаем false
4. Сравниваем 234 и 345 – получаем false
5. Сравниваем 234 и 977 – получаем false
6. Сравниваем 234 и 40 – получаем false
7. Сравниваем 234 и 12 – получаем false
8. Сравниваем 234 и -183 – получаем false
9. Сравниваем 234 и 234 – получаем true
10. Возвращаем индекс элемента – 6

Худший случай, когда искомого элемента нет в массиве – в этом случае – мы перебираем все элементы. Т.е. сложность линейная – O(n).

Бинарный поиск:

Рассмотрим следующий пример:

class BinarySearchDemo {
    public static void main(String args[]) {
        int[] integerArray = {-183, 12, 15, 40, 234, 345, 800, 977800, 345, 977};
        int elementToFind = 977800;
        System.out.println("Element " + elementToFind + " found, index: " + binarySearch(integerArray, elementToFind, 0, integerArray.length - 1));
    }

    public static int binarySearch(int[] sortedIntegerArray, int elementToFind, int low, int high) {
        if (low > high) {
            return -1;
        }

        int mid = low + (high - low) / 2;

        if (elementToFind < sortedIntegerArray[mid]) { 
            return binarySearch(sortedIntegerArray, elementToFind, low, mid - 1); 
        } else if (elementToFind > sortedIntegerArray[mid]) {
            return binarySearch(sortedIntegerArray, elementToFind, mid + 1, high);
        } else {
            return mid;
        }
    }
}

В данном примере происходит следующее:

1. В методе binarySearch мы принимаем упорядоченный (отсортированный) массив целых чисел.
2. Проверяем, чтобы low был меньше high (low = 0, high = 9) – получаем false
3. Получаем середину массива – 234
4. Сравниваем 234 и искомым значением 977800 – 977800 больше.
5. Отсекаем левую часть массива и получаем новые low – 5 и high – 9.
6. Новая медиана – 977800
7. Попадаем в условие else – возвращаем индекс 7.

Наиболее важным, при выборе алгоритма, должно быть понимание того, как он работает и какие имеет сильные и слабые стороны.

Выбор структуры данных и алгоритма

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

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

Использовать только время вычислений для определения эффективности алгоритма – не совсем корректно, потому что это крайне зависит от “железа” и объёма данных. Поэтому, принято использовать понятие сложности алгоритма.

• сложность по памяти – как много памяти потребуется для вычислений
• сложность по времени – как долго мы будем проводить вычисления

Обе эти сложности крайне зависят от входных данных. Обычно, они обозначаются, как n.

Предположим, что у нас есть некоторый массив целых чисел [10,6,4,23,87,1,12,1004] и мы хотим получить сумму всех элементов массива.

class IntegerArraySumDemo {
    public static void main(String[] args) {
        int [] integerArray = {10,6,4,23,87,1,12,1004};
        int sum = 0;

        for (int i = 0; i < integerArray.length; i++) {
            sum+= integerArray[i];
        }

        System.out.println(sum);
    }
}

В данном случае, количество операция напрямую зависит от количества элементов в массиве. Т.е. если у нас 10 элементов – мы должны получить доступ к массиву и выполнить операцию сложения 10 раз. Если 100 элементов – 100 раз.
Такая сложность, называется линейной и обозначается O(n).

В качестве следующего примера, рассмотрим случай, когда нам необходимо получить доступ к элементу массива по индексу:

class GetIntegerArrayElementByIndex {
    public static void main(String[] args) {
        int[] integerArray = {10, 6, 4, 23, 87, 1, 12, 1004};
        int indexOfRequiredElement = 5;
        
        if (indexOfRequiredElement < integerArray.length) {
            int element = integerArray[indexOfRequiredElement];
            System.out.println(element);
        }
    }
}

В данном случае, независимо от количества элементов в массиве мы выполняем фиксированное количество операций – если говорить грубо, то это 3 операции (проверка индекса, получение элемента по индексу, вывод в консоль). Это количество операций останется таким же и при 100 элементах в массиве, и при 1000000.
Такая сложность называется константной и обозначается O(1).

Стоит отметить, что если количество операций всегда будет 100, то всё равно обозначение будет O(1).
А если мы сложность O(10n), то финальное обозначение будет O(n). Это называется упрощением O-нотации.

Примеры временной сложности

Предположим, что у нас есть компания. В ней есть департаменты  (уникальное имя) и сотрудники (не уникальные имена). И сотрудники и департаменты имеют идентификатор (уникальный) и детальную информацию. Сущности упорядочены по имени. Мы можем вбить в поиск только один параметр в поиск – имя. И в нашей системе периодически происходят сбои (то поиск полетит, то сортировка).

• O (1) – поиск детальной информации департамента по имени. Так как мы точно знаем, что имя департамента уникально, то вбив в поиск имя департамента – мы получим все данные по нему.
• O (1) лучший случай – мы ищем сотрудника по имени и первый в списке сотрудник оказывается тем, который нам нужен.
• O (n) – поиск детальной информации сотрудника по имени. Сортировка поломалась. В худшем случае в нашей системе только сотрудники и все сотрудники имеют одинаковые имена (мир Эдуардов). В этом случае мы напрямую зависим от количества сотрудников в системе. Нам придётся пройтись по всем сотрудникам и сравнивать по идентификатору и искать детальную информацию.
• O (log n) – у нас сломался поиск и мы просто видим страницы с сотрудниками и департаментами. Поиск по имени Кирилл. Допустим, у нас 100 страниц, на каждой из которых 50 сотрудников/департаментов. Упорядоченность по имени сохраняется. Мы открываем страницу 51 и смотрим первую запись и видим, что это Олег. Это означает, что страницы 51 – 100 точно не подходят. Мы переходим на страницу 25 – первая запись – Игорь. Отбрасываем страницы 1-25. Открываем страницу 13 и первое имя Кирилл с нужным нам идентификатором.

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

http://bigocheatsheet.com/

На этом мы заканчиваем обзор структур данных и алгоритмов.