Transformada de Schwartz

En programación informática , la transformada de Schwartz es una técnica que se utiliza para mejorar la eficiencia de la ordenación de una lista de elementos. Este modismo ^[1] es apropiado para la ordenación basada en la comparación cuando el ordenamiento se basa en realidad en el ordenamiento de una determinada propiedad (la clave ) de los elementos, donde el cálculo de esa propiedad es una operación intensiva que debe realizarse una cantidad mínima de veces. La transformada de Schwartz es notable porque no utiliza matrices temporales con nombre.

La transformada de Schwartz es una versión de un modismo de Lisp conocido como decorating-sort-undecorate , que evita tener que volver a calcular las claves de ordenación asociándolas temporalmente con los elementos de entrada. Este enfoque es similar a la memorización , que evita repetir el cálculo de la clave correspondiente a un valor de entrada específico. En comparación, este modismo asegura que la clave de cada elemento de entrada se calcule exactamente una vez, lo que puede dar como resultado la repetición de algunos cálculos si los datos de entrada contienen elementos duplicados.

El modismo recibe su nombre de Randal L. Schwartz , quien lo demostró por primera vez en Perl poco después del lanzamiento de Perl 5 en 1994. El término "transformada de Schwartz" se aplicó únicamente a la programación en Perl durante varios años, pero luego fue adoptado por algunos usuarios de otros lenguajes , como Python , para referirse a modismos similares en esos lenguajes. Sin embargo, el algoritmo ya se usaba en otros lenguajes (sin un nombre específico) antes de que se popularizara entre la comunidad Perl en forma de ese modismo particular de Schwartz. El término "transformada de Schwartz" indica un modismo específico, y no el algoritmo en general.

Por ejemplo, para ordenar la lista de palabras ("aaaa", "a", "aa") según la longitud de las palabras: primero se construye la lista (["aaaa", 4], ["a", 1], ["aa", 2]), luego se ordena según los valores numéricos obtenidos (["a", 1], ["aa", 2], ["aaaa", 4]), luego se eliminan los números y se obtiene ("a", "aa", "aaaa"). Ese era el algoritmo en general, por lo que no cuenta como una transformación. Para convertirla en una verdadera transformación de Schwartz, se haría en Perl de la siguiente manera:

@sorted = map { $_ -> [ 0 ] } sort { $a -> [ 1 ] <=> $b -> [ 1 ] o $a -> [ 0 ] cmp $b -> [ 0 ] } # Usar comparación numérica, volver a la ordenación de cadena en el mapa original { [ $_ , length ( $_ )] } # Calcular la longitud de la cadena @unsorted ;

El idioma de Perl

La forma general de la transformada de Schwartz es:

@sorted = mapa { $_ -> [ 0 ] } ordenar { $a -> [ 1 ] cmp $b -> [ 1 ] o $a -> [ 0 ] cmp $b -> [ 0 ] } mapa { [ $_ , foo ( $_ )] } @unsorted ;

Aquí foo($_)representa una expresión que toma $_(cada elemento de la lista por turno) y produce el valor correspondiente que se debe comparar en su lugar.

Leyendo de derecha a izquierda (o de abajo a arriba):

la lista original @unsortedse introduce en una mapoperación que envuelve cada elemento en una matriz (referencia a una matriz anónima de 2 elementos) que consta de sí mismo y del valor calculado que determinará su orden de clasificación (la lista de elementos se convierte en una lista de [elemento, valor]);
luego la lista de listas producidas por mapse alimenta a sort, que la ordena según los valores calculados previamente (lista de [elemento, valor] ⇒ lista ordenada de [elemento, valor]);
Finalmente, otra mapoperación desenvuelve los valores (de la matriz anónima) utilizados para la ordenación, produciendo los elementos de la lista original en el orden ordenado (lista ordenada de [elemento, valor] ⇒ lista ordenada de elemento).

El uso de matrices anónimas garantiza que el recolector de basura de Perl recuperará la memoria inmediatamente después de que se realice la clasificación.

Análisis de eficiencia

Sin la transformada de Schwartz, la ordenación en el ejemplo anterior se escribiría en Perl de la siguiente manera:

