Ordenando e-mails (Ejemplo de SORT)

[Ernesto Hernandez-Novich]

Una pregunta frecuente es ¿cómo usar sort pero que _no_ sea para un orden
numérico ni alfanumérico puro? La función sort() de Perl ordena por defecto
en forma _alfanumérica_ ascendente, pero en ocasiones es necesario un
orden diferente por cualesquiera otro criterio, en particular cuando uno
trabaja con estructuras de datos complejas. Además, no tiene _ningún_
sentido implementar mysort() nuevamente, porque el sort de Perl utiliza
el algoritmo QuickSort (el más rápido que existe :-), de manera que cualquier
otro que uno implemente sería más lento...

Para este ejemplo, presento un caso concreto: ordenar una lista arbitraria
de direcciones de correo en orden de _dominio_, y luego alfabéticamente
por usuario. Es decir, si tengo una lista como

x at aqui.net
b at dominio.com
a at dominio.com
c at otro.sitio.aqui.net
d at uno.mas.ve

Se quiere un resultado como

d at uno.mas.ve
a at dominio.com
b at dominio.com
x at aqui.net
c at otro.sitio.aqui.net

Nótese que el punto no es ordenar _alfabéticamente_ los dominios, sino
que todos los dominios de igual nombre esten _juntos_ y los subdominios
aparezcan después de su dominio principal. En el problema concreto que
se quería resolver, la lista de correos se distribuye _muchísimo_ más
rápido si se tiene este orden previamente; por supuesto, si se quiere
ordenar los dominios alfabéticamente se puede (se deja de ejercicio para
el lector :-). (Los lectores observadores se darán cuenta que los
dominios están ordenados alfanuméricamente de "derecha a izquierda").

Este es el programa para solucionarlo:

#!/usr/bin/perl

# Rutina para ordenar por dominio. La rutina será invocada desde sort,
# por lo tanto debe operar con dos variables $a y $b, retornando
# 0 si son iguales, -1 si $a es menor que $b o 1 si $a es mayor que $b.

sub bydomain () {
  my ($au,$ad) = split /@/,$a;  # Se separa usuario de dominio
  my ($bu,$bd) = split /@/,$b;

  # Invierto los dominios y los comparo.
  # Si son _diferentes_ $ret será 1 o -1, y lo retorno directamente
  # para que sort continúe trabajando. Como he comparado según los
  # dominios invertidos dom.com y sub.dom.com realmente son
  # comparados como moc.mod y moc.mod.bus, por lo tanto los
  # subdominios siempre son _mayores_ que sus dominios padres y quedan
  # en el orden deseado ;-)
  if ($ret = (reverse($ad) cmp reverse($bd))) {
    return $ret;
  } else {
    # Pero si son iguales, debo ordenar los nombres de usuario
    return ($au cmp $bu);
  }
}

@all = <>;                # Leo _todo_ en un arreglo, un e-mail por elemento
map { chomp } @all;       # Le quitamos el \n a todas las líneas del arreglo
map { $_ = ~ tr/A-Z/a-z/; # Ponemos todas las líneas en minúscula
@all = sort bydoman @all; # Ordeno el arreglo "por dominio" usando el
                          # sort de Perl pero mi función de comparación.

# Ya lo que queda es trabajar con la lista ordenada

foreach $email (@all) {
  print "$email\n";
}


Ciertamente, mientras mayor sea la lista más memoria consume porque la
estoy cargando de una sola vez en memoria. Si quisiera hacer el ordenamiento
sobre algo que no cabe en memoria RAM, no me queda más remedio que usar
archivos parciales, cargarlos en memoria, ordenarlos, y luego usar  un
merge sort para combinar los archivos en uno final. Para el caso concreto
que había que resolver (una docena de listas, la más larga con 600+
elementos) el consumo era irrisorio.

Incidentalmente, el uso de map es _muchísimo_ más eficiente que usar
un for para iterar sobre la lista y aplicar los cambios a cada uno (esto
es heredado de LISP y ML); es lo que se llama un "iterador implícito" y
es una construcción esencial en la programación funcional. Les invito
a comparar ambos map con unos simples for/foreach para que vean la
diferencia.

El uso de funciones de ordenamiento agrega una increíble flexibilidad
al momento de manipular estructuras de datos complejas. Supongan que
tienen una lista de referencias a hashes, y que en cada hash tienen
una clave "Edad" y desean ordenar según edades... entonces la funcion
para ordenar recibe dos variables $a y $b que son _referencias_ a hashes:

sub byage () {
  return ($a->{Edad} <=> $b->{Edad});
}

Y si @personas es el arreglo de referencias a hashes, ordenarlo por
edades es tan simple como

@personas = sort byage @personas;

Trivial ;-) Supongan ahora que el hash tiene varias claves numéricas (Edad,
Sueldo, etc.) y que tienen que ordenarlo a cada rato
por una clave diferente. La solución inocente es tener _varias_
funciones de ordenamiento separadas... sin embargo, podemos aprovechar
el lenguaje de la siguiente forma:

sub nicehack ($$) {
  my ($clave,$refarreglo) = @_;

  return ( sort { return ($a->{$clave} <=> $b->{$clave} ) } @$refarreglo );
}

@poredad = nicehack('Edad',\@personas);
@porsueldo = nicehack('Sueldo',\@personas);

Más detalles del uso de sort en man perlfunc.
-- 
Ernesto Hernández-Novich - Running Linux 2.2.18 i686 - Unix: Live free or die!
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/E d+(++) s+: a C+++$ UBLAVHIOSC*++++$ P++++$ L+++$ E- W+ N++ o K++ w--- O-
M- V PS+ PE Y+ PGP>++ t+ 5 X+ R* tv+ b++ DI+++$ D++ G++ e++ h r++ y+
-----END GEEK CODE BLOCK-----


------------------------------------------------------------------------
Enviar e-mail a <majordomo at pm.org> colocando en el cuerpo:
"UNSUBSCRIBE caracas-pm-list" para desuscribirse.
"INFO caracas-pm-list" para conocer las reglas de etiqueta.
------------------------------------------------------------------------