Los algoritmos de la stdlib y su complejidad real

La biblioteca estándar te da un vocabulario de algoritmos tan cómodo que es fácil olvidar que cada llamada tiene un precio en tiempo y en memoria. Encadenar cinco transformaciones no cuesta cinco veces más que una: cuesta cinco recorridos y cuatro arrays intermedios. Esta lección lee esos algoritmos como lo que son —implementaciones concretas con contratos de complejidad publicados— y te enseña a estimar el coste de una cadena antes de escribirla.

map, filter y el coste de la comodidad

map y filter son lineales en tiempo, pero su firma esconde el dato importante: devuelven un array nuevo. Cada eslabón de una cadena reserva un búfer, lo llena y lo entrega al siguiente, que hace lo mismo:

let resultado = numeros
    .map { $0 * 2 }        // recorrido 1, array nuevo de n elementos
    .filter { $0 > 10 }    // recorrido 2, array nuevo de k elementos
    .map(String.init)      // recorrido 3, array nuevo de k elementos

Tres pasadas y tres asignaciones de montón para un trabajo que un solo bucle haría con una. map reserva de golpe la capacidad exacta porque conoce count; filter no puede saber cuántos sobrevivirán, así que crece por duplicación amortizada. La diferencia se nota cuando n es grande.

flowchart LR
A[array base: n elementos] --> B[map: asignacion uno, n elementos]
B --> C[filter: asignacion dos, k elementos]
C --> D[map: asignacion tres, k elementos]
style B fill:#f38ba8,color:#11111b
style C fill:#f38ba8,color:#11111b
style D fill:#f38ba8,color:#11111b

Hay dos matices que casi nadie tiene presentes. El primero es el orden de los eslabones: filtrar antes de transformar reduce el trabajo del mapa a los supervivientes, mientras que transformar antes de filtrar paga la transformación por todos. Cuando la transformación es cara y el filtro selectivo, invertir el orden puede dividir el tiempo por diez sin cambiar el resultado. El segundo es que forEach no es equivalente a for-in: no admite break ni continue, y un return dentro solo sale de la closure, así que nunca puede terminar antes de tiempo.

reduce y el pliegue con acumulador mutable

reduce es el más general de todos: colapsa una colección en un solo valor aplicando una función de acumulación. Su complejidad es lineal en número de llamadas, pero puede ser cuadrática en trabajo real:

// TRAMPA: cada paso construye un array nuevo copiando el anterior
let malo = palabras.reduce([String]()) { acc, p in acc + [p] }   // O(n al cuadrado)

// CORRECTO: un solo bufer que se muta en su sitio
let bueno = palabras.reduce(into: [String]()) { acc, p in acc.append(p) }  // O(n)

La causa es la semántica de valor. En la primera versión, el operador de concatenación crea un array nuevo en cada iteración: sumando los tamaños, el trabajo total es cuadrático. reduce(into:) pasa el acumulador como parámetro inout, de modo que el búfer se reutiliza y la copia sobre escritura nunca se dispara. La regla es mecánica: si el acumulador es un tipo con almacenamiento —array, diccionario, conjunto, cadena— usa siempre la variante into.

El caso más habitual en código real es agrupar, y ahí la diferencia es brutal:

// agrupar por inicial en una sola pasada, sin copias intermedias
let porInicial = palabras.reduce(into: [Character: [String]]()) { acc, p in
    acc[p.first ?? "?", default: []].append(p)
}

El subíndice con default: es otra pieza afinada: accede, muta en su sitio y evita el ciclo de leer, copiar, modificar y volver a escribir que produciría acc[k] = (acc[k] ?? []) + [p]. Cuando el acumulador es un valor simple —una suma, un máximo, un bool— reduce sin into es perfectamente idiomático y no copia nada.

sorted, partition y el orden que no te prometen

let ordenados = personas.sorted { $0.edad < $1.edad }   // O(n log n)

var datos = [5, 1, 9, 3, 7]
let p = datos.partition { $0 >= 5 }   // O(n), reordena en su sitio
// datos = [3, 1, ...] con los mayores o iguales a partir del indice p

sorted es O(n log n) en tiempo y O(n) en espacio adicional; su versión mutante sort ordena en su sitio. La implementación actual es un timsort modificado que de hecho es estable, pero la documentación no garantiza la estabilidad, y apoyarse en ella es construir sobre un detalle de implementación que puede cambiar. Si necesitas estabilidad, hazla explícita ordenando por una tupla que incluya el índice original.

partition(by:) es un algoritmo distinto y mucho más barato: reordena en su sitio en una sola pasada lineal y devuelve el índice de la frontera. No ordena, solo separa, y desordena libremente dentro de cada bloque. Cuando lo único que necesitas es “los que cumplen a un lado”, partir cuesta lineal donde ordenar costaría logarítmico de más.

Del mismo modo, min, max y prefix combinados con ordenación esconden una elección: si solo quieres los tres mayores de un millón de elementos, sorted().prefix(3) paga n log n para tirar casi todo, mientras que un recorrido lineal manteniendo tres candidatos cuesta lineal. La biblioteca no trae ese algoritmo hecho, y reconocer cuándo hace falta escribirlo es parte del oficio.

firstIndex, contains y el momento de cambiar de estructura

firstIndex(of:), first(where:), contains y min recorren desde el principio y paran en cuanto pueden: son lineales en el peor caso y muy baratos en el mejor. El problema no es una llamada, es una llamada dentro de un bucle:

// cuadratico: para cada id, un recorrido completo del array
let encontrados = ids.filter { id in usuarios.contains { $0.id == id } }

// lineal: una sola construccion de indice y busquedas constantes
let conjunto = Set(usuarios.map(\.id))
let rapido = ids.filter { conjunto.contains($0) }

El patrón se repite en todo código real: cuando una búsqueda vive dentro de una iteración, el remedio casi nunca es optimizar la búsqueda, es precalcular una estructura con acceso constante. Un Set o un Dictionary construido en tiempo lineal amortiza su coste en la primera decena de consultas.

Merece la pena recordar además los costes de mutación, porque también se esconden dentro de bucles:

var a: [Int] = []
a.append(1)          // constante amortizado
a.insert(0, at: 0)   // LINEAL: desplaza todos los elementos
a.removeFirst()      // LINEAL en Array; constante en ArraySlice
a.reserveCapacity(n) // evita las reasignaciones por crecimiento

Un insert(at: 0) dentro de un bucle es el mismo error cuadrático que un contains anidado, disfrazado de otra cosa. Si necesitas construir una secuencia al revés, añade al final y llama a reverse una sola vez.