Playlist (5): haciendo eficiente, casi por gusto, la cola de reproducción

Minirok hereda de Amarok el concepto de cola de reproducción: una manera de indicar qué pistas se han de reproducir a continuación, si no se desea seguir el orden propio de la lista (screenshot).

La implementación en la versión anterior de Minirok era bien sencilla: una lista de Python que contiene, en orden, los ítems según han sido encolados. Cuando acaba una pista, antes de pasar a reproducir el siguiente ítem, se intenta reproducir el primer ítem de la cola, si lo hubiere. Al dibujar cada pista, se recorre la lista (mediante su método index()) para ver si dicha pista es parte de la cola o no, y poder mostrar en la interfaz su posición. Para encolar o desencolar ítems, un único método toggle_enqueued(), capaz actuar sobre un ítem cada vez.

Lo que salta a la vista con esta implementación es que el dibujado de cualquier ítem es O(m), con m el tamaño de la cola, ya que para cada ítem hay que recorrer la cola para ver si el ítem se encuentra en ella o no. Esto suena, en principio, mal — sin embargo, y dado que el tamaño de la cola suele ser muy muy pequeño, el efecto es despreciable.

No obstante, al estar rescribiendo partes importantes del código, me pareció que era una buena oportunidad para cambiar esto. El resultado: una implementación más eficiente (y algo más compleja, dicho sea de paso), y la satisfacción de un trabajo bien hecho.

---

La primera mitad de la idea es sencilla y no nueva: como lo que hay que optimizar es la operación index() (que, dado un valor, obtiene su posición en la lista), hacemos de estos índices un valor calculado en los objetos de la clase PlaylistItem, siendo el modelo el encargado de mantenerlos actualizados. Es decir, la misma idea que en esta entrada comenté para la lista en sí.

En segundo lugar, y ya casi por ejercicio (imaginando que se tratara de una parte mucho más crítica en cuanto a eficiencia) he introducido un nuevo método toggle_enqueued_many(), capaz de encolar y desencolar varios ítems a la vez. La principal ventaja consiste en que en el caso de desencolar ítems de una lista muy grande, sólo hay que recalcular los atributos queue_position de los ítems restantes una vez.

Y, otra vez, me ha pasado que releyendo el código para comentarlo aquí me ha venido la inspiración, y he visto una manera más sencilla y eficiente de hacerlo. (De hecho, no entiendo muy bien cómo no lo hice así desde el principio, pues el problema es bien sencillo.)

---

Si nos dan una lista de índices a eliminar, y queremos ajustar los valores restantes de la lista de manera que coincidan con sus nuevas posiciones, la mejor manera (hasta donde yo he llegado :-) es agrupar los índices a eliminar en grupos contiguos, y decrementar los valores que quedan entre cada par de grupos (más entre el último grupo y el final de la lista) tantas unidades como ítems se hayan eliminado hasta ese punto.

Con un ejemplo se ve mejor. Por ejemplo, dada la lista:

  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
   17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]

Y la lista de índices a eliminar:

  [2, 10, 11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 29]

Al agrupar esta última tenemos (el primer valor es la posición y el segundo la cantidad de ítems a eliminar):

  [(2, 1), (10, 6), (21, 5), (29, 1)]

Así, haríamos:

• desde 3 a 9, decrementar 1
• desde 16 a 20, decrementar 7 (= 1+6)
• desde 26 a 28, decrementar 12 (= 1+6+5)
• del 30 en adelante, decrementar 13 (= 1+6+5+1)

En código Python, por si a alguien le pica la curiosidad, viene a ser esto:

  def dequeue(self, indexes):
      indexes.sort()

      chunks = contiguous_chunks(indexes)
      chunks.append((len(self.queue), 0)) # fake chunk at the end

      accum = 0
      for i, (index, amount) in enumerate(chunks[:-1]):
          accum += amount
          until = sum(chunks[i+1])
          for item in self.queue[index+amount:until]:
              item.queue_position -= accum

      for index in reversed(indexes):
          item = self.queue.pop(index)
          item.queue_position = None

Casualmente, la función contiguous_chunks() la tenía escrita ya como parte del AlterItemlistMixin que comenté el otro día.

El diff entero, de la revisión 575 recién salida de la cocina, aquí.