Множество

Быстрое понимание уникальности, принадлежности и операций над наборами

• проверка принадлежности элемента → in set
• получение уникальных значений → множество
• разница наборов (кто есть в A, но нет в B) → множество
• пересечение ролей/прав/фич → множество

Это теория множеств: B ⊇ A

use std::collections::HashSet;
fn main() -> std::io::Result<()> {
    let need = HashSet::from(["read", "write"]);
    let mut user = HashSet::from(["read"]);
    
    if user.is_superset(&need) {
        println!("1. множество user является надмножеством need, т.е. user содержит по крайней мере все значения из need");
    }else{
        println!("1. множество user не входит во множество need");
    }
    
    user.insert("write"); 
    if user.is_superset(&need) {
        println!("2. множество user является надмножеством need, т.е. user содержит по крайней мере все значения из need");
    }
    Ok(())
}

Дизъюнктное объединение множеств вариантов

Если мы хотим понимать почему Rust устроен так (pattern matching, enums, типы), множества помогают.

Например:

• enum — это дизъюнктное объединение множеств вариантов, а каждая функция на enum — это отношение между множества.
• Option<T> = {None} ∪ {Some(x) | x ∈ T}

Если понимаем операции над множествами → легче проектировать типы.

Оптимизация алгоритмов (понимание сложности)

Знание теории множеств → понимание, почему:

• поиск в HashSet → O(1)
• поиск в Vec → O(n)
• разница двух множеств → O(n)
• пересечение — дешево/дорого в зависимости от контейнера

Корректная работа с данными в БД

SQL — это теория множеств.

UNION, INTERSECT, EXCEPT — прямые операции над множествами.

Если понимаете:

• что такое подмножество
• что такое декартово произведение
• что такое отношение

→ вы лучше понимаете JOIN’ы, нормализацию, ключи, индексы.

Например:

JOIN = подмножества декартова произведения, понимаете, как работает запрос под капотом.

Работа с графами

Граф — это структура из двух множеств:

• множество вершин
• множество ребер (каждое ребро — пара из множества вершин)

Формальные спецификации, корректность, тестирование

Множества дают точный язык для описания требований.

Например:

• “Состояния системы — множество, переходы — отношение”

Следить, чтобы состояние системы было корректным.

Валидация состояний и инварианты, это про множества:

• допустимых состояний
• допустимых переходов
• разрешённых комбинаций

Это множество из трёх элементов. Инвариант: система никогда не должна быть “между” состояниями.

#![allow(unused)]
fn main() {
enum State {
    New,
    Pending,
    Done,
}
}

Комбинаторика (часто нужна для оптимизации)

Если вы когда-нибудь оценивали:

• количество вариаций
• сложность перебора
• вероятность ошибки

→ это всё операции над мощностями множеств (размерами наборов данных).