C – ¿Cómo implementar la estructura de datos Set?

5 minutos de lectura

¿Hay alguna forma complicada de implementar una estructura de datos establecida (una colección de valores únicos) en C? Todos los elementos de un conjunto serán del mismo tipo y hay una gran memoria RAM.

Como sé, para los números enteros se puede hacer muy rápido y fácil usando matrices indexadas por valor. Pero me gustaría tener un tipo de datos Set muy general. Y sería bueno si un conjunto pudiera incluirse a sí mismo.

  • Tengo la misma pregunta aquí: stackoverflow.com/questions/2537681/how-to-implement-a-set . ¡Quizás ayude!

    – Andréi Ciobanu

    13 de abril de 2010 a las 15:38

  • Complemento desvergonzado: escribí una biblioteca de árbol B en memoria en C: ccan.ozlabs.org/info/btree.html . Un árbol B cumple esencialmente el mismo papel que un árbol binario con respecto a los conjuntos.

    –Joey Adams

    13 de abril de 2010 a las 15:50


  • Por supuesto, implementar conjuntos que se contienen a sí mismos es solo buscar problemas.

    – Marca de alto rendimiento

    13 de abril de 2010 a las 16:47

avatar de usuario
vladr

Hay múltiples formas de implementar establecer (y mapear) la funcionalidad, por ejemplo:

  • enfoque basado en árboles (recorrido ordenado)
  • enfoque basado en hash (recorrido desordenado)

Ya que mencionaste matrices indexadas por valorprobemos el enfoque basado en hash que se construye de forma natural sobre la técnica de matriz indexada por valores.

Cuidado con el ventajas y desventajas de enfoques basados ​​en hash vs. basados ​​en árboles.

Puedes diseñar un hash-set (un caso especial de tablas hash) de punteros a hashable VAINAs, con encadenamientorepresentada internamente como una matriz de tamaño fijo de cubos de hashablesdonde:

  • todos hashables en un cubo tienen el mismo valor hash
  • un cubo se puede implementar como un matriz dinámica o lista enlazada de hashables
  • a hashable‘s el valor hash se usa para indexar en la matriz de cubos (matriz indexada de valor hash)
  • uno o más de los hashables contenido en el conjunto hash podría ser (un puntero a) otro conjunto hash, o incluso al propio conjunto hash (es decir, la autoinclusión es posible)

Con grandes cantidades de memoria a su disposición, puede dimensionar generosamente su matriz de cubos y, en combinación con un buen método hash, reducir drásticamente la probabilidad de colisiónlogrando un rendimiento de tiempo prácticamente constante.

Tendrías que implementar:

  • los función hash para el tipo que está siendo hash
  • una función de igualdad para el tipo que se utiliza para probar si dos hashables son iguales o no
  • el conjunto de hash contains/insert/remove funcionalidad.

También puedes usar direccionamiento abierto como alternativa al mantenimiento y la gestión de cubos.

avatar de usuario
y y

Los conjuntos generalmente se implementan como una variedad de árbol binario. Árboles negros rojos tener un buen desempeño en el peor de los casos.

Estos también se pueden utilizar para construir un mapa para permitir búsquedas de clave/valor.

Este enfoque requiere algún tipo de ordenación de los elementos del conjunto y los valores clave en un mapa.

No estoy seguro de cómo administraría un conjunto que posiblemente podría contenerse a sí mismo usando árboles binarios si limita la membresía del conjunto a tipos bien definidos en C … la comparación entre tales construcciones podría ser problemática. Sin embargo, podría hacerlo fácilmente en C++.

Si la cantidad máxima de elementos en el conjunto (la cardinalidad del tipo de datos subyacente) es lo suficientemente pequeña, es posible que desee considerar usar una matriz de bits simple y antigua (o como los llame en su idioma favorito).

Entonces tiene una verificación de membresía de conjunto simple: el bit n es 1 si el elemento n está en el conjunto. Incluso podría contar miembros ‘ordinarios’ desde 1, y solo hacer que el bit 0 sea igual a 1 si el conjunto se contiene a sí mismo.

Este enfoque probablemente requerirá algún tipo de otra estructura de datos (o función) para traducir del tipo de datos miembro a la posición en la matriz de bits (y viceversa), pero realiza operaciones básicas de conjunto (unión, intersección, prueba de membresía, diferencia, inserción, remoción, obligatoriedad) muy, muy fácil. Y solo es adecuado para conjuntos relativamente pequeños, supongo que no querrías usarlo para conjuntos de enteros de 32 bits.

La forma de obtener genericidad en C es por void *, por lo que usará punteros de todos modos, y los punteros a diferentes objetos son únicos. Esto significa que necesita un mapa hash o un árbol binario que contenga punteros, y esto funcionará para todos los objetos de datos.

La desventaja de esto es que no puede ingresar valores r de forma independiente. No puede tener un conjunto que contenga el valor 5; tiene que asignar 5 a una variable, lo que significa que no coincidirá con un 5 aleatorio. Puede ingresarlo como (void *) 5y para fines prácticos, es probable que esto funcione con números enteros pequeños, pero si sus números enteros pueden tener tamaños lo suficientemente grandes como para competir con los punteros, tiene una probabilidad muy pequeña de fallar.

Esto tampoco funciona con valores de cadena. Dado char a[] = "Hello, World!"; char b[] = "Hello, World!";un conjunto de punteros encontraría a y b ser diferente. Probablemente desee codificar los valores, pero si le preocupan las colisiones de hash, debe guardar la cadena en el conjunto y hacer un strncmp() para comparar la cadena almacenada con la cadena de sondeo.

(Existen problemas similares con los números de punto flotante, pero tratar de representar números de punto flotante en conjuntos es una mala idea en primer lugar).

Por lo tanto, probablemente desee un valor etiquetado, una etiqueta para cualquier tipo de objeto, una para el valor entero y otra para el valor de cadena, y posiblemente más para diferentes tipos de valores. Es complicado, pero factible.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad