Data.Set: ¿siempre sabe mejor?

Necesito representar un conjunto y estoy empezando a trabajar con Data.Set. Veo que no hay nada que hacer realmente: singleton, union, intersection, etc. están todos allí. Me gusta. Puedo expresar "qué", no "cómo". Pero mi programador C interno es incómodo. Hay muchas maneras de implementar un conjunto (árbol binario, hash, matriz booleana, etc.). ¿Realmente puedo confiar en Data.Set para elegir el mejor? ¿Puedo guiarlo de alguna manera, o simplemente me rindo a su juicio (lo admito, probablemente superior)?Data.Set: ¿siempre sabe mejor?

Fuente

2012-03-18 gcbenison

Vaya con la opción 2, especialmente si esto se utiliza en el código de producción. – Shredderroy

Data.Set no tiene inteligencia interna (solo vea the source!). Es solo un árbol equilibrado o elementos ordenados. Puede buscar intrusos para muchos otros conjuntos y estructuras similares a conjuntos con diferentes características de rendimiento. Por ejemplo, vea unordered-containers (HashSet), HashTables y bloomfilter.

Fuente

2012-03-18 04:14:00

OK, gracias. Supongo que una pregunta de seguimiento es: ¿existe, o habrá alguna vez, un 'Data.Set' en el que se pueda confiar para que haga algunas de estas elecciones de implementación para la persona que llama? es decir, cuando se le dice que el dominio es solo [1..8], se dará cuenta de que solo puede usar un byte. – gcbenison

Como los valores están todos enmarcados, no podrá hacer que se use solo un byte. ¿Cómo implementarías eso en Haskell? Supongo que verificará el valor de la entrada y configurará el bit en su 'Word8' manualmente, luego tendrá que asignar un valor encuadrado para cada búsqueda. No me parece una victoria de rendimiento. –

Parece que todavía podría establecer comparaciones de igualdad sin asignaciones, y tal vez uniones e intersecciones con una sola asignación de Word8. – gcbenison

El general Data.Set utiliza un árbol binario equilibrado. Si tiene conjuntos de enteros o vectores de bits, querrá Data.IntSet, que usa Patricia try.

Ambas implementaciones se han perfeccionado a través de años de la competencia para obtener el mejor rendimiento posible con Haskell.

Surrender Dorothy!

Fuente

2012-03-18 04:12:43

Esto combinado con la respuesta de Thomas juntos forman una buena respuesta. 'Data.Set' es genial, tiene una interfaz maravillosa, y es lo suficientemente rápido en la mayoría de los casos (mucho mejor de lo que cualquiera de nosotros podría rodar a mano), pero (como todas las cosas) no resolverá todos los problemas de manera óptima. No te preocupes hasta que lo necesites; cuando lo haga, consulte algunas de las otras bibliotecas. – luqui

@luqui Creo que cuando tienes conjuntos de enteros vale la pena ir directamente a 'Data.IntSet'. –

Respuesta

Cuestiones relacionadas