C - Как реализовать структуру данных Set?

Question

Есть ли какой-нибудь хитрый способ реализовать заданную структуру данных (набор уникальных значений) в C? Все элементы в наборе будут одного типа, и там будет огромная оперативная память.

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

Answer 1

Существует несколько способов реализации функциональности set (и map), например:

• древовидный подход (упорядоченный обход)
• подход, основанный на хеше (неупорядоченный обход)

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

Остерегайтесь преимуществ и недостатков подходов, основанных на хэше или на основе деревьев.

Вы можете создать хеш-набор (особый случай хеш-таблиц ) указателей на hashable POD s, с цепочкой , внутренне представлен в виде массива фиксированных размеров сегментов hashables , где:

• все hashables в ведре имеют одинаковое значение хеша
• блок может быть реализован в виде динамического массива или связанного списка хэшиблей
• a hashable ' хэш-значение используется для индексации в массиве сегментов (индексированный по хэш-значениям массив)
• один или несколько из хеш-символов , содержащихся в хеш-наборе, могут быть (указатель на) другого хеш-набора или даже на сам хеш-набор (т. Е. возможно )

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

Вы должны реализовать:

• хэш-функция для хешируемого типа
• функция равенства для типа, используемого для проверки того, равны или нет два хешла
• функциональность хэш-набора contains / insert / remove.

Вы также можете использовать открытую адресацию в качестве альтернативы ведению и управлению группами.

Answer 2

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

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

Этот подход требует определенного порядка элементов набора и значений ключей на карте.

Я не уверен, как вы будете управлять набором, который может содержать себя, используя двоичные деревья, если вы ограничите членство в наборе четко определенными типами в C ... сравнение между такими конструкциями может быть проблематичным. Вы могли бы сделать это достаточно легко в C ++, однако.

Answer 3

Если максимальное количество элементов в наборе (количество элементов базового типа данных) достаточно мало, вы можете рассмотреть возможность использования простого старого массива битов (или как вы их называете на своем любимом языке).

Тогда у вас есть простая проверка на членство в наборе: бит n равен 1, если элемент n находится в наборе. Вы даже можете посчитать «обычные» члены от 1 и сделать бит 0 равным 1, если набор содержит сам себя.

Этот подход, вероятно, потребует какой-то другой структуры данных (или функции) для перевода из типа данных элемента в позицию в битовом массиве (и обратно), но он выполняет операции базового набора (объединение, пересечение, тест членства , разница, вставка, удаление, принуждение) очень очень легко. И он подходит только для относительно небольших наборов, вы не захотите использовать его для наборов 32-разрядных целых чисел, я не думаю.

Answer 4

Способ получения универсальности в C - void *, так что вы все равно будете использовать указатели, а указатели на разные объекты уникальны. Это означает, что вам нужна хеш-карта или двоичное дерево, содержащее указатели, и это будет работать для всех объектов данных.

Недостатком этого является то, что вы не можете вводить значения самостоятельно. Вы не можете иметь набор, содержащий значение 5; Вы должны присвоить 5 переменной, что означает, что она не будет совпадать со случайной 5. Вы можете ввести ее как (void *) 5, и для практических целей это, вероятно, будет работать с маленькими целыми числами, но если ваши целые числа могут попасть в большие достаточно размеров, чтобы конкурировать с указателями, вероятность провала очень мала.

Также это не работает со строковыми значениями. Учитывая char a[] = "Hello, World!"; char b[] = "Hello, World!";, набор указателей найдет a и b разными. Возможно, вы захотите хешировать значения, но если вас беспокоит коллизия хешей, вам следует сохранить строку в наборе и выполнить strncmp(), чтобы сравнить сохраненную строку со строкой проверки.

(Есть аналогичные проблемы с числами с плавающей точкой, но попытка представлять числа с плавающей точкой в ​​наборах - плохая идея).

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