Что такое простая библиотека C для ряда целочисленных наборов?
Я должен изменить программу C, и я должен включать ряд наборов беззнаковых целых чисел. Таким образом, у меня есть миллионы наборов целых чисел (каждый из этих целочисленных наборов содержит между 3 и 100 целыми числами), и я должен сохранить их в некоторой структуре, позволяет, называют это каталогом, который может в логарифмическое время говорить мне, существует ли данный целочисленный набор уже в каталоге. Единственные операции, которые должны быть определены на каталоге, являются поиском, и вставить.
Это было бы легко на языках со встроенной поддержкой полезных структур данных, но я - иностранец для C, и озирающийся на Google (удивительно) не отвечал на мой вопрос удовлетворительно. Этот проект озирается вокруг права:
http://uthash.sourceforge.net/
но я должен был бы придумать свой собственный генератор ключа хеша.
Это - стандартная, простая проблема, таким образом, я надеюсь, что существует стандартное и простое решение.
4 ответа
Это зависит от того, что вы собираетесь делать с данными. Но, возможно, tsearch уже делает то, что вы хотите. Вы также можете создать отсортированный массив для каждого набора и искать значения с помощью bsearch, хотя производительность может пострадать при вставке.
EDIT: Если вы ищете (внешнюю) библиотеку, вы найдете сравнение некоторых реализаций хэш-таблиц на C и C++ здесь. Автор статьи написал общую реализацию заголовка под названием khash. Так что скомпилированный бинарник не имеет никаких дополнительных зависимостей.
Создайте простую хеш-таблицу самостоятельно. Вы станете лучшим программистом, если будете знать, как реализовать его самостоятельно.
Если я правильно вас понял, вы хотите представить набор целых чисел, который я не считаю особенно тривиальным.
Первый пункт - представить набор целых чисел. Самый простой способ - использовать такой массив переменного размера:
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 не помог.
Это не так уж сложно, просто нужно принять некоторые решения, прежде чем продолжить.
EDIT: извините, я начал отвечать, так как это 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 << ' ';
Используя эту структуру данных, вы можете легко хранить все ваши множества, но вам также нужен способ проверить, включен ли уже набор в каталог. Неясно: хотите ли вы знать, существует ли уже в каталоге набор, содержащий все одинаковые элементы?
Вы можете сделать это вручную, проверяя все элементы, но поскольку у вас их миллионы, вы должны найти способ хэшировать элементы набора в уникальное число и использовать карту наборов.