@sorted = ordenar { foo ( $a ) cmp foo ( $b ) } @unsorted ;

Si bien es más corto de codificar, el enfoque ingenuo aquí podría ser mucho menos eficiente si la función clave (llamada foo en el ejemplo anterior) es costosa de calcular. Esto se debe a que el código dentro de los corchetes se evalúa cada vez que se deben comparar dos elementos. Una ordenación por comparación óptima realiza O ( n log n ) comparaciones (donde n es la longitud de la lista), con 2 llamadas a foo en cada comparación, lo que da como resultado O ( n log n ) llamadas a foo . En comparación, al usar la transformada de Schwartz, solo hacemos 1 llamada a foo por elemento, en la etapa inicial del mapa , para un total de n llamadas a foo .

Sin embargo, si la función foo es relativamente simple, entonces la sobrecarga adicional de la transformada de Schwartz puede ser injustificada.

Ejemplo

Por ejemplo, para ordenar una lista de archivos por sus tiempos de modificación , un enfoque ingenuo podría ser el siguiente:

 función naiveCompare(archivo a, archivo b) { return modificationTime(a) < modificationTime(b) }  // Supongamos que sort(list, comparisonPredicate) ordena la lista dada usando  comparisonPredicate para comparar dos elementos. sortedArray := sort(archivosArray, naiveCompare)

A menos que se memoricen las horas de modificación de cada archivo, este método requiere volver a calcularlas cada vez que se compara un archivo en la clasificación. Con la transformada de Schwartz, la hora de modificación se calcula solo una vez por archivo.

Una transformada de Schwartz implica el lenguaje funcional descrito anteriormente, que no utiliza matrices temporales.

El mismo algoritmo se puede escribir de manera procedimental para ilustrar mejor su funcionamiento, pero esto requiere el uso de matrices temporales y no es una transformación de Schwartz. El siguiente pseudocódigo de ejemplo implementa el algoritmo de esta manera:

 para cada archivo en filesArray Insertar matriz(archivo, modificationTime(archivo)) al final de transformArray  función simpleCompare(matriz a, matriz b) { devolver a[2] < b[2] }  transformArray := sort(transformedArray, simpleCompare)  para cada archivo en transformArray Insertar archivo[1] al final de sortedArray

Historia

La primera aparición conocida en línea de la transformada de Schwartz es una publicación del 16 de diciembre de 1994 de Randal Schwartz en un hilo del grupo de noticias de Usenet comp.unix.shell , publicado también en comp.lang.perl. (La versión actual de la línea de tiempo de Perl es incorrecta y se refiere a una fecha posterior de 1995). El hilo comenzaba con una pregunta sobre cómo ordenar una lista de líneas por su "última" palabra:

adj.:Joshua Nganuncio:KaLap Timothy Kwongadmg:Gobernador de MahalingamAdm.: Martha L. Nangalama

Schwartz respondió:

#!/usr/bin/perl require 5 ; # ¡Nuevas características, nuevos errores! print map { $_ -> [ 0 ] } sort { $a -> [ 1 ] cmp $b -> [ 1 ] } map { [ $_ , /(\S+)$/ ] } <> ;

Este código produce el resultado:

admg:Gobernador de Mahalingamanuncio:KaLap Timothy KwongAdm.: Martha L. Nangalamaadj.:Joshua Ng

Schwartz señaló en la publicación que estaba "hablando con ceceo en Perl", una referencia a los orígenes del modismo en Lisp .

El término "transformada de Schwartz" fue acuñado por Tom Christiansen en una respuesta posterior. Publicaciones posteriores de Christiansen dejaron en claro que no había tenido la intención de nombrar el constructo, sino simplemente referirse a él desde la publicación original: su intento de finalmente llamarlo "Transformada Negra" no prosperó ("Negra" es aquí un juego de palabras con "schwar[t]z", que significa negro en alemán).

Comparación con otros idiomas

Algunos otros lenguajes proporcionan una interfaz conveniente para la misma optimización que la transformada de Schwartz:

