Ordenación de datos avanzada en Perl

Salvador Fandiño (sfandino@yahoo.com) – Madrid.pm – 10.7.2008

Builtin sort

Se trata de una operacion generica que permite resolver cualquier problema de ordenacion:

sort { CMP($a, $b) } @a

o

sub my_cmp ($$) { CMP($_[0], $_[1]) };
sort my_cmp @a`

Basado en sortsv

Codigo en pp_sort.c

Funcionalmente la interfaz C es identica a la de Perl.

Basado en mergesort [O(NlogN), estable] a no ser que se demande otra implementación como quicksort [O(NlogN), no estable, algo mas rápida en general, mal comportamiento en casos extremos O(N^2)]:

use sort '_quicksort';

Vease tambien perldoc sort.

Tiene optimizaciones para casos algunos casos especiales:

• datos semiordenados [O(N)]

@a = (9,1,2,3,4,5,6,7,0)

• en orden creciente o decreciente

@a = (0,7,6,5,4,3,2,1,9)

• algoritmo optimizado para aprovechar las caches del procesador (problematica documentada en el codigo fuente).

En general...

(volvemos a hablar del sort de Perl)

sort @a

es mucho mas rapido que

sort { CMP($a, $b) } @a

porque en el segundo caso se ejecuta codigo Perl para realizar la comparacion dentro del bucle con complejidad O(NlogN) del mergesort, mientras que en el primer caso no, la comparacion es una subrutina en C minima.

Pero tiene optimizaciones para casos frecuentes:

• ordenar cadenas (asc y desc)

sort @a
sort { $b cmp $a } @a

• ordenar cadenas con locale (asc y desc)

• ordenar numeros (asc y desc)

sort { $a <=> $b } @a

• ordenar enteros (asc y desc)

• reverse sort

reverse sort @a

• inplace sort

@a = sort @a

Tecnicas para conseguir ordenar mas rapido

Todas se basan en el mismo principio: reducir (o eliminar completamente) el codigo Perl del comparador.

Paper clasico sobre el tema: A Fresh Look at Efficient Perl Sorting de Uri Guttman y Larry Rosler.

The Schwartzian Transform (ST)

@a = map $_->[1],
     sort { $a->[0] cmp $b->[0] }
     map [ KEY($_), $_] @data;

Ventajas:

• aumento considerable de velocidad

• de aplicacion general

• facil de usar

• tecnica generica decorate-process-undecorate

Desventajas:

• utiliza muchas memoria, no sirve para listas muy grandes (los algoritmos de ordenacion se llevan fatal con el swap).

• aumentar la cantidad de memoria referenciada desde el sort tambien relentiza la ordenacion por el efecto de las caches del procesador.

• si no se conoce el idioma es dificil entender que hace el codigo.

The Orcish Maneuver (OM)

my %k;
@a = sort { ($k{$a} ||= KEY($a))
               cmp
            ($k{$b} ||= KEY($b)) } @data

en mi opinion, buena idea mal llevada a la practica:

my %k;
$k{$_} = KEY($_) for @data;
@a = sort { $k->{$a} <=> $b->{$b} } @data;

es mas facil de entender y mas rapida.

La OM usa mucha menos memoria que la ST pero es un poco mas lenta porque los accesos a un hash son mas lentos que los accesos a un array.

Solo se puede utilizar cuando los objetos que se ordenan se pueden convertir a cadenas de forma univoca (relaccion inyectiva). Por ejemplo, tiene problemas cuando se ordenan objetos que utilizan overload.

Otra transformacion (... anonima)

my @k = map KEY($_), @data;
@a = @data[ sort { $k[$a]
                     cmp
                   $k[$b] } 0..$#data
          ];

Ventajas:

• igual de rapida (o mas) que la ST, usa accesos a arrays (sin indireccion)

• usa muy poca memoria (un array para las claves de ordenacion, otro array para los indices, que probablemente ocupa menos que un hash).

• el slice es una operacion muy rapida.

Inconvenientes:

• codigo complicado

• poco popular.

The Guttman-Rosler Transform (GRT)

@a = map (split /\|/),
  sort
    map KEY_AS_STRING($_).”|$_”, @data

Ventajas:

• muy rapida, no se ejecuta codigo Perl dentro del bucle O(NlogN)

• consumo de memoria bajo array con las claves y los datos a ordenar concatenados

Inconvenientes:

• muy complicada

• generar las claves de ordenacion en formato cadena puede ser complicado, especialmente si:

  • se mezcla con unicode

  • las claves de ordenacion dependen del byte-order de la maquina

  • o de la estructura de algun tipo como los numeros en punto flotante.

• hacer el join clave|valor, que luego se pueda deshacer tambien tiene su complicacion

• si los datos a ordenar no son scalares, hay que ordenar indices y luego hacer un slice:

@a = @data[ map (split /\|/),
              sort
                map KEY_AS_STRING($data[$_]).”|$_”,
                    0..$#data
          ];

En definitiva es un metodo que hay que adaptar a cada caso concreto para que sea efectivo.

Algunos idiomas usuales

multikey sorting

                @a = sort { K1($a) cmp K1($b)
                                   or
                            K2($a) cmp K2($b)
                                   or
                                   ...
                           } @data;

ordenaciones “raras”

A veces es necesario ordenar cosas que no siguen el orden habitual de cadenas ASCII o de numeros:

@a = sort { collate($a) cmp collate($b) } @data;

Otras consideraciones a la hora de ordenar

• usa la base de datos si puedes

    SELECT ... ORDER BY ... 

• en serio, usa la base de datos si puedes!!!

• usar el comando sort del sistema operativo tambien es una buena idea si los datos de entrada ya estan en un fichero, son simples y es facil determinar donde empiezan y donde acaban las claves de ordenacion. Como contrapartida usar un comando externo siempre tiene problemas de portabilidad y el coste de lanzar un proceso externo.

• Si no cabe en la memoria RAM no lo ordenes con el sort de Perl.

Modulos en CPAN

Sort::Naturally

Ordena los datos partiendo las cadenas en subcadenas y numeros y ordenandolos de acuerdo a estas subcadenas.

Por ejemplo:

            file4  => file  4
            file14 => file 14
    
            ==> file4 < file14

Ventajas:

• popular
• DWIM

Inconvenientes:

• muy lento
• DWIM siempre que “what I mean” es lo que haria un Mac.

Sort::Maker

Generador de funciones de ordenacion generico y multi clave

Ventajas:

• recomendado por Damian Conway en Perl Best Practices... ummm... Damian y Uri son amigos!

• genera funciones de ordenacion que implementan las transformaciones descritas con anterioridad

• pure Perl

• se puede ver el codigo fuente de las funciones generadas para pegar en tu propio codigo y eliminar la dependencia del modulo o con fines educativos

Inconvenientes:

• la interfaz de uso es bastante engorrosa

• para usarlo bien hay que conocer que es lo que hace por debajo, especialmente para generar GRTs

Sort::Key & family

Modulos muy rapidos para ordenacion generica y multi clave

@a = keysort { KEY($_) } @data;

• muy, muy, muy rapido!!!

• consumo de memoria minimo

• interfaz facil de usar

• soporte para varios tipos de datos no basicos pero comune (direcciones IP, oids, natural)

• extensible para soportar nuevos tipos de datos.

Inconvenientes:

• interfaz facil de usar... una vez que entiendes como va!

• XS

• solo soporta un conjunto limitado de comparaciones (equivalentes a cmp, cmp con locale y <=>, asc y desc).

Sort::External

Imprescindible si tus datos no entran en memoria, usa almacenamiento temporal en disco

Ventajas:

• muy rapido (hasta donde puede llegar un metodo de ordenacion externa)

• varias opciones para ajustar su funcionamiento (por ejemplo, uso de memoria RAM).

Inconvenientes:

• usa XS

• interfaz de bajo nivel. Hay que usar GRT para conseguir el rendimiento optimo

• los datos tienen que ser serializables

Otros

• Sort::Versions – ordena cadenas de version que no es facil!

• Sort::Packed – ordena arrays de datos “enpacados” en scalares. Muy rapido.

Sort::Key en detalle

Se trata de varios modulos:

• Sort::Key – funciones para ordenar datos por mono-clave y generadores de bajo nivel de funciones de ordenacion multi-clave.

• Sort::Key::Register – syntax sugar para registrar nuevos tipos y su metodo de ordenacion

• Sort::Key::Maker – syntax sugar para crear funciones de ordenacion multiclave

• Sort::Key::Multi – systax sugar para crear funciones de ordenacion multiclave para tipos comunes.

• Sort::Key::Merger – combinado con Sort::Key permite realizar ordenaciones externas... pero Sort::External (a dia de hoy) es mas rapido.

• Sort::Key::Radix – similar a Sort::Key pero realiza las ordenaciones empleando el metodo radixsort que en muchos casos es mas rapido que el mergesort.

• Sort::Key::Top – implementa algoritmos de seleccion que permiten encontrar que elemento ocuparia una posicion en una lista una vez ordenada pero sin realizar la ordenacion (por ejemplo, la mediana).

• Sort::Key::OID, Sort::Key::IPv4, Sort::Key::Natural, Sort::Key::LargeInt – añaden soporte para varios tipos de datos comunes.

Uso de Sort::Key

Dos funciones basicas:

• sortkey – ordena comparando las claves como cadenas de texto (PVs)

• nsortkey – ordena comparando las claves como numeros (NVs)

y algunas mas que son optimizaciones de las anteriores:

• isortkey – ordena comparando las claves como numeros enteros con signo (IVs)

• usortkey – ordena ... enteros sin signo (Uvs)

• lsortkey – ordena comparando las claves como cadenas de texto y teniendo en cuenta el locale

• para invertir el sentido de la ordenacion (desc), se añade el prefijo 'r': rsortkey, rnsortkey, risortkey, rusortkey, etc.

• los mismos nombres con la terminacion _inplace ordenan un array “in place”

    keysort_inplace { $_->age() } @people;

Ejemplos:

• ordenar cadenas por su longitud:

@a = ukeysort { length $_ } @data;

• ordenar cadenas por su valor invertido:

@a = keysort { reverse $_ } @data;

Ordenacion multiclave con Sort::Key::Multi

Multiples prefijos → multiples claves

ordenar lista de nombres como “Pedro Picapiedra”

    use Sort::Key::Multi qw(sskeysort);
    @a = sskeysort { (split /\s+/)[1,0] } @names;

Ordenacion multiclave con Sort::Key::Maker

Ejemplo:

    use Sort::Key::Maker name_sorter =>
                  sub { (split /\s+/)[1,0] },
                  qw(string string);
    
    @a = name_sorter @names;

• soporta tipos definidos por el usuario con Sort::Key::Register

• para indicar que se quiere orden descendente, se añade un signo menos '-' delante del tipo correspondiente.

• la referencia a la funcion de extraccion de la clave puede pasarse en el use o (=xor) cuando se llama a la funcion de ordenacion.

        Use sort::Key::Maker riskeysort =>
                                qw(-integer string);
    
        @a = riskeysort { length $_, scalar(reverse $_) } @data;

Como funciona Sort::Key por dentro

• tambien basada en sortsv

• las claves son convertidas en typos basicos de C y almacenadas en arrays

• comparaciones especificas para cada tipo de datos en C

• el algoritmo es muy similar a la transformacion

my @k = map KEY($_), @data;` 
@a = @data[ sort { $k[$a]
                    cmp
                   $k[$b] } 0..$#data
          ];