10
Supongamos que estamos atravesando un gráfico y queremos determinar rápidamente si un nodo se ha visto antes o no. Tenemos algunas precondiciones establecidas.Búsqueda rápida de elementos para un lenguaje funcional (Haskell)
- nodos han sido marcadas con números enteros valores 1..N
- Graph se implementa con nodos que tiene una lista de adyacencia
- Cada valor entero de 1..N se produce en el gráfico, que es de tamaño N
¿Alguna idea para hacer esto de una manera puramente funcional? (No se permiten tablas ni matrices Hash).
Quiero una estructura de datos con dos funciones trabajando en ella; agregar (agrega un entero encontrado) y buscar (verifica si se ha agregado un entero). Ambos deberían tomar preferentemente O (n) tiempo amortizado para N repeticiones.
¿Esto es posible?
Supongo que Data.Set dará un rendimiento logarítmico o cuasi-constante en AddToSet y miembro, en comparación con el rendimiento esperado en tiempo constante con tablas hash. –
Chris, tienes razón. Las operaciones de inserción y búsqueda de datos son O (log n). – namin
Si sus enteros son lo suficientemente pequeños para el tipo Int, puede usar Data.IntSet, que es la versión optimizada de Set. – mattiast