Множества

Как устроено множество

Множество - это математическая структура, где каждый элемент либо есть, либо его нету.

Что должно уметь делать множество:

добавлять элемент
проверять наличие элемента
удалять элемент

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

Придумаем какую-нибудь функцию которая сопоставляет каждому элементу какое-либо небольшое число
Вычислим функцию от элемента
Положим элемент в список с номером, равным значению фуекции

Способ 1: Завести массив где в ячейку с индексом равным числу которое мы кладем класть boolean переменную true что такое число есть. При удалении менять на false. Но тогда если множество будет большим это будет есть большое количество памяти а если таких множеств несколько то съест еще больше.

Способ 2: Чтобы поместить большое количество элементов в сравнительно небольшой массив нужно сопоставить каждому элементу какое-либо небольшое число. Для этого сформируем соответсвующую функцию.

Пример функции добавления для чисел

Функция - последняя цифра числа $X (F(X) = X \% 10)$ . Функция которая переводит большие числа в маленькие - хеш функция.
Вычислим функцию от элемента.
Положим элемент в список с номером, равным значению функции.

Например, наша функция преобразует число 137 -> 7 и 17 -> 7. Такая ситуация называется коллизией. Если мы будем класть в ячейку true/false то когда мы получим число 137 мы положим в ячейку с номером 7 флаг true и когда нас запросят узнать есть ли в множестве число 17 мы скажем что да а это неверно.

Одним из решений этой проблемы - класть в ячейку не флаг а само число. Но в таком виде множество не может одновременно хранить в себе значения и 137 и 17 и т.д.

Решением стало - завести список для всех чисел которые имеют одинаковый хеш.

Если у нас множество длины N и внем лежит K элементов, то мы можем перебрать все элементов за N + K. Мы будем идти по всем спискам пока список пустой мы его пропускаем, а как только обнаруживаем непустой список у нас запускается внутренний цикл проходит по всем элементам и их возвращает.

Если мы решим напечатать значения Set'a, то оно выводся в произвольном порядке (в порядке возрастания значения хеш функции).

Для того чтобы удалить элемент мы сначала находим значение хеш функции находим ячейку с этим знаением и в найденном списке находим нужный элемент. Удаление-1: мы перемещаем элементы на 1 позицию влево, начиная с позиции того элемента который хотим удалить и последний элемент удаляем. Удаление-2: копируем последний элемент на место элемента который удаляем и удаляем самый последний это возможно когда не важен порядок элементов. Удаление элемента происходит $O(1)$ а его поиск за $O(K/N)$ .

public class MySet {

    int setSize = 10;
    int[][] mySet = new int[setSize][];


    public void add(int x) {
        int[] xSet = mySet[x % 10];
        if (xSet == null) {
            mySet[x % 10] = new int[]{x};
        } else {
            mySet[x % 10] = ArrayUtils.add(xSet, x);
        }
    }

    @Override
    public String toString() {
        return "MySet{" +
                "setSize=" + setSize +
                ", mySet=" + Arrays.toString(mySet) +
                '}';
    }

    public boolean find(int x) {
        for (int now : mySet[x % 10]) {
            if (now == x) {
                return true;
            }
        }
        return false;
    }

    public void delete(int x) {
        int[] xList = mySet[x % 10];
        for (int i = 0; i < xList.length; i++) {
            int now = xList[i];
            if (now == x) {
                xList[i] = xList[xList.length - 1];
                mySet[x % 10] = ArrayUtils.remove(xList, xList.length - 1);
                return;
            }
        }
    }
}

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

$F(X) = X \% setSize$ - хеш функция

$MySet$ - хеш таблица

Совпадение значений хеш-функции для разных параметров - коллизия.

Что можно эффективно хранить в множестве

Эффективно можно хранить только неизменяемые объекты.
Для неизменяемых объектов можно посчитать значение хеш-функции при их создании
Хеш функция должна давать равномерное распределение

Амортизированная сложность

Слишком большой размер - ест много памяти $O(N)$

Слишком маленький размер - большой коэфициент заполнения и медленный поиск и удаление $O(K/N)$

Хочется иметь разумный баланс, например, коэфициент заполнения не больше единицы (т.е. $K<=N$ ) Тогда все операции в среднем будут занимать $O(1)$

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

Амортизированная сложность - это среднее время выполнения опреации (условно).

У нас амортизированная сложность операции $O(1)$ - всего было N операций и суммарно на это ушло $O(N)$ .

В худшем случае отдельная операция выполняется за $O(N)$ - может не подходить для систем реального времени.

Примеры задач

Задача 1.

Переберем число А за $O(N)$ . Переберем число B за $O(N)$ . Если их сумма равна X, то вернем эту пару.

Решение 1 (неправильное)

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

public static int[] findTwoDigitBySum(int[] nums, int sum) {
    for (int a : nums) {
        for (int b : nums) {
            if (a + b == sum) {
                return new int[]{a, b};
            }
        }
    }
    return new int[]{0, 0};
}

Решение (исправленное)

public static int[] findTwoDigitBySum(int[] nums, int sum) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == sum) {
                return new int[]{nums[i], nums[j]};
            }
        }
    }
    return new int[]{0, 0};
}

Задача 2

Дан словарь из N слов, длина каждого не превосходит K. В записи каждого из M слов текста (каждое длиной до K) может быть пропущена одна буква. Для каждого слова сказать, входит ли оно (возможно, с одной пропущеной буквой) в словарь.

Смотрите также: