Что такое простая библиотека C для набора целых множеств?

Question

Мне нужно изменить программу на C, и мне нужно включить набор целых чисел без знака. То есть у меня есть миллионы наборов целых чисел (каждый из этих наборов целых чисел содержит от 3 до 100 целых чисел), и мне нужно хранить их в некоторой структуре, давайте назовем ее каталогом, который может в логарифмическом времени сказать мне, является ли данный целое множество уже существует в каталоге. Единственные операции, которые необходимо определить в каталоге, - это поиск и вставка.

Это было бы легко для языков со встроенной поддержкой полезных структур данных, но я иностранец в Си и, оглядываясь по сторонам, Google (как ни удивительно) не ответил удовлетворительно на мой вопрос. Этот проект выглядит примерно так:

http://uthash.sourceforge.net/

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

Это стандартная, простая проблема, поэтому я надеюсь, что есть стандартное и простое решение.

Answer 1

Это зависит от того, что вы собираетесь делать с данными. Но, может быть, tsearch уже делает то, что вы хотите. Вы также можете создать отсортированный массив для каждого набора и просмотреть значения с помощью bsearch, хотя при вставке производительность может снизиться.

РЕДАКТИРОВАТЬ: Если вы ищете (внешнюю) библиотеку, вы найдете сравнение некоторых реализаций хеш-таблиц C и C ++ здесь . Автор статьи написал реализацию общего заголовка под названием khash . Таким образом, у вас скомпилированный бинарный файл не имеет никаких дополнительных зависимостей.

Answer 2

РЕДАКТИРОВАТЬ: извините, я начал отвечать, потому что это C ++, а не C. Да, тогда вы должны найти свою хэш-функцию и кодировать ее самостоятельно ... так как вы уже знаете среднее измерение набора, это не так так сложно, просто выбери хорошую хеш-функцию! Но вам нужно будет кодифицировать весь набор в одно число, если вы хотите проверить, существует ли уже каталог.

Вы можете попробовать, итеративно хэшируя отдельные числа набора:

int hashcode = initvalue
for (int i = 0; i < 0; ++i)
  hashcode = calc_code(hashcode, number_set[i], i);

таким образом, что хэш-функция зависит от его предыдущего значения, текущего номера и текущего индекса.

А как насчет наборов STL?

#include <set>

int nums[6] = {1,6,34,2,67,41};
set<int> numbers;

for( int i = 0; i < 6; ++i ) numbers.insert(nums[i]);

for( set<int>::const_iterator iter = numbers.begin(); iter != numbers.end(); ++iter )
  cout << *iter << ' ';

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

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

Answer 3

Если я вас правильно понимаю, вы хотите представить наборы целых чисел, которые я не считаю особенно тривиальными.

Первый пункт должен представлять набор целых чисел. Самый простой способ - использовать массив переменного размера, например так:

typedef struct { 
  int size;
  int elems[1];
} intset;

, чем вы можете создать новый набор (с фиксированным количеством элементов) с помощью

intset *newset(int size) 
{ 
  intset *set;
  set = malloc(sizeof(intset) + sizeof(int)*(size-1));
  if (set) set->size = size;
  return set;
}

и сохраните элементы с set->elems[0]=i1; ....

Другой вариант - использовать битовые массивы, но реализация будет зависеть от природы целых чисел, которые нужно хранить (например, находятся ли они в фиксированном диапазоне? Обычно они появляются в группах в наборе?).

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

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

Как я уже сказал, мне кажется, это не тривиально, я не удивлен, что Google не помог.

Это не очень сложно, хотя вам просто нужно принять некоторые решения, прежде чем продолжить.

Answer 4

Реализуйте простую хеш-таблицу самостоятельно. Это сделает вас лучшим программистом, если вы знаете, как реализовать его самостоятельно.

http://en.wikipedia.org/wiki/Hash_table