transformada de Schwartzian

En programación informática , la transformada de Schwartzian es una técnica utilizada para mejorar la eficiencia de ordenar una lista de elementos. Este modismo ^[1] es apropiado para la clasificación basada en comparación cuando la clasificación en realidad se basa en la clasificación de una determinada propiedad (la clave ) de los elementos, donde calcular esa propiedad es una operación intensiva que debe realizarse un número mínimo de veces. . La transformada de Schwartzian se destaca porque no utiliza matrices temporales con nombre.

La transformación Schwartziana es una versión de un modismo de Lisp conocido como decor-sort-undecorate , que evita volver a calcular las claves de clasificació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 garantiza que la clave de cada elemento de entrada se calcule exactamente una vez, lo que aún puede resultar en la repetición de algunos cálculos si los datos de entrada contienen elementos duplicados.

El modismo lleva el 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 "transformación schwartziana" 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 estaba en uso en otros lenguajes (sin ningún nombre específico) antes de que Schwartz lo popularizara entre la comunidad Perl en la forma de ese modismo particular. 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 la palabra: primero cree la lista (["aaaa",4],["a",1],["aa ",2]), luego ordénelo de acuerdo con los valores numéricos obteniendo (["a",1],["aa",2],["aaaa",4]), luego elimine los números y obtendrá ( "a", "aa", "aaaa"). Ese era el algoritmo en general, por lo que no cuenta como transformación. Para que sea una verdadera transformación Schwartziana, se haría en Perl así:

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

El idioma 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 ( $_ )] } @sin clasificar ;

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

Leyendo de derecha a izquierda (o de abajo hacia 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 el 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 producida por mapse introduce en sort, que la clasifica según los valores previamente calculados (lista de [elemento, valor] ⇒ lista ordenada de [elemento, valor]);
finalmente, otra mapoperación desenvuelve los valores (de la matriz anónima) utilizados para la clasificación, produciendo los elementos de la lista original en el orden ordenado (lista ordenada de [elemento, valor] ⇒ lista ordenada de elementos).

El uso de matrices anónimas garantiza que el recolector de basura de Perl recupere la memoria inmediatamente después de realizar la clasificación.

Análisis de eficiencia

Sin la transformada de Schwartz, la clasificación en el ejemplo anterior se escribiría en Perl así:

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

Si bien el código es más corto, 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 entre paréntesis se evalúa cada vez que es necesario comparar dos elementos. Una clasificación de comparación óptima realiza comparaciones O ( n log n ) (donde n es la longitud de la lista), con 2 llamadas a foo en cada comparación, lo que da como resultado llamadas O ( n log n ) a foo . En comparación, usando la transformación Schwartziana, 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 Schwartziana puede no estar justificada.

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 tiempo de modificación (a) <tiempo de modificación (b) }  // Supongamos que sort(list, comparePredicate) ordena la lista dada usando  // el comparativoPredicate para comparar dos elementos. sortedArray: = ordenar (filesArray, ingenuoCompare)

A menos que se memoricen los tiempos de modificación para cada archivo, este método requiere volver a calcularlos cada vez que se compara un archivo en la clasificación. Utilizando la transformada de Schwartzian, el tiempo de modificación se calcula solo una vez por archivo.

Una transformación Schwartziana implica el lenguaje funcional descrito anteriormente, que no utiliza matrices temporales.

El mismo algoritmo se puede escribir de forma procesal para ilustrar mejor cómo funciona, 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, hora de modificación (archivo)) al final de transformadaArray  función simpleCompare(matriz a, matriz b) { devolver a[2] < b[2] }  matriz transformada: = ordenar (matriz transformada, comparación simple)  para cada archivo en transformArray insertar archivo [1] al final de sortedArray

Historia

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

adjn:Joshua Ngadktk:KaLap Timothy Kwongadmg:Mahalingam Gobieramananadministrador: Martha L. Nangalama

Schwartz respondió con:

#!/usr/bin/perl requiere 5 ; # ¡Nuevas funciones, nuevos errores! imprimir mapa { $_ -> [ 0 ] } ordenar { $a -> [ 1 ] cmp $b -> [ 1 ] } mapa { [ $_ , /(\S+)$/ ] } <> ;

Este código produce el resultado:

admg:Mahalingam Gobieramananadktk:KaLap Timothy Kwongadministrador: Martha L. Nangalamaadjn:Joshua Ng

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

El término "transformación schwartziana" fue acuñado por Tom Christiansen en una respuesta de seguimiento. Publicaciones posteriores de Christiansen dejaron en claro que no había tenido la intención de nombrar la construcción, sino simplemente referirse a ella desde la publicación original: su intento de nombrarla finalmente "The Black Transform" no tuvo éxito ("Black" aquí es 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 Schwartzian:

En Python 2.4 y versiones posteriores, tanto la función sorted() como el método in situ list.sort() toman un parámetro key= que permite al usuario proporcionar una "función clave" (como foo en los ejemplos anteriores). En Python 3 y superiores, el uso de la función clave es la única forma de especificar un orden de clasificación personalizado (se eliminó el parámetro cmp= previamente admitido que permitía al usuario proporcionar una "función de comparación"). Antes de Python 2.4, los desarrolladores usaban el modismo decorar-ordenar-desdecorar (DSU) originado en lisp, ^[2] generalmente envolviendo los objetos en una tupla (clasificación, objeto).
En Ruby 1.8.6 y versiones posteriores, la clase abstracta Enumerable (que incluye Array s) 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.
A partir de D 2 está disponible la función de clasificación Schwarz . Podría requerir menos datos temporales y ser más rápido que el modismo Perl o el modismo decorar-ordenar-desdecorar presente en Python y Lisp. Esto se debe a que la clasificación se realiza in situ y solo se crea un mínimo de datos adicionales (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 que los valores resultantes se almacenen en caché durante la clasificación. Por ejemplo, una forma cómoda 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 clasificación inestables en PHP.

función  spaceballs_sort ( matriz &  $a ) :  void {  array_walk ( $a ,  función ( & $v ,  $k )  {  $v  =  matriz ( $v ,  $k );  });  surtido ( $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 requiere 1 argumento para realizar una transformación de Schwartzian bajo el capó:
```
@a . ordenar ( { $^a . Str } ) # o más corto: @a.sort(*.Str)
```
ordenaría la representación de la cadena usando una transformada Schwartziana,
```
@a . ordenar ( { $^a . Str  cmp  $^b . Str } )
```
haría lo mismo convirtiendo los elementos a comparar justo antes de cada comparación.
En Rust , de manera algo confusa, el método slice::sort_by_key no realiza una transformación Schwartziana ya que no asignará almacenamiento adicional para la clave, llamará a la función clave para cada valor para 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 Clasificación garantizando la estabilidad de la clasificación" . Libro de cocina de Python . O'Reilly y asociados. pag. 43.ISBN 0-596-00167-3. Este modismo también se conoce como "transformada Schwartziana", por analogía con un modismo relacionado de Perl.
^ "Cómo/Clasificar/Decorar Ordenar Desdecorar".
^ "Clases de Ruby-doc Core-API" . Consultado el 14 de septiembre de 2011 .

enlaces externos

La implementación/clasificación del algoritmo de Wikibook tiene una página sobre el tema: Transformada de Schwartzian

Ordenar con la transformada de Schwartz por Randal L. Schwartz
Mark-Jason Dominus explica la transformada Schwartziana
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234
Fundación de software Python (2005). 1.5.2 Quiero hacer una clasificación complicada: ¿puedes hacer una Transformada Schwartziana en Python? Consultado el 22 de junio de 2005.
Módulo Memoize Perl: agiliza funciones costosas almacenando en caché sus resultados.