Transformada schwartziana
De Viquipèdia
La transformada schwartziana és una tècnica en programació que s'utilitza per a l'ordenació eficient d'una matriu. Aquesta fa servir el resultat d'una operació de càlcul intensiu sense la necessitat d'efectuar-la per a cada comparació que fa la subrutina de comparació.
Aquesta pràctica rep el nom de Randal L. Schwartz, qui va popularitzar-la entre els programadors de Perl. No obstant, s'ha utilitzat en informàtica com a mínim des de l'estàndard Common Lisp. És un cas especial de memoització, que funcionaria per a qualsevol algorisme.
Per exemple, per a ordernar una llista de fitxers d'acord amb el seu moment de modificació, sense transformada seria (en pseudocodi):
funció ComparacióIngènua(fitxer a, fitxer b) {
retorna TempsModificació(a) < TempsModificació(b)
}
// S'assumeix que ordena(llista, PredicatComparació) ordena la llista fent servir
// el PredicatComparació per a comparar dos elements.
MatriuOrdenada := ordena(MatriuFitxers, ComparacióIngènua)
A menys que els temps de modificació es memoitzin per a cada fitxer, aquest mètode requereix tornar a calcular cada vegada que un fitxer es compara en l'ordenació. Com a alternativa, amb la transformada schwartziana:
per cada fitxer a MatriuFitxers
inserta Matrix(fitxer, TempsModificació(fitxer)) al final de MatriuTransformada
funció ComparacióSimple(matriu a, matriu b) {
retorna a[2] < b[2]
}
MatriuTransformada := ordena(MatriuTransformada, ComparacióSimple)
per cada fitxer a MatriuTransformada
inserta MatriuTransformada[1] al final MatriuOrdenada
Primer el bucle inicial itera cada element de MatriuFitxers i crea una referència d'una matriu anònima per a cada un. La matriu anònima té doncs dos elements: l'original de MatriuFitxers i el temps de modificació d'aqueix fitxer.
A continuació s'ordena la llista de referències de matrius anònimes que retorna el primer mapatge. La llista s'ordena d'acord amb els segons elements de cada matriu anònima.
Finalment la llista ordenada de referències de matrius s'itera en el darrer bucle. Aquest simplement construeix la matriu ordenada a partir del primer element de cada referència de les matrius, que és de fet el nom del fitxer.
Taula de continguts |
[edita] Implementacions
[edita] Perl
En aquest llenguatge pot fer-se de forma molt compacta tot de seguit, però a diferència del pseudocodi, ha de fer-se en «sentit invers».
@sorted_array =
map { $_->[0] } # extreu els elements de la llista original
sort { $a->[1] <=> $b->[1] } # ordena la llista per claus
map { [$_, -M $_] } # aparella els elements de la llista amb les claus
@files_array;
[edita] Python
En aquest exemple de Python, f(x) retorna una clau que pot utilizar-se per a l'ordenació. Aquesta podria retornar la mida de x, o bé fer una consulta a una base de dades amb el valor que contingui.
# python2.4
new_list = sorted(old_list, key=f)
# python2.3
new_list = [(f(x), x) for x in old_list]
new_list.sort()
new_list = [x[1] for x in new_list]
[edita] Ruby
El mètode sort_by method (des de la versió 1.8) hi implementa aquesta transformada.
new_list = old_list.sort_by {|file| file.mtime }
[edita] Enllaços externs
- (anglès) Explicació de la transformada schwartziana - per Mark-Jason Dominus
- (anglès) Transformada schwartziana a Python
