Есть ли какой-либо сложный способ реализации установленной структуры данных (коллекции уникальных значений) в C? Все элементы в наборе будут одного типа и есть огромная оперативная память.C - Как реализовать Установить структуру данных?
Как я знаю, для целых чисел это можно сделать очень быстро'Ничего, используя массивы с индексированными значениями. Но я бы хотел иметь очень общий тип данных Set. И было бы неплохо, если бы набор мог включить себя.
Есть несколько путей реализации набора (и карты) функциональность, например:
С вы упомянули массивы с индексированными значениями, давайте попробуем подход, основанный на хеше, который строит естественно поверх значения -индексный метод массива.
Опасайтесь advantages and disadvantages основанных на хеше или основанных на дереве подходов.
Вы можете создать хэш-набор (частный случай hash-tables) указателей на hashablePOD с, с chaining, внутренне представлена в виде массива фиксированного размера из ведра hashables, где:
с большими объемами памяти в вашем распоряжении, вы можете выбрать размер вашего массива ковшей щедро и, в сочетании с хорошим методом хеширования, резко снизить вероятность collision, достигая практически постоянная работа.
Вы бы реализовать:
contains/insert/remove функциональность.Вы также можете использовать open addressing в качестве альтернативы ведению и управлению ковшими.
Наборы обычно реализуются как некоторые разновидности binary tree. Red black trees имеют хорошую производительность в худшем случае.
Они также могут быть использованы для построения map, чтобы разрешить поиск ключей/значений.
Этот подход требует определенного порядка упорядочивания элементов набора и значений ключа на карте.
Я не уверен, как вы могли бы управлять множеством, который мог бы содержать себя с использованием двоичных деревьев, если вы ограничиваете членство в определенных типах в C ... сравнение таких конструкций может быть проблематичным. Однако вы могли бы сделать это достаточно легко на C++.
Если максимальное количество элементов в наборе (мощность базового типа данных) достаточно мало, вы можете захотеть использовать простой старый массив бит (или то, что вы называете на своем любимом языке).
Затем у вас есть простая проверка принадлежности к члену: бит n равен 1, если элемент n находится в наборе. Вы можете даже считать «обычных» членов от 1 и только сделать бит 0 равным 1, если набор содержит сам.
Этот подход, вероятно, потребует какой-либо другой структуры (или функции) для перевода из типа данных элемента в позицию в битовом массиве (и обратно), но он выполняет операции базового набора (объединение, пересечение, членство тест, разница, вставка, удаление, принуждение) очень просто. И он подходит только для относительно небольших наборов, вы бы не хотели использовать его для наборов 32-битных целых чисел, которые я не предполагаю.
Путь получения универсальности в C равен void *, так что вы все равно будете использовать указатели, а указатели на разные объекты уникальны. Это означает, что вам нужна карта хэша или двоичное дерево, содержащее указатели, и это будет работать для всех объектов данных.
Недостатком этого является то, что вы не можете вводить rvalues самостоятельно. У вас не может быть набора, содержащего значение 5; вам нужно назначить 5 переменной, что означает, что она не будет соответствовать случайному 5. Вы можете ввести ее как (void *) 5, и для практических целей это, скорее всего, будет работать с небольшими целыми числами, но если ваши целые числа могут быть в больших размерах чтобы конкурировать с указателями, это имеет очень небольшую вероятность неудачи.
И это не работает со строковыми значениями. Учитывая char a[] = "Hello, World!"; char b[] = "Hello, World!";, набор указателей найдет a и b будет отличаться. Вероятно, вы захотите хэш-значения, но если вас беспокоят хеш-коллизии, вы должны сохранить строку в наборе и сделать strncmp() для сравнения сохраненной строки с пробной строкой.
(Там же аналогичные проблемы с числами с плавающей точкой, но при попытке представления чисел с плавающей точкой в наборах это плохая идея в первой очереди.)
Таким образом, вы, вероятно, хотите помеченное значение, один тег для любого типа объекта, один для целочисленного значения и один для строкового значения и, возможно, больше для разных значений. Это сложно, но выполнимо.
У меня такой же вопрос здесь: http://stackoverflow.com/questions/2537681/how-to-implement-a-set. Может быть, это помогает! –
... или вопрос на собеседование? – vladr
Бесстыдный плагин: я написал библиотеку B-дерева в памяти в C: http: //ccan.ozlabs.org/info/btree.html. B-дерево выполняет, по существу, ту же роль, что и бинарное дерево относительно множеств. –