WWDC18–223: Adoptando algoritmos en Swift

Resumen de la charla: embracing algorithms at WWDC 2018. (Diapositivas)

Descripción de la charla

Dave Abrahams plantea el escenario de una aplicación móvil que consiste en arrastrar figuras geométricas hasta un lienzo. Luego se puede hacer las siguientes operaciones sobre ciertas figuras seleccionadas:

1. Borrar
2. Traer al frente
3. Enviar hacia el fondo
4. Mover hacia atrás
5. Mover hacia delante
6. Reunir en un índice específico

Se revisa la operación de borrar figuras seleccionadas: inicialmente se recorre el arreglo de todas las figuras manualmente y se elimina la que esté seleccionada. Éste implementación es problemática, porque al eliminar la posición i-esima del arreglo, el rango de ejecución del ciclo For pierde sentido.

extension Canvas  {
  mutating  func deleteSelection() {
    for i in 0..<shapes.count {
      if shapes[i].isSelected {
        shapes.remove(at: i)
      }
    }
  }
}

Como alternativa manual, se propone recorrer el arreglo en sentido inverso. Aunque funciona, no es la solución óptima, puesto que la complejidad computacional del algoritmo es cuadratica. Esto se debe a que recorrer el arreglo manualmente es una operación lineal, y el llamado a la función anidada remove(at:) también lo es.

extension Canvas  {
  mutating  func deleteSelection() {
    for i in (0..<shapes.count).reversed() {
      if shapes[i].isSelected {
        shapes.remove(at: i)
      }
    }
  }
}

Se sugiere optimizar el funcionamiento del algoritmo usando la función: removeAll(where:), que elimina todos los elementos de la colección que cumplan con la condición del predicado, con la ventaja de qué sólo es esto, operación tiene complejidad computacional lineal.

extension Canvas  {
  mutating  func deleteSelection() {
    shapes.removeAll(where: { $0.isSelected })
  }
}

removeAll(where:) es una función de MutableCollection, que utiliza la función halfStablePartition(isSuffixElement:), que organiza la colección, dejando todos los elementos que cumplen la condición de su argumento al final, y devolviendo el índice del primer elemento que cumple con la condición. Una vez que se tiene todo el arreglo organizado, se puede eliminar los elementos a partir de dicho índice.

Get GoyesDev’s stories in your inbox
Join Medium for free to get updates from this writer.
Remember me for faster sign in
extension MutableCollection where Self: RangeReplaceableaCollection  {
  mutating  func removeAll(where shouldRemove: (Element) -> Bool) {
    let suffixStart = halfStablePartition(isSuffixElement: shouldRemove)
    removeSubrange(suffixStart…)
  }
}

Pero, ¿como funciona halfStablePartition? cómo se puede ver en el código a continuación, primero se trata de encontrar el índice del primer elemento que cumpla la condición. Luego se creó un índice justo después del creado recientemente, y se revisan todos los elementos, a partir de ese punto desplazando este nuevo índice. Si el predicado no se cumple, se intercambian los elementos apuntados por los índices, y se mueve el índice inicial, una posición hacia adelante. Luego se mueve el índice de comparación una posición hacia adelante también. Como sólo se recorre el arreglo una vez, la complejidad computacional de este algoritmo es lineal.

extension MutableCollection {
  mutating  func halfStablePartition(isSuffixElement: (Element) -> Bool) -> Index {
    guard var i = firstIndex(where: isSuffixElement) else { return endIndex }
    var j = index(after: i)
    while j != endIndex {
      if !isSuffixElement(self[j]) { swapAt(i, j); formIndex(after: &i) }
      formIndex(after: &j)
    }
    return i
  }
}

Se hizo un análisis semejante con el resto de operaciones, y se descubrió, que podían ser expresadas en términos de la función stablePartition(isSuffixElement:).

extension Canvas {
  mutating  func bringForward() {
    if let i = shapes.firstIndex(where: { $0.isSelected }) {
      if i == 0 { return }
      let predecessor = i - 1
      shapes[predecessor…].stablePartition(isSuffixElement: { !$0.isSelected })
    }
  }
}

A pesar de qué la solución es óptima, se está combinando lógica particular del negocio, con lógica específica del algoritmo. Esto provoca que sea muy difícil crear pruebas automatizadas. Por esta razón, es necesario generalizar la solución.

extension MutableCollection {
  mutating  func bringForward(elementsSatisfying predicat: (Element) -> Bool) {
    if let i = firstIndex(where: { $0.isSelected }) {
      if i == startIndex { return }
      let predecessor = i - 1
      self[predecessor…].stablePartition(isSuffixElement: { !$0.isSelected })
    }
  }
}

Todavía se puede hacer otra refactorización, de modo que sea más inteligible:

extension MutableCollection {
  mutating  func bringForward(elementsSatisfying predicat: (Element) -> Bool) {
    if let predecessor = indexBeforeFirst(where: { $0.isSelected }) {
      self[predecessor…].stablePartition(isSuffixElement: { !$0.isSelected })
    }
  }
}

extension Collection {
  func indexBeforeFirst(where predicate: (Element) -> Bool) -> Index? {
    return indices.first {
      let successor = index(after: $0)
      return successor != endIndex && predicate(self[successor])
    }
  }
}

Después de esta última modificación, será más fácil para el cliente de estas funciones, entender la intención del código.

Observaciones

• “Evitar ciclos crudos” — Sean Parent (C++ Seasoning)
• Cada vez que añadas un nuevo ciclo, reemplázalo con el llamado a un algoritmo. Si no puedes encontrar uno, crea ese algoritmo y mueve el ciclo a su implementación.
• Buscar separar la lógica específica del algoritmo de la lógica del negocio.
• En lugar de construir todo el código (lógica de negocio + algoritmo) en una sola clase, buscar edificar una jerarquía de abstracciones que permita reutilización del código.
• Documentar todos los métodos que nos traen comportamiento, de modo que los clientes de estos no necesiten conocer los detalles de implementación.

Otros artículos de interés

• Notas WWDC, 2018