¿Qué es una biblioteca C simple para un conjunto de conjuntos enteros?

Question

Tengo que modificar un programa C y necesito incluir un conjunto de enteros sin signo. Es decir, tengo millones de conjuntos de enteros (cada uno de estos conjuntos enteros contiene entre 3 y 100 enteros), y necesito almacenarlos en alguna estructura, vamos a llamarlo el directorio, que en tiempo logarítmico puede decirme si un determinado el conjunto entero ya existe en el directorio. Las únicas operaciones que deben definirse en el directorio son buscar e insertar.

Esto sería fácil en idiomas con soporte integrado para estructuras de datos útiles, pero soy un extranjero para C y al mirar en Google (sorprendentemente) no contesté mi pregunta satisfactoriamente. Este proyecto se ve sobre la derecha:

http://uthash.sourceforge.net/

pero tendría que llegar a mi propio generador de clave hash.

Este es un problema simple y estándar, por lo que espero que haya una solución estándar y simple.

Answer 1

Depende de lo que va a hacer con los datos. Pero tal vez tsearch ya hace lo que quiere. También puede construir una matriz ordenada para cada conjunto y buscar los valores con bsearch, aunque el rendimiento puede sufrir durante la inserción.

EDITAR Si está buscando una biblioteca (externa), encontrará una comparación de la implementación de la tabla hash C y C++ here. El autor del artículo ha escrito una implementación de encabezado genérico llamada khash. Entonces, usted está compilado en binario y no tiene dependencias adicionales.

Answer 2

Implemente una tabla de hash simple usted mismo. Te hará un mejor programador, cuando sepas cómo implementar uno por tu cuenta.

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

Answer 3

EDIT: lo siento, comenzó a contestar ya que es C++ y no C. Sí, entonces debería encontrar su función hash y el código por ti mismo .. puesto que ya conoce la dimensión media de un conjunto ¡no es tan difícil, solo elige una buena función hash! Pero necesitará codificar un conjunto completo en un solo número si desea verificar si un directorio ya está allí.

Usted puede tratar mediante hash de forma iterativa los números individuales del conjunto:

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

de manera que el hashfunction depende de su valor anterior, el número actual y el índice actual.

¿Qué hay de los conjuntos de 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 << ' '; 

El uso de esta estructura de datos que puede almacenar fácilmente todos sus juegos, pero se necesita también una manera de comprobar si un conjunto ya está incluido en el directorio. No está claro: ¿quieres saber si ya existe un conjunto que tenga todos los MISMOS elementos en el directorio?

Puede hacerlo de forma manual mediante la comprobación de todos los elementos, pero ya que usted tiene millones de ellos tendrá que buscar un camino para discutir los elementos del conjunto en un número único y el uso de un mapa de conjuntos ..

Answer 4

Si Te entiendo correctamente, quieres representar un conjunto de conjuntos de números enteros que no creo que sean particularmente triviales.

El primer punto es representar un conjunto de números enteros. La forma más sencilla sería utilizar una matriz de tamaño variable de la siguiente manera:

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

de lo que puede crear un nuevo conjunto (con un número fijo de elementos) con

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

y almacenar los elementos con set->elems[0]=i1; ....

Otra opción sería utilizar matrices de bits, pero la implementación dependería de la naturaleza de los enteros para almacenar (por ejemplo, ¿están dentro de un rango fijo? ¿Aparecen generalmente en grupos en un conjunto?).

Una vez que tenga su conjunto de números enteros, necesitará una función de comparación (para determinar si dos conjuntos tienen los mismos elementos). Si optó por una matriz para representar un conjunto y mantiene esa matriz ordenada, es bastante simple comprobar si dos conjuntos son idénticos; si es un mapa de bits, dependerá de cómo lo implemente.

Ahora, para el conjunto de conjuntos puede elegir un vector (ordenado), que puede necesitar cambiar el tamaño de vez en cuando al insertar elementos o una tabla hash. En este último caso, deberá escribir una función hash para sus conjuntos de números enteros (¡posiblemente utilizando las funciones existentes!).

Como dije, no me parece trivial, no me sorprende que Google no haya ayudado.

No es extremadamente complicado, sin embargo, solo tiene que tomar algunas decisiones antes de continuar.