En programación de computadoras , la transformada de Schwartzian es una técnica utilizada para mejorar la eficiencia de ordenar una lista de elementos. Esta expresión [1] es apropiada para la clasificación basada en la comparación cuando la ordenación se basa realmente en la ordenació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 es notable porque no utiliza matrices temporales con nombre.
La transformación de Schwartzian es una versión de un modismo de Lisp conocido como decorar-clasificar-undecorar , 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 tecla correspondiente a un valor de entrada específico. En comparación, esta expresión asegura 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 idioma 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 de 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 idiomas (sin un nombre específico) antes de que Schwartz lo popularizara entre la comunidad de Perl en la forma de ese idioma particular. El término "transformada de Schwartzian" indica un idioma 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 que obtiene (["a",1],["aa",2],["aaaa",4]), luego elimine los números y obtendrá ( "un","aa","aaaa"). Ese fue el algoritmo en general, por lo que no cuenta como una transformación. Para que sea una verdadera transformación Schwartziana, se haría en Perl así:
Aquí foo($_)representa una expresión que toma $_(cada elemento de la lista a su vez) y produce el valor correspondiente que se comparará en su lugar.
El uso de matrices anónimas garantiza que el recolector de elementos no utilizados de Perl recuperará la memoria inmediatamente después de realizar la clasificación.