NSArraySpeedTest2

Por qué no necesitas una pila y un array que no lo es (NSMutableArray)

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:

  1. vector
  2. deque
  3. list
  4. slist
  5. bit_vector
  6. set
  7. map
  8. multiset
  9. multimap
  10. hash_set
  11. hash_map
  12. hash_multiset
  13. hash_multimap
  14. stack
  15. queue
  16. priority_queue
  17. bitset
O sea, 17 estructuras de datos. Veamos lo que tenemos en Cocoa:
  1. NSMutableArray
  2. NSMutableDictionary
  3. NSMutableSet
Y poco más (aunque en CoreFoundation podemos encontrar algo más como CFBinaryHeap o CFMutableBitVector).
A parte de la diferencia enorme en el número, llama mucho la atención la diferencia en los nombres. Mientras que en C++ la implementación de las estructuras de datos está claramente visible en el nombre, Cocoa opta por ocultar el «cómo» y solo nos dice el qué hacen las clases.
Si rebuscamos en el código disponible de NSArray nos llevamos una sorpresa al leer el siguiente comentario:
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.

 

Fernando Rodríguez

Sígueme en twitter.
Cursos de desarrollo iPhone

Acerca de Fernando Rodriguez

Fundador & Editor Jefe de justcodeit, Fernando Rodríguez (@frr149 & Linkedin) es desarrollador & un experto en la enseñanza de máxima calidad en programación y desarrollo para dispositivos iOS, Cocoa Touch, Objective C, Swift, Python, entre otros, aunque su mejor carta de presentación, es la opinión de sus alumnos: http://keepcoding.io/es/testimonio/ CLO en KeepCoding & Arunovo. Instructor de iOS Avanzado del Big Nerd Ranch. Profesor Asociado de la U-tad, autor invitado de revistas como iPhoneWorld, Applesfera.com & ponente habitual en conferencias dentro y fuera de España (iOSDevUK, CodeMotion, BCNDevCon, etc). En sus vidas anteriores fue un nerd de Python y Django, mago de Smalltalk, y para su pesar, galeote de C++ y un gran cocinero.

Share this:

Leave a comment