Рубрики

Разреженный набор

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

  1. вставка
  2. делеция
  3. Поиск
  4. Очистка / Удаление всех элементов.

Одним из решений является использование самобалансирующегося бинарного дерева поиска, такого как красно-черное дерево, дерево AVL и т. Д. Временная сложность этого решения для вставки, удаления и поиска составляет O (Log n).

Мы также можем использовать хеширование. При хешировании временная сложность первых трех операций составляет O (1). Но временная сложность четвертой операции составляет O (n).

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

Разреженный набор превосходит все BST, хеширование и битовый вектор. Мы предполагаем, что нам дан диапазон данных (или максимальное значение, которое может иметь элемент) и максимальное количество элементов, которые могут быть сохранены в наборе. Идея состоит в том, чтобы поддерживать два массива: разреженный [] и плотный [].

dense[]   ==> Stores the actual elements
sparse[]  ==> This is like bit-vector where 
              we use elements as index. Here 
              values are not binary, but
              indexes of dense array.
maxVal    ==> Maximum value this set can 
              store. Size of sparse[] is
              equal to maxVal + 1.
capacity  ==> Capacity of Set. Size of sparse
              is equal to capacity.  
n         ==> Current number of elements in
              Set.

insert (x): пусть x будет элементом для вставки. Если x больше maxVal или n (текущее количество элементов) больше емкости, мы возвращаемся.
Если ни одно из вышеприведенных условий не выполняется, мы вставляем x в density [] с индексом n (положение после последнего элемента в индексированном массиве на основе 0), увеличиваем n на единицу (текущее количество элементов) и сохраняем n (индекс x в плотный []) в разреженном [x].

search (x): для поиска элемента x мы используем x в качестве индекса в sparse []. Значение sparse [x] используется в качестве индекса в density []. И если значение density [sparse [x]] равно x, мы возвращаем плотность [x]. Иначе мы вернем -1.

delete (x): чтобы удалить элемент x, мы заменяем его последним элементом в density [] и обновляем индекс последнего элемента в sparse []. Наконец, уменьшаем n на 1.

clear (): установить n = 0.

print (): мы можем напечатать все элементы, просто пройдя плотную [].

Иллюстрация:

Let there be a set with two elements {3, 5}, maximum
value as 10 and capacity as 4. The set would be 
represented as below.

Initially:
maxVal   = 10  // Size of sparse
capacity = 4  // Size of dense
n = 2         // Current number of elements in set

// dense[] Stores actual elements
dense[]  = {3, 5, _, _}

// Uses actual elements as index and stores
// indexes of dense[]
sparse[] = {_, _, _, 0, _, 1, _, _, _, _,}

'_' means it can be any value and not used in 
sparse set


Insert 7:
n        = 3
dense[]  = {3, 5, 7, _}
sparse[] = {_, _, _, 0, _, 1, _, 2, _, _,}

Insert 4:
n        = 4
dense[]  = {3, 5, 7, 4}
sparse[] = {_, _, _, 0, 3, 1, _, 2, _, _,}

Delete 3:
n        = 3
dense[]  = {4, 5, 7, _}
sparse[] = {_, _, _, _, 0, 1, _, 2, _, _,}

Clear (Remove All):
n        = 0
dense[]  = {_, _, _, _}
sparse[] = {_, _, _, _, _, _, _, _, _, _,}

Ниже приведена реализация C ++ вышеуказанных функций.

/ * AC-программа для реализации Sparse Set и ее операций * /
#include<bits/stdc++.h>

using namespace std;

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

class SSet

{

    int *sparse;   // Хранить индексы актуальных элементов

    int *dense;    // Для хранения актуальных заданных элементов

    int n;         // Текущее количество элементов

    int capacity;  // Емкость набора или размер узла []

    int maxValue;  / * Максимальное значение в наборе или размер

                     разреженный [] * /

  

public:

    // Конструктор

    SSet(int maxV, int cap)

    {

        sparse = new int[maxV+1];

        dense  = new int[cap];

        capacity = cap;

        maxValue = maxV;

        n = 0;  // Нет элементов изначально

    }

  

    // Деструктор

    ~SSet()

    {

        delete[] sparse;

        delete[] dense;

    }

  

    // Если элемент присутствует, возвращает индекс

    // элемент в плотном []. Остальное возвращает -1.

    int search(int x);

  

    // Вставляет новый элемент в набор

    void insert(int x);

  

    // Удаляет элемент

    void deletion(int x);

  

    // Печатает содержимое набора

    void print();

  

    // Удаляет все элементы из набора

    void clear() { n = 0; }

  

    // Находит пересечение этого множества с s

    // и возвращает указатель на результат.

    SSet* intersection(SSet &s);

  

    // Функция для нахождения объединения двух множеств

    // Сложность времени-O (n1 + n2)

    SSet *setUnion(SSet &s);

};

  
// Если x присутствует в множестве, то возвращает индекс
// этого в плотном [], иначе возвращает -1.

int SSet::search(int x)

{

    // искомый элемент должен находиться в диапазоне

    if (x > maxValue)

        return -1;

  

    // Первое условие проверяет, что 'x'

    // в пределах 'n' в этом наборе и втором

    // условие говорит нам, что оно присутствует в

    // структура данных.

    if (sparse[x] < n && dense[sparse[x]] == x)

        return (sparse[x]);

  

    // Не найден

    return -1;

}

  
// Вставляет новый элемент в набор

void SSet::insert(int x)

{

    // Угловые случаи, х не должно быть вне

    // диапазон, плотный [] не должен быть полным и

    // х уже не должно быть

    if (x > maxValue)

        return;

    if (n >= capacity)

        return;

    if (search(x) != -1)

        return;

  

    // Вставка в массив-плотных [] по индексу 'n'.

    dense[n] = x;

  

    // Отображение в массив sparse [].

    sparse[x] = n;

  

    // Увеличиваем количество элементов в наборе

    n++;

}

  
// Функция, которая удаляет 'x', если присутствует в этих данных
// структура, иначе она ничего не делает (просто возвращает).
// Удаляя «x», мы удаляем «x» из этого набора.

void SSet::deletion(int x)

{

    // Если х нет

    if (search(x) == -1)

        return;

  

    int temp = dense[n-1];  // Взять элемент с конца

    dense[sparse[x]] = temp;  // Перезаписать.

    sparse[temp] = sparse[x]; // Перезаписать.

  

    // Поскольку один элемент был удален, мы

    // уменьшаем n на 1.

    n--;

}

  
// печатает содержимое набора, которое также является содержимым
// плотного []

void SSet::print()

{

    for (int i=0; i<n; i++)

        printf("%d ", dense[i]);

    printf("\n");

}

  
// Функция для поиска пересечения двух множеств
SSet* SSet::intersection(SSet &s)
{

    // Емкость и максимальное значение набора результатов

    int iCap    = min(n, s.n);

    int iMaxVal = max(s.maxValue, maxValue);

  

    // Создать набор результатов

    SSet *result = new SSet(iMaxVal, iCap);

  

    // Находим меньшее из двух множеств

    // Если этот набор меньше

    if (n < s.n)

    {

        // Поиск каждого элемента этого набора в 's'.

        // Если найден, добавить его в результат

        for (int i = 0; i < n; i++)

            if (s.search(dense[i]) != -1)

                result->insert(dense[i]);

    }

    else

    {

        // Поиск каждого элемента 's' в этом наборе.

        // Если найден, добавить его в результат

        for (int i = 0; i < s.n; i++)

            if (search(s.dense[i]) != -1)

                result->insert(s.dense[i]);

    }

  

    return result;

}

  
// Функция для нахождения объединения двух множеств
// Сложность времени-O (n1 + n2)
SSet* SSet::setUnion(SSet &s)
{

    // Находим емкость и максимальное значение для результата

    // устанавливать.

    int uCap    = s.n + n;

    int uMaxVal = max(s.maxValue, maxValue);

  

    // Создать набор результатов

    SSet *result =  new SSet(uMaxVal, uCap);

  

    // Пройдите первый набор и вставьте все

    // элементы этого в результате.

    for (int i = 0; i < n; i++)

        result->insert(dense[i]);

  

    // Пройдите второй сет и вставьте все

    // элементы этого в результате (Обратите внимание, что разреженные

    // set не вставляет запись, если она уже есть

    // настоящее время)

    for (int i = 0; i < s.n; i++)

        result->insert(s.dense[i]);

  

    return result;

}

  

  
// Драйвер программы

int main()

{

    // Создаем набор set1 с емкостью 5 и макс.

    // значение 100

    SSet s1(100, 5);

  

    // Вставляем элементы в набор set1

    s1.insert(5);

    s1.insert(3);

    s1.insert(9);

    s1.insert(10);

  

    // Печать элементов в структуре данных.

    printf("The elements in set1 are\n");

    s1.print();

  

    int index = s1.search(3);

  

    // переменная 'index' хранит индекс числа до

    // быть найденным

    if (index != -1)  // 3 существует

        printf("\n3 is found at index %d in set1\n",index);

    else            // 3 не существует

        printf("\n3 doesn't exists in set1\n");

  

    // Удалить 9 и напечатать set1

    s1.deletion(9);

    s1.print();

  

    // Создать набор с емкостью 6 и максимальным значением

    // 1000

    SSet s2(1000, 6);

  

    // Вставить элементы в набор

    s2.insert(4);

    s2.insert(3);

    s2.insert(7);

    s2.insert(200);

  

    // Набор для печати 2.

    printf("\nThe elements in set2 are\n");

    s2.print();

  

    // Печать пересечения двух множеств

    SSet *intersect = s2.intersection(s1);

    printf("\nIntersection of set1 and set2\n");

    intersect->print();

  

    // Печать объединения двух наборов

    SSet *unionset = s1.setUnion(s2);

    printf("\nUnion of set1 and set2\n");

    unionset->print();

  

    return 0;

}

Выход :

The elements in set1 are
5 3 9 10 

3 is found at index 1 in set1
5 3 10 

The elements in set2 are-
4 3 7 200 

Intersection of set1 and set2
3 

Union of set1 and set2
5 3 10 4 7 200 

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

союз ():
1) Создать пустой разреженный набор, скажем, результат.
2) Пройдите первый набор и вставьте все его элементы в результат.
3) Пройдите второй набор и вставьте в него все его элементы (обратите внимание, что разреженный набор не вставляет запись, если она уже присутствует)
4) Вернуть результат.

пересечение ():
1) Создать пустой разреженный набор, скажем, результат.
2) Пусть меньший из двух заданных наборов будет первым, а большой — вторым.
3) Рассмотрите меньшее множество и ищите каждый его элемент за секунду. Если элемент найден, добавьте его в результат.
4) Вернуть результат.

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

Ссылки:
http://research.swtch.com/sparse
http://codingplayground.blogspot.in/2009/03/sparse-sets-with-o1-insert-delete.html

Эта статья предоставлена Rachit Belwariar . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Разреженный набор

0.00 (0%) 0 votes