Разбираемся в «базовых» алгоритмах для проекта

Kandinsky 2.2

Меня зовут Александр Певненко, я Java developer в СберТехе. Вместе с командой развиваю Platform V DataSpace — BaaS-продукт, обеспечивающий базовые сервисы для работы с данными.

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

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

Поэтому здесь я приведу несколько «базовых» алгоритмов, знание которых помогает мне работать с прицелом на эффективность кода, и дополню примерами на Python и Java.

Общее про алгоритмы

Мне нравится определение Паноса Луридаса: алгоритмы — вещь, которая показывает нам, что делать, чтобы ничего не делать.

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

При этом для понимания алгоритмов не важно, на чём вы пишете. Примеры реализации сейчас есть на любом языке. Чтобы быстро понять тему, достаточно знать хотя бы один язык и помнить основы школьной алгебры, а именно — вопросы уровня «что такое логарифм».

Подсказка для тех, кто не помнит

Это операция, обратная возведению в степень. log₁₀ (100) = 2 — это то, в какую степень нужно возвести 10, чтобы получить 100.

Структуры данных: массив и связанный список

В основе алгоритмов лежат структуры данных — математически подтвержденные, логически реализуемые конструкции, которые чаще всего уже «вшиты» в язык программирования. По сути, они представляют собой способы хранения и организации данных, реализованные с помощью алгоритмов. Ниже опишу два типа структур, которые чаще всего используются нами в работе: массив и связанный список.

Массив — структура, при которой все данные хранятся последовательно. Например, у нас есть ячейки для хранения единицы информации. Каждая имеет свой адрес, и когда мы хотим что-то положить внутрь, то запрашиваем память у компьютера и получаем адрес свободной ячейки.

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

Примеры реализации структур данных на Java:

Массив:

    final int length = 100;
    int[] arr = new int[length];

    //наполним массив нечетными значениями
    for(int i = 0 ; i < arr.length ; i++) {
        arr[i] = 2*i + 1;
    }
    for (int j : arr) {
        System.out.println(j);
    }


    long time = System.nanoTime();
    //вывод на экран элементов массива
    for (int j : arr) {
        System.out.println(j);
    }
    System.out.println("_____________");
    System.out.println("time: " + (System.nanoTime() - time)/1000 + " микросекунд");
    System.out.println("_____________");

Связанный список:

    List<Integer> linkList = new LinkedList<>();

    for(int i = 0 ; i < arr.length ; i++) {
        linkList.add(2*i + 1);
    }

    time = System.nanoTime();
    for (int j : linkList) {
        System.out.println(j);
    }

    System.out.println("_____________");
    System.out.println("time: " + (System.nanoTime() - time)/1000 + " микросекунд");
    System.out.println("_____________");

От структур данных переходим к алгоритмам.

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

Это алгоритм поиска, который работает только в отсортированном списке. На вход отдаём отсортированный список, а на выходе получаем позицию нужного нам элемента, если он присутствует в списке. Проще всего разбирать алгоритм бинарного поиска в сравнении с обычным поиском. Допустим, мы ищем рецепт в кулинарной книге. Помним, что название блюда начинается на букву К. Есть два подхода, как найти нужные данные: долго и муторно листать с буквы А до нужного рецепта или открыть книгу с буквы К и пролистать немного вперёд или назад, чтобы ускорить процесс.

По похожему принципу и работает бинарный поиск. Пусть у нас есть отсортированный массив чисел: 1, 3, 4, 7, 9,16. Чтобы узнать позицию числа 7 методом обычного поиска, начнём счёт с начала: 1, 3, 4 ……. — и только на седьмой раз мы найдём нужную цифру

Чтобы упростить и ускорить этот процесс, используем бинарный поиск. Для этого поделим массив на две части и найдём середину, а затем сравним с искомым числом. Начинаем с середины: 4 больше 7? Нет, значит отбрасываем половину, остаётся только 7, 9, 16. Опять начинаем с середины: 9 больше 7? Да, значит снова делим пополам, только теперь убираем половину справа — 7. Нужное число найдено (позицию предварительно запоминаем).

А теперь представим, что массив состоит из 100, 1000, 10 000 элементов. При обычном подходе на поиск искомого числа может уйти как 100, так и 10 000 попыток. Каждый шаг при бинарном поиске сокращает количество этих попыток вдвое, то есть для поиска n цифр или элементов понадобится log₂n шагов.

Вот так выглядит реализация линейного поиска на Python:

def LinearSearch(lys, element):
    for i in range (len(lys)): 
        if lys[i] == element: 
             return i 
    return -1

А вот так — бинарного поиска на Python:

def BinarySearch(lys, val):
    first = 0 
    last = len(lys)-1
    index = -1
    while (first <= last) and (index == -1): 
        mid = (first+last)//2 
        if lys[mid] == val:
            index = mid
        else: 
            if val < lys[mid] :
            	last = mid -1 
            else :
            	first = mid +1
    return index

Примеры на Java:

Поиск перебором O(n):

public static int linearSearch(int arr[], int elementToSearch) {

    for (int index = 0; index < arr.length; index++) {
        if (arr[index] == elementToSearch)
            return index;
    }
    return -1;
}

Поиск бинарный O(log(n)):

private static int binarySearch(int[] sortedArray, int value, int low, int high) {
    int index = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (sortedArray[mid] < value) {
            low = mid + 1;
        } else if (sortedArray[mid] > value) {
            high = mid - 1;
        } else if (sortedArray[mid] == value) {
            index = mid;
            break;
        }
    }
    return index;
}

«О»-нотация

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

Почему? Допустим, мы ищем число 57 в массиве из 100 чисел. Используя обычный алгоритм, мы затратим около 100 шагов для поиска искомого числа. А в случае с бинарным поиском, который при каждом шаге сокращает нужный массив в два раза:

1. Берём середину от диапазона 1-100: 50 — число не найдено, и оно больше 50.

2. Берём середину от диапазона 50-100: 75 — число не найдено, и оно меньше 75.

3. Берём середину от диапазона 50-75: 62 — число не найдено, и оно меньше 62.

4. Берём середину от диапазона 50-62: 56 — число не найдено, и оно больше 56.

5. Берём середину от диапазона 56-62: 59 — число не найдено, и оно меньше 59.

6. Берём середину от диапазона 56-59: 58 — число не найдено, и оно меньше 58.

7. Берём середину от диапазона 56-58: 57 — искомое число найдено!

Итого нам нужно было 7 операций вместо 100, как в случае с обычным поиском, следовательно, log₂(100) ≈ 7.

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

Для этого используется «О»-нотация O(n), где n — это количество операций, которое предстоит выполнить алгоритму. При этом нотация рассматривает худший сценарий, то есть позволяет определить, что алгоритм не будет работать медленнее O(n).

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

Для примера рассмотрим поиск значения в массиве из 100 отсортированных по возрастанию элементов. Пусть для проверки одного элемента нам потребуется одна миллисекунда. Тогда для обычного поиска линейное время O(n) = 100 мс, для бинарного поиска — логарифмическое время O(log(n)) = 7 мс.

Давайте увеличим количество элементов до 100 000:

• обычный поиск — 100 000 мс = 100 сек = 1 мин 40 сек;

• бинарный поиск — 17 мс.

Ощутимая разница, не так ли?

«О»-нотация — рабочий инструмент для замера производительности кода, который помогает оценить алгоритмическую сложность участка программы. Я использую его для оценки и повышения скорости вызова методов в коде проекта.

Сортировка выбором

Базовые алгоритмы поиска работают только для отсортированных данных. Поэтому переходим к алгоритмам, которые помогут эти данные упорядочить: алгоритмам сортировки. Один из базовых — сортировка выбором.

Пусть у нас есть список рецептов в алфавитном порядке. У каждого рецепта свой рейтинг, и нужно отсортировать список по рейтингу в порядке убывания или возрастания. Самое очевидное решение — пройтись по всему списку, последовательно выбирать рецепты с высокими рейтингами и переносить их в новый пустой список, от наивысшего показателя к низшему. В этом вся суть сортировки выбором: каждый раз мы выбираем новый элемент и кладём его в список отсортированных элементов. В виде Java-кода это может выглядеть так:

public static int linearSearch(int arr[], int elementToSearch) {

    for (int index = 0; index < arr.length; index++) {
        if (arr[index] == elementToSearch)
            return index;
    }
    return -1;
}

Рекурсия

Последний алгоритм, о котором хотелось бы рассказать. Часто тема рекурсии вызывает у программистов смешанные чувства. Кто-то любит её за изящность и компактность решений, кто-то, наоборот, избегает из-за кажущейся сложности. Мне нравится разбирать тему рекурсии на примере поиска книги в коробке. В большой коробке лежат много маленьких. Внутри большинства из них — другие коробки, и только в одной лежит книга. Чтобы найти её, можно:

1. Достать все маленькие коробки и сложить в кучу

2. Открывать коробки поочерёдно.

3. Если внутри маленькой коробки оказывается другая коробка — вернуть её в кучу.

4. Если внутри оказывается книга, то поиск окончен.

Это обычный подход к решению задачи. Его суть — обращаться к куче коробок до тех пор, пока в ней есть объекты.

А вот рекурсивный метод:

1. Проверить каждый предмет в большой коробке.

2. Если внутри коробка, то выполняем шаг 1, то есть возвращаемся к проверке.

3. Если внутри книга — поиск окончен.

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

Для простоты понимания предлагаю посмотреть на код:

Python:

def factorial(n):
    res = 1
    if n == 1 or n == 0:
        return res
    else:
	 res = n*factorial_recursive(n-1)
        return res

Java:

//рекурсия(на примере поиска факториала)

private int fact(int n) {
    int result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * fact(n-1);
    return result;
}

}

Итог: алгоритмы точно не помешают

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

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

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