целочисленные множества
(перечитывая Писсанецки)
При работе с разреженными данными часто приходится хранить уникальные индексы элементов. Во всеми нами любом С++ (или в чуть менее нами любимом C#) есть std::set (System.Collections.Generic.HashSet), которые как будто предназначены как раз для решения таких задач.
Однако все становится не столь радужно, когда приходится добавлять элементы в множество несколько раз за итерацию. Становится печально видеть, что вместо полезной нагрузки мы тратим время на вызовы хэш-функции и поиск элементов во множестве.
Предположим, что максимальное значение включаемого целого числа в такое множество известно заранее. Например, это число столбцов в разреженной матрице. В таком случае, можно имитировать множество следующим образом:
Count = 4
Capacity = 10
First = 9
Next = EMPTY | 5 | 1 | EMPTY | EMPTY | NIL | EMPTY | EMPTY | EMPTY | 2
(индексы: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)
Преимущества:
При работе с разреженными данными часто приходится хранить уникальные индексы элементов. Во всеми нами любом С++ (или в чуть менее нами любимом C#) есть std::set (System.Collections.Generic.HashSet), которые как будто предназначены как раз для решения таких задач.
Однако все становится не столь радужно, когда приходится добавлять элементы в множество несколько раз за итерацию. Становится печально видеть, что вместо полезной нагрузки мы тратим время на вызовы хэш-функции и поиск элементов во множестве.
Предположим, что максимальное значение включаемого целого числа в такое множество известно заранее. Например, это число столбцов в разреженной матрице. В таком случае, можно имитировать множество следующим образом:
- EMPTY - целочисленная константа
- NIL - целочисленная константа
- Count - число элементов в множестве
- Capacity - размер множества
- First - первый элемент множества (NIL, если множество пустое)
- Next - вектор целых чисел длиной N. Если значение в векторе:
- Не NIL и не EMPTY, то это значение следующего элемента в множестве
- EMPTY, то такого элемента нет в множестве
- NIL, то это последний элемент в множестве
Count = 4
Capacity = 10
First = 9
Next = EMPTY | 5 | 1 | EMPTY | EMPTY | NIL | EMPTY | EMPTY | EMPTY | 2
(индексы: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)
Преимущества:
- Типовые операции не требуют вызова хеш-функции
- Типовые операции (кроме случая, описанного в недостатках) не требуют поиска элемента в дереве значений
- Типовые операции не (де)аллоцируют память
- Как следствие предыдущих пунктов, типовые операции крайне быстры
- Годится только для хранения целых чисел
- Требуется заранее знать максимальное значение хранимого элемента
- Требуется заранее выделить память под вектор Next
- Требуется O(n) действий для удаление элемента