Playlist (2): estructura interna de los datos (y moraleja)

La lista de reproducción es, a todas todas, un simple array de ítems. Con Qt3, el orden de esta lista se guardaba en las estructuras internas (y no directamente accesibles) de la clase QListView. Esta clase ofrecía iteradores para acceder a los ítems en orden, y estos ítems tenían métodos como itemAbove() e itemBelow() para, dado por ejemplo la pista actual en reproducción, poder saltar a la pista siguiente o la anterior.

Ahora, con Qt4, la responsibilidad de estas estructuras internas corresponde al modelo, es decir, a nosotros mismos. Como implementadores, tenemos que almacenar la lista en una estructura o estructuras que, por una parte, proporcionen toda la funcionalidad necesaria y, por otra, sean razonablemente eficientes. Para ello, hay que saber primero qué tipo de acceso a la estructura vamos a necesitar.

Se necesita, en primer lugar, un acceso por índice numérico, y se necesita que sea rápido. Como se vio en la entrada anterior, el método data() del modelo recibe una fila y una columna; y dicho método se invoca muchas muchas veces por la vista, así que debe de ser realmente rápido. Asimismo, todo el resto de interacciones entre la vista y el modelo se basan en número de fila. Por esto, el almacén principal de los ítems es una lista de Python, llamada _itemlist, y que se debe modificar únicamente mediante dos métodos insert_items() y remove_items():

  class Playlist:

      def insert_items(self, position, items):
          amount = len(items)
          self.beginInsertRows(QtCore.QModelIndex(),
                               position, position + amount - 1)
          self._itemlist[position:0] = items
          self._row_count += amount
          self.endInsertRows()

      def remove_items(self, position, amount):
          self.beginRemoveRows(QtCore.QModelIndex(),
                               position, position + amount - 1)
          self._itemlist[position:position+amount] = []
          self._row_count -= amount
          self.endRemoveRows()

          return items

(Las funciones beginRemoveRows() y endRemoveRows() son funciones heredadas de la clase base, y han de ser llamadas para indicar a la vista que va a haber modificaciones en la lista de ítems.)

Por otra parte, en distintas partes el modelo también necesita la operación inversa: a partir de un determinado ítem, averiguar su posición. En principio esto se podría hacer con el método index() de las listas de Python, pero tendría complejidad O(n); y a nosotros nos conviene O(1), sobre todo con vistas a listas grandes (siendo n el tamaño de la lista).

Mi primera idea, que implementé y mantuve hasta ayer mismo, fue acoplar un diccionario a la lista de ítems. Es decir, mantener una estructura adicional que mapeara ítems a posiciones: la obtención de la posición de cualquier ítem sería O(1), a cambio de incrementar la complejidad temporal de las dos funciones explicadas anteriormente, para mantener el diccionario actualizado. (Este incremento, lamentablemente, es O(m+n) tanto en el caso peor como en el mejor, ya que hay que iterar sobre todos los elementos del diccionario y mirar si hay que actualizarlos uno a uno.)

Sin embargo, al comenzar a preparar esta entrada, lo miré todo con nuevos ojos, y se me ocurrió una manera más sencilla y eficiente: mantener un atributo con la posición en los ítems mismos.

Al principio de comenzar a migrar la lista, me planteé los ítems como un simple contenedor para los tags del fichero, y que todo el resto de información debería almacenarse en el modelo en sí. Y, por tanto, implementé el diccionario acoplado. Pero algo más tarde cambié de idea y comencé a incluir algunos otros atributos en los ítems, de cuya actualización el encargado era el modelo. Sin embargo, se me olvidó considerar este nuevo paradigma para almacenar la posición de cada ítem en la lista.

Una vez hecho, para mantener el atributo position actualizado sólo hay que añadir un poco de código a los dos métodos anteriores, así:

  class Playlist:

      def insert_items(self, position, items):
          [...]
          for item in self._itemlist[position:]:
              item.position += amount

          for i, item in enumerate(items):
              item.position = position + i
          [...]

      def remove_items(self, position, amount):
          [...]
          for item in items:
              item.position = None

          for item in self._itemlist[position+amount:]:
              item.position -= amount
          [...]

Este nuevo cambio tiene complejidad O(n+m) en el caso peor, pero O(m) en el caso mejor (siendo m el número de items a insertar o eliminar). El cambió está implementado en la revisión 549 (diff).

Moraleja: siempre es bueno examinar tras un tiempo las soluciones que hemos dado a un problema, por ejemplo describiendo por escrito sus detalles. Muy a menudo encontraremos que pasado un tiempo nuestro cerebro es capaz de ver maneras más eficientes o elegantes de hacer las cosas.