En Python 2.4 y versiones posteriores, tanto la función sorted() como el método list.sort() en el lugar toman un parámetro key= que permite al usuario proporcionar una "función clave" (como foo en los ejemplos anteriores). En Python 3 y versiones posteriores, el uso de la función key es la única forma de especificar un orden de clasificación personalizado (se eliminó el parámetro cmp= compatible anteriormente que permitía al usuario proporcionar una "función de comparación"). Antes de Python 2.4, los desarrolladores usaban el modismo de decorar-ordenar-desdecorar (DSU) originado en Lisp, ^[2] generalmente envolviendo los objetos en una tupla (sortkey, object).
En Ruby 1.8.6 y versiones superiores, la clase abstracta Enumerable (que incluye Arrays ) contiene un método sort_by ^[3] , que permite especificar la "función clave" (como foo en los ejemplos anteriores) como un bloque de código.
En D 2 y versiones posteriores, está disponible la función Schwartz Sort . Puede requerir menos datos temporales y ser más rápida que el modismo Perl o el modismo decorar-ordenar-desdecorar presente en Python y Lisp. Esto se debe a que la ordenación se realiza en el lugar y solo se crean datos adicionales mínimos (una matriz de elementos transformados).
La función principal de Racketsort acepta un #:keyargumento de palabra clave con una función que extrae una clave y una #:cache-keys?solicitud adicional de que los valores resultantes se almacenen en caché durante la ordenación. Por ejemplo, una forma conveniente de mezclar una lista es .(sort l < #:key (λ (_) (random)) #:cache-keys? #t)

En PHP 5.3 y superiores, la transformación se puede implementar mediante el uso de array_walk , por ejemplo, para solucionar las limitaciones de los algoritmos de ordenamiento inestables en PHP.

función  spaceballs_sort ( matriz &  $a ) :  void {  array_walk ( $a ,  función ( & $v ,  $k )  {  $v  =  matriz ( $v ,  $k );  });  asort ( $a );  array_walk ( $a ,  función ( & $v ,  $_ )  {  $v  =  $v [ 0 ];  }); }

En Elixir , los métodos Enum.sort_by/2 y Enum.sort_by/3 permiten a los usuarios realizar una transformación Schwartziana para cualquier módulo que implemente el protocolo Enumerable .
En Raku , es necesario proporcionar un comparador lambda que solo toma 1 argumento para realizar una transformación Schwartziana bajo el capó:
```
@a . sort ( { $^a . Str } ) # o más corto: @a.sort(*.Str)
```
ordenaría la representación de cadena utilizando una transformada de Schwartz,
```
@a . sort ( { $^a . Str  cmp  $^b . Str } )
```
haría lo mismo convirtiendo los elementos a comparar justo antes de cada comparación.
En Rust , de manera un tanto confusa, el método slice::sort_by_key no realiza una transformación de Schwartz, ya que no asignará almacenamiento adicional para la clave, sino que llamará a la función de clave para cada valor en cada comparación. El método slice::sort_by_cached_key calculará las claves una vez por elemento.
En Haskell , la sortOnfunción de la biblioteca base realiza una transformación Schwartziana.

Referencias

^ Martelli, Alex; Ascher, David, eds. (2002). "2.3 Ordenar garantizando la estabilidad de la ordenación" . Libro de recetas de Python . O'Reilly & Associates. pág. 43. ISBN 0-596-00167-3Este modismo también se conoce como "transformada de Schwartz", por analogía con un modismo de Perl relacionado.
^ "Cómo ordenar, decorar, ordenar y desdecorar".
^ "Ruby-doc Core-API Classes" . Consultado el 14 de septiembre de 2011 .

Enlaces externos

El Wikilibro Implementación/Ordenamiento de algoritmos tiene una página sobre el tema: Transformada de Schwartz

Ordenación con la transformada de Schwartz por Randal L. Schwartz
Mark-Jason Dominus explica la transformada de Schwartz
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234
Python Software Foundation (2005). 1.5.2 Quiero hacer una ordenación complicada: ¿se puede hacer una transformada de Schwartz en Python?. Consultado el 22 de junio de 2005.
Módulo Memoize de Perl: hace que funciones costosas sean más rápidas almacenando en caché sus resultados.