Estructuras de datos en Cocoa
En un artículo anterior mencionaba CHDataStructures por la necesidad de usar una clase “pila” (Stack) en Cocoa.
Al parecer se trata de un error común cuando se llega a Cocoa. Siempre llama la atención la falta de ciertas estructuras de datos clásicas como pilas, colas o tablas hash.
Sin embargo, si uno se detiene a revisar con más atención la documentación de las clases proporcionadas por Cocoa, pronto se da cuenta que ni todo es lo que parece, ni falta nada importante.
Usar NSMutableArray como pila
Cuando preguntas por la falta de una clase pila, la respuesta de los más viejos del lugar es siempre la misma: usa NSMutableArray.
En un principio, supuse que se referían a añadir y quitar por el final del array, considerando el final como la cabeza de la pila. Parecía una chapuza, y bastante innecesaria.
Luego me percaté que la cosa era peor, ya que NSMutableArray tiene métodos para añadir y eliminar por el principio. Ahora estábamos hablando de un chapuza portentosa, ya que al añadir y quitar por el principio, habría que mover todos los demás elementos del array.
Un array que no lo es: NSMutableArray
Pero comparemos primero las estructuras de datos disponibles en Cocoa y en otro lenguaje. Si mal no recuerdo, las estructuras de datos disponibles en C++ son las siguientes:
- vector
- deque
- list
- slist
- bit_vector
- set
- map
- multiset
- multimap
- hash_set
- hash_map
- hash_multiset
- hash_multimap
- stack
- queue
- priority_queue
- bitset
- NSMutableArray
- NSMutableDictionary
- NSMutableSet
Computational Complexity The access time for a value in the array is guaranteed to be at worst O(lg N) for any implementation, current and future, but will often be O(1) (constant time). Linear search operations similarly have a worst case complexity of O(N*lg N), though typically the bounds will be tighter, and so on. Insertion or deletion operations will typically be linear in the number of values in the array, but may be O(N*lg N) clearly in the worst case in some implementations. There are no favored positions within the array for performance; that is, it is not necessarily faster to access values with low indices, or to insert or delete values with high indices, or whatever.
El tiempo de acceso NO constante, tal y como sería de esperar, sino que puede serlo, como también puede ser logarítmico. Los tiempos de inserción son en el peor caso O(N Lg N), lo cual también es incongruente con un array.
Por lo visto, parece ser que cuando le pedimos un array a Cocoa, lo que nos da en realidad es algún tipo de árbol balanceado (hay referencias en internet que afirman tratarse de un 2-3 tree). Posiblemente se empiece con una implementación de array estandar y a medida que aumentan los elementos se cambia a algún tipo de árbol.
Conclusiones
A pesar del nombre, un NSArray o NSMutableArray no es sólo lo que aparenta, sino que se trata de una estructura de datos más compleja, como puedan ser las “Collection” de COM o los arrays de PHP.
Los NSMutableArrays son eficientes en ciertas cosas para las cuales un array es inadecuado y por lo tanto no tiene demasiado sentido hacer tu propia clase pila o cola si vas a añadir muchas cosas por delante. Prueba primero lo que viene “de serie” en Cocoa y reinventa la rueda sólo si es necesario.
Por lo tanto, no hay una necesidad real de librerías como CHDataStructures, ya que Cocoa proporciona todo lo necesario para un uso normal. Lo único que tal vez hecho en falta es un trie y un suffix tree.
