📈 Big O Notation: Сложность алгоритмов

🔵 O(1) — Константное время
Константное время выполнения означает, что время выполнения операции не зависит от размера входных данных. Это как мгновенный доступ к элементу массива по индексу. Независимо от того, сколько данных в массиве, операция займёт одно и то же время.

🔵 O(n) — Линейное время
Линейная сложность указывает на то, что время выполнения алгоритма растёт пропорционально количеству элементов. Поиск элемента в LinkedList — классический пример. Чтобы найти нужный элемент, вам придётся пройти весь список, начиная с головы, что займёт линейное время, если искомый элемент находится в конце.

🔵 O(log n) — Логарифмическое время
В логарифмических алгоритмах задача сокращается на каждом шаге вдвое. Пример — бинарный поиск в отсортированном массиве. На каждом шаге вы делите массив пополам, и продолжаете поиск в нужной половине. Это значительно быстрее, чем линейный поиск.

🔵 O(n^2) — Квадратичное время
В алгоритмах с квадратичной сложностью каждый элемент сравнивается с каждым другим. Примером является сортировка пузырьком (Bubble Sort), где алгоритм многократно сравнивает и обменивает элементы местами, что приводит к квадратичному времени выполнения при увеличении числа элементов.

🔵 O(n^3) — Кубическое время
Кубическая сложность встречается в задачах с тройными вложенными циклами. Пример — умножение матриц, где каждый элемент одной матрицы должен быть умножен на каждый элемент другой, что приводит к тройным вложенным операциям.

🔵 O(n log n) — Линейно-логарифмическое время
Линейно-логарифмическая сложность характерна для более продвинутых алгоритмов сортировки, таких как быстрая сортировка (QuickSort) или сортировка слиянием (MergeSort). Эти алгоритмы делят массив на части и сортируют их, что делает их более эффективными по сравнению с квадратичными.

🔵 O(2^n) — Экспоненциальное время
Экспоненциальная сложность наблюдается в рекурсивных алгоритмах, таких как вычисление чисел Фибоначчи без мемоизации. На каждом шаге создаётся две новые ветви вычислений, что приводит к экспоненциальному росту времени выполнения с увеличением входных данных.

🔵 O(n!) — Факториальное время
Факториальная сложность возникает в задачах, связанных с вычислением всех возможных перестановок или комбинаций. Например, задача генерации всех перестановок строки: с увеличением длины строки число возможных комбинаций возрастает факториально.

🔵 O(√n) — Время квадратного корня
Этот тип сложности встречается, например, в алгоритмах поиска делителей числа или проверки на простоту. Например, чтобы проверить, является ли число простым, достаточно проверить делители до его квадратного корня, что сокращает количество операций по сравнению с линейным подходом.

📖 Обзор книги «Грокаем алгоритмы», Адитья Бхаргава

Направление: #proglib_algorithms
Уровень: #proglib_junior

Автор применяет уникальный визуальный подход, с помощью которого объясняет базовые концепции, такие как сортировка, рекурсия, алгоритм Дейкстры, и многие другие. Благодаря большому количеству иллюстраций и практическим примерам, книга превращается в практическое руководство, особенно полезное для тех, кто только начинает своё знакомство с алгоритмами. Все примеры адаптированы под Python 3, что делает их актуальными для современных разработчиков.

💬 Что говорят люди:

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

➕ Плюсы:

- Иллюстрации всё решают — если вам сложно понять текстовое объяснение, то более 400 наглядных схем точно помогут понять сложные алгоритмы.
- Понятно даже без математики — никакой сложной терминологии и математических уравнений. Бхаргава берёт сложные темы и объясняет их простым языком, делая алгоритмы доступными даже тем, кто не любит математику​.
- Практичность на первом месте — каждый алгоритм сопровождается кодом на Python 3, что помогает сразу применять изученное в реальных задачах​.

➖ Минусы:

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

🖊 Об авторе:

Адитья Бхаргава — опытный инженер-программист с большим стажем работы в ведущих IT-компаниях. Он известен своим умением объяснять сложные технические темы простым и понятным языком, что делает его книги популярными среди программистов любого уровня.

Скидка 25% по промокоду: proglib

Купить книгу

⚡️ Как избавиться от задержек и сделать систему быстрее

1️⃣ Кэширование

Временное хранение часто используемых данных в памяти для сокращения времени доступа.

▪️ Чем полезно:
- Получение данных из кэша (например, Redis, Memcached) гораздо быстрее, чем запросы к базе данных.
- Кэширование статических ресурсов (изображения, CSS, JS) снижает необходимость многократного запроса их с исходного сервера.

2️⃣ Распределение нагрузки

Распределение входящего сетевого трафика между несколькими серверами для предотвращения перегрузки одного сервера.

▪️ Чем полезно:
- Балансировка нагрузки предотвращает перегрузку одного сервера, что может замедлить отклик.
- Обеспечивает отказоустойчивость, гарантируя обработку запросов даже при выходе некоторых серверов из строя.

3️⃣ Асинхронная обработка

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

▪️ Чем полезно:
- Пользователям не нужно ждать завершения длительных задач (например, отправки электронной почты или обработки изображений).

4️⃣ Разделение данных (шардирование)

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

▪️ Чем полезно:
- Запросы могут выполняться параллельно на нескольких шардах, сокращая время получения данных.
- Распределение нагрузки предотвращает перегрузку одного экземпляра базы данных.

5️⃣ Сети доставки контента (CDA)

Распределенные сети серверов, которые доставляют веб-контент на основе географического расположения пользователя.

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

6️⃣ Оптимизация баз данных

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

▪️ Чем полезно:
- Ускоряет получение данных, позволяя базе данных находить записи без сканирования всех таблиц.

7️⃣ Минимизация сетевых переходов

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

▪️ Чем полезно:
- Каждый сетевой переход добавляет задержку; их минимизация ускоряет передачу данных.

8️⃣ Параллельная и конкурентная обработка

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

▪️ Чем полезно:
- Параллельное выполнение задач позволяет обрабатывать данные быстрее за счёт разделения работы на несколько потоков.
- Более эффективное использование ресурсов процессора, что снижает задержки при выполнении сложных операций.

9️⃣ Предварительная и предсказательная загрузка

Предугадывание будущих запросов данных и их предварительная загрузка.

▪️ Чем полезно:
- Данные уже доступны, когда они запрашиваются, устраняя задержки при получении.
- Особенно эффективно в приложениях с предсказуемыми шаблонами доступа.

⚙️ Агрегация и композиция: два подхода к организации объектов

Когда мы проектируем классы, важно правильно выстраивать отношения между ними. Два ключевых способа организации объектов — это агрегация и композиция.

▪️ Агрегация представляет собой "слабую" связь, где объекты могут существовать отдельно друг от друга. Она подходит, когда один объект использует другой, но не зависит от его существования.

▪️ Композиция — это "сильная" связь, при которой объекты не могут существовать независимо. Это отношение "часть-целое", когда одна сущность полностью зависит от другой.

Оба этих подхода помогают создавать гибкую и поддерживаемую архитектуру приложений. Правильный выбор типа отношения зависит от контекста задачи и желаемой структуры взаимодействия объектов.

🔜 Подробнее про каждый подход разберём в следующих постах.

ℹ️ Агрегация: что это и когда использовать?

Агрегация — это тип отношения между классами, при котором один класс "владеет" экземпляром другого, но их жизненные циклы не зависят друг от друга. Это «слабое» отношение, так как объект одного класса может существовать независимо от объекта другого.

Пример:

class Engine {
    void start() {
        System.out.println("Двигатель запущен");
    }
}

class Car {
    private Engine engine;

    Car(Engine engine) {
        this.engine = engine;
    }

    void startCar() {
        engine.start();
        System.out.println("Машина поехала");
    }
}

public class Main {
    public static void main(String[] args) {
        Engine engine = new Engine(); // Двигатель может существовать отдельно
        Car car = new Car(engine);
        car.startCar();
    }
}

🔹 В этом примере класс Car агрегирует объект Engine, но двигатель может существовать сам по себе, вне машины.

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

ℹ️ Композиция: что это и когда использовать?

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

Пример:

class Heart {
    void beat() {
        System.out.println("Сердце бьется");
    }
}

class Human {
    private final Heart heart;

    Human() {
        this.heart = new Heart(); // Сердце создаётся вместе с человеком
    }

    void live() {
        heart.beat();
        System.out.println("Человек живёт");
    }
}

public class Main {
    public static void main(String[] args) {
        Human human = new Human();
        human.live();
    }
}

🔹 В этом примере класс Human композирует объект Heart, и сердце не может существовать вне человека.

Композицию стоит использовать, когда объекты должны быть тесно связаны и уничтожаться вместе. Например, птица и её крылья — без птицы существование крыльев не имеет смысла.

⌛ Как отслеживать изменения в файловой системе в реальном времени

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

🔹 Возможные сценарии использования:
- Отслеживание действий пользователя.
- Мониторинг изменений в конфигурационных файлах для их динамической перезагрузки.
- Автоматическая обработка данных, как только они поступают в систему (например, новые изображения или документы).
- Логирование и анализ активности в системных директориях.

import java.nio.file.*;
import java.io.IOException;

public class DirectoryWatcher {
    public static void main(String[] args) throws IOException, InterruptedException {
        WatchService watchService = FileSystems.getDefault().newWatchService();
        Path path = Paths.get("/path/to/watch");
        path.register(watchService, StandardWatchEventKinds.ENTRY_CREATE, 
                                    StandardWatchEventKinds.ENTRY_DELETE, 
                                    StandardWatchEventKinds.ENTRY_MODIFY);

        System.out.println("Monitoring directory: " + path);
        
        while (true) {
            WatchKey key = watchService.take();
            key.pollEvents().forEach(event -> {
                WatchEvent.Kind<?> kind = event.kind();
                System.out.println(kind.name() + ": " + event.context());
            });
            if (!key.reset()) break;
        }
    }
}

WatchService — это механизм мониторинга событий файловой системы. Для его работы регистрируем путь для отслеживания событий с помощью path.register() и указываем тип событий: создание, удаление или модификация.
В бесконечном цикле программа ожидает события с помощью watchService.take(), после чего события обрабатываются через лямбду.
Метод reset() проверяет, можно ли продолжить отслеживание, если нет — цикл завершится.

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

ℹ️ Как устроен под капотом TreeSet?

TreeSet — это коллекция, которая хранит уникальные элементы и автоматически сортирует их в натуральном порядке или по заданному Comparator. Под капотом используется самобалансирующееся красно-черное дерево, которое гарантирует, что добавление, удаление и поиск элементов будут происходить за логарифмическое время. В отличие от HashSet, TreeSet не только предотвращает дублирование элементов, но и поддерживает их упорядоченность.

🔹 Структура TreeSet

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

▪️ Каждый узел содержит ключ и ссылки на дочерние узлы
▪️ Дерево автоматически сбалансировано — максимальная глубина любого пути от корня к листу в два раза меньше самой длинной возможной
▪️ Элементы располагаются в отсортированном порядке по мере добавления, что гарантирует логарифмическую сложность поиска и вставки

🔹 Производительность

▪️ Добавление: При добавлении элемента дерево балансируется, чтобы соблюсти свойства красно-черного дерева. Это обеспечивает сложность добавления O(log n).
▪️ Удаление: Работает схожим образом — дерево ребалансируется, а ссылки между узлами корректируются. Удаление также выполняется за O(log n).
▪️ Поиск: Благодаря сбалансированной структуре, поиск элемента в TreeSet занимает O(log n), что делает его быстрее, чем линейный поиск в несбалансированных структурах.

🔹 Использование памяти

Каждый узел в TreeSet хранит не только ключ, но и ссылки на дочерние узлы (левый и правый). Это создает определенные накладные расходы по памяти, ведь для каждого элемента требуется больше памяти, чем, например, в HashSet, где хранятся лишь сами элементы.

🔹 Преимущества и недостатки

▪️ Преимущества:
- Гарантированный порядок элементов: В отличие от HashSet, TreeSet хранит элементы в отсортированном виде. Это важно, если нужно быстро получать минимальные, максимальные или средние значения без дополнительной сортировки. Также можно извлекать диапазоны значений с помощью методов вроде subSet().
- Навигационные методы: TreeSet предоставляет мощные инструменты для навигации по набору, такие как методы для поиска ближайших элементов (floor(), ceiling()), что делает его удобным для задач с диапазонами данных.
▪️ Недостатки:
- Производительность: Операции в TreeSet медленнее, чем в HashSet.
- Большие накладные расходы по памяти: Для каждого элемента TreeSet требуется хранить дополнительные ссылки на дочерние узлы, что увеличивает потребление памяти.

💡 ReentrantLock vs. Lock

Lock — это интерфейс, предоставляющий базовые методы для управления синхронизацией потоков. Одной из наиболее популярных реализаций этого интерфейса является ReentrantLock, которая предлагает более широкие возможности по сравнению с базовыми реализациями. Разбираемся, в чём различие:

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

🔵 Больше контроля
ReentrantLock даёт больше возможностей управления блокировкой: можно настраивать справедливость (потоки захватывают блокировку по очереди) и использовать неблокирующие методы, такие как tryLock(), чтобы избежать ожидания.

🔵 Управление состоянием
С ReentrantLock блокировку можно вручную освобождать, что полезно при более сложной логике.

🔵 Дополнительные методы
ReentrantLock предоставляет такие полезные методы, как getHoldCount(), чтобы узнать, сколько раз текущий поток захватил блокировку, и isHeldByCurrentThread() для проверки, удерживается ли она этим потоком.

Используйте ReentrantLock, если вам требуется гибкость и контроль над блокировками. Lock подходит для простых случаев синхронизации.

🔥 Свежие обновления GraalVM

Недавно вышли новые демо и руководства для GraalPy и GraalJS, которые помогут легче внедрять многоязычную работу в проектах. Эти улучшения делают работу с Python и JavaScript внутри Java-приложения ещё удобнее и быстрее.

📌 Подробности и примеры можно найти на GitHub и GraalVM.

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

🔗 Шпаргалка: Основы тестирования с JUnit

1️⃣ Добавляем зависимость JUnit

Для Maven:

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter-api</artifactId>
    <version>5.9.3</version>
    <scope>test</scope>
</dependency>

Для Gradle:

testImplementation 'org.junit.jupiter:junit-jupiter-api:5.9.3'

2️⃣ Создаем тестовый класс

Начнем с создания класса для тестирования и метода с аннотацией @Test:

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

public class MyTest {
    @Test
    public void testAddition() {
        int result = 2 + 2;
        assertEquals(4, result); // Проверка, что результат 4
    }
}

3️⃣ Основные аннотации JUnit

- @Test — указывает, что метод является тестом.
- @BeforeEach — выполняется перед каждым тестом (настройка окружения).
- @AfterEach — выполняется после каждого теста (очистка).
- @BeforeAll — выполняется один раз перед всеми тестами (должен быть статическим).
- @AfterAll — выполняется один раз после всех тестов (тоже статический).

Пример использования:

@BeforeEach
public void setUp() {
    // Код инициализации перед каждым тестом
}

@AfterEach
public void tearDown() {
    // Код очистки после каждого теста
}

4️⃣ Основные ассерты (проверки)

- assertEquals(expected, actual) — проверяет равенство значений.
- assertNotEquals(expected, actual) — проверяет неравенство.
- assertTrue(condition) — проверяет, что условие истинно.
- assertFalse(condition) — проверяет, что условие ложно.
- assertNull(object) — проверяет, что объект равен null.
- assertThrows(exception.class, () -> { ... }) — проверяет, что выбрасывается исключение.

5️⃣ Параметризованные тесты

Если нужно протестировать несколько вариантов входных данных, используйте параметризованные тесты:

@ParameterizedTest
@ValueSource(strings = {"abc", "123", "xyz"})
public void testWithParameters(String input) {
    assertNotNull(input);
}

6️⃣ Используйте assertAll() для группировки нескольких проверок в одном тесте

@Test
public void testMultipleAsserts() {
    assertAll(
        () -> assertEquals(4, 2 + 2),
        () -> assertTrue(3 > 1),
        () -> assertNotNull(new Object())
    );
}

7️⃣ Мокирование зависимостей

Для изоляции кода можно использовать библиотеки для мокирования, такие как Mockito:

@Mock
private MyService myService;

@BeforeEach
public void setUp() {
    MockitoAnnotations.initMocks(this);
}

@Test
public void testWithMock() {
    when(myService.getData()).thenReturn("Mock Data");
    assertEquals("Mock Data", myService.getData());
}

8️⃣ Запуск тестов

В IDE тесты можно запускать прямо из тестового класса.
Maven: mvn test.
Gradle: gradle test.