Ordenamiento de listas enlazadas simplesLeandro Rabindranath León |
Aunque en posts previos he presentado esquemas de ordenamientos para listas enlazadas, voy a permitirme este para explicar cómo instrumentar el quicksort y el mergesort sobre listas simplemente enlazadas.
Contents
- 1 Doble o simplemente enlazada, ¿cuál y cuándo usar una o la otra?
- 2 Estructura e interfaz de la lista
- 3 Quicksort
- 4 Mergesort
- 5 ¿Cuál utilizar: quicksort o mergesort?
1 Doble o simplemente enlazada, ¿cuál y cuándo usar una o la otra?
En general, las listas enlazadas deben usarse cuando se manejan secuencias de longitud variable; es decir, cuando no tenemos idea precisa o aproximada acerca de la cantidad de elementos que manejaremos. Si tenemos idea precisa sobre la escala o al menos podemos acotarla y su escala no es muy fluctuante, entonces es preferible un arreglo; ocupa menos memoria y tenemos otras ventajas. Por el contrario, cuando la escala es desconocida o fluctuante, entonces la lista enlazada es la escogencia para representar secuencias.
Con listas enlazadas tenemos dos sabores: simple o doble. ¿Cuándo simple y cuándo doble? Esencialmente yo manejo una sola razón para usar listas doblemente enlazadas, cual es la necesidad de eliminar lo más eficientemente posible en cualquier posición de la lista. Este es caso, por ejemplo, de una dicola o dipolo, en el cual se eliminan elementos por las dos puntas de la secuencia. Notemos que es sólo la eliminación en O(1), por ambos extremos, la que exige el doble enlace. Cuando se trata de añadidura es posible insertar en una lista simple por ambos extremos.
Alguien pudiera objetar la eliminación en cualquier posición y para ello plantearía la necesidad de recorrer la lista desde alguno de sus extremos para poder encontrar el elemento deseado. Esto no es necesariamente correcto.
Supongamos por ejemplo que deseamos mantener un cache de entradas leídas a un archivo (o fichero si eres español). Usamos una tabla hash para buscar en O(1) en el cache. Puesto que el cache es finito y muchísimo más pequeño que el archivo, éste se llenará en algún momento. Así que surge la pregunta, ¿cuál entrada sustituimos?. En los cursos de sistemas operativos se aprende las bondades de la política LRU; o sea “Least Recently Used” o “menos recientemente utilizada”. En cristiano: eliminamos la entrada que tiene más tiempo dentro del cache sin ser accedida. Ajá, pero ¿cómo determinamos cuál la más antigua? ¿y la más nueva? Bueno, una solución es una lista doblemente enlazada ordenada por acceso. Cuándo se añade una nueva entrada al cache se inserta en la cola. De este modo, el frente de la cola contiene el elemento más antiguo. ¿Y los accesos? Bueno, cada vez que realizamos un acceso eliminamos la entrada de la cola y la reinsertamos. De este modo, la entrada recién accedida deviene en la cola la más reciente o la más nueva. La búsqueda en la tabla hash nos permite recuperar la entrada en O(1). En ese momento, puesto que la entrada pertenece a una lista doble, tenemos todo el contexto necesario para eliminarla de la lista.
Como en la anterior, hay otra situaciones más a menudo reservadas a mundos de programación de élite: compiladores, sistemas operativos, manejadores gráficos, bases de datos y otros tantos.
Hay otra gran ventaja de una lista doble y que es justo que forme parte del criterio para decidir si usarla o no: es más sencilla de implementar que la simple. Por tanto, si requerimos una lista y no encontramos en una situación de prototipado la escogencia es la doble.
Ahora bien, en el mundo de producción el espectro de situaciones que realmente ameritan una lista doble es bastante reducido. Yo diría que la probabilidad de encontrarse en una situación de programación que amerite una lista doblemente enlazada oscila entre el 1 % y el 5 %. Lo que a efectos prácticos significaría que el 95 % de las veces usaremos listas simples ... y en el 95 % de las veces que requiramos ordenar listas será sobre listas simples. Ordenar listas simples es pues una necesidad.
Muchos programadores se desaniman por los rumores de dificultad que tienen las listas simples y optan por listas dobles cuando requieren ordenarlas. Lo cual es lamentable, pues ordenar listas simples es tan o más fácil que ordenar las dobles. Veamos.
2 Estructura e interfaz de la lista
En este post quizá sí sea adecuado un poco más de detalle sobre la representación de la lista.
2.1 El nodo
Comencemos por la representación del nodo:
class Slinknc
{
Slinknc * next;
public:
// ...
};
template <typename T>
class Snodenc : public Slinknc
{
T data;
public:
// ...
};
Separamos el nodo en dos clases porque a veces sólo requerimos el enlace. El resto de la interfaz no es necesario para el contexto de este escrito.
2.2 La lista
La siguiente clase está tomada directamente de Aleph-w:
class HTList
{
Slinknc * head;
Slinknc * tail;
public:
};
El nombre HTList es de Head-Tail list.
head apunta al primer elemento de la lista y tail al último. Cuando la lista se construye o está vacía los valores de head y tail son nulos.
La lista maneja objetos de tipo Slinknc ; o sea, sólo maneja enlaces simples. Los contenidos de los nodos, es decir el dato, jamás son accedidos por HTList. No se requiere conocer el dato para efectuar operaciones sobre HTList. De este modo podríamos, por ejemplo, manejar nodos que pertenezcan a varias listas. Para ello, el nodo contiene tantos enlaces simples, o sea, objetos de tipos de Slinknc m como listas donde pueda pertenecer.
Para listas que manejen memoria dinámica, Aleph-w exporta el siguiente tipo de dato:
template <typename T>
class DynList : public HTList
{
// ..
};
El cual representa secuencias de elementos de tipo genérico T implementadas mediante listas simplemente enlazadas. En esta clase se maneja la memoria y se oculta el nodo; sólo se muestran los datos de tipo genérico T. La herencia pública hace que DynList sea también un objeto de tipo HTList. Por consiguiente métodos y funciones que operen sobre objetos de tipo HTList también operan sobre elementos de tipo DynList.
Alguien podrá observar que para ordenar requerimos mirar el dato del nodo, lo cual es correcto, pero mantendremos la independencia con el dato a través de la comparación, operación que dilucidaremos cuando llegue el momento. Por lo pronto, es importante aceptar que no necesitamos conocer el tipo de dato para operar listas de tipo HTList.
2.2.1 Algunos observadores
Una primera manera de aprehender la independencia entre las operaciones sobre una lista enlazada y el dato que se maneja e mirando los siguientes métodos observadores:
/// Retorna true si la lista está vacía
bool is_empty() const { return head == NULL; }
/// Retorna true si la lista contiene exactamente un solo elemento
bool is_unitarian() const { return head != NULL and head == tail; }
/// Retorna true si la lista tiene un elemento o está vacía
bool is_unitarian_or_empty() const { return head == tail; }
/// Retorna el primer elemento de la lista
Slinknc * get_first() const { return head; }
/// Retorna el último elemento de la lista
Slinknc * get_last() const { return tail; }
2.2.2 Inserción
Hay dos tipos de inserción, por el frente o por el final. La inserción por el final es así:
// inserta link al final de la lista this
void append(Slinknc * link)
{
if (head == NULL)
{
head = tail = link;
return;
}
NEXT(tail) = link;
tail = link;
}
NEXT(p) es un macro que nos edulcora p->next. La inserción por el frente te la dejamos en ejercicio.
2.2.3 Eliminación
Como ya lo explicamos al inicio, con listas simples sólo es posible eliminar por el frente:
// Elimina y retorna el primer elemento de la lista this
Slinknc * remove_first()
{
if (is_empty())
throw std::underflow_error("HTList is empty");
Slinknc * ret_val = head;
if (head == tail) // Lista con un solo elemento?
head = tail = NULL;
else
{
head = NEXT(head);
if (head == NULL)
tail = NULL;
}
ret_val->reset();
return ret_val;
}
Una manera de aprehender la versatilidad de la lista simple es estudiando cómo esta puede implementar una pila o una cola.
Para ver la lista como una pila siempre insertamos por el frente (con insert(), que no está mostrado). La eliminación siempre sacara el elemento más joven dentro de la secuencia, o sea el último que fue insertado.
Para verla como cola siempre insertamos por el final (con append()). La eliminación por el frente sacará el elemento más antiguo de la secuencia.
2.2.4 Concatenación de listas
Puesto que tenemos las direcciones del primer y último elemento, podemos concatenar dos listas en O(1):
// concatena la lista l la lista this. l deviene vacía
void append(HTList & l)
{
if (l.is_empty())
return; // si l está vacía ==> this es el resultado
if (this->is_empty())
{ // si this está vacía ==> l es el resultado
this->swap(l);
return;
}
NEXT(tail) = l.head;
tail = l.tail;
l.head = l.tail = NULL; // vaciar l
}
void concat_list(HTList & l) { append(l); } // Sinónimo
La sobrecarga de append() implementa la concatenación. En algunas circunstancias, ésta por ejemplo, conviene ser más específico e indicar que se trata de una concatenación. De allí pues el sinónimo.
3 Quicksort
Comencemos por el quicksort, el cual es el método más fácil de implementar. Grosso modo, el quicksort es estructuralmente simple y se resume del siguiente modo:
template <typename T, class Compare>
void quicksort(HTList & list, Compare & cmp)
{
if (list.is_unitarian_or_empty())
return;
Snodenc<T> * pivot = // seleccionar pivote y particionar lista
quicksort <T, Compare> (bigger, cmp);
quicksort <T, Compare> (smaller, cmp);
list.concat_list(smaller); // restaurar listas ordenadas en list
list.append(pivot);
list.concat_list(bigger);
}
Como ya lo debes saber, el trabajo del quicksort lo realiza el proceso de partición. cmp es el criterio de comparación entre los elementos.
Un paréntesis. Al momento de redacción de este post, yo ya he incorporado a Aleph-w muchas funcionalidades del nuevo estándar C++llamado C++11. Esa es en parte la razón por la cual el criterio de comparación se pasa como parámetro. Una sobrecarga del método de ordenamiento se plantea así:
template <typename T, class Compare = Aleph::less<T>>
void quicksort(DynList<T> & list, Compare && cmp = Compare())
{
quicksort<T, Compare>((HTList&) list, cmp);
}
Esta sobrecarga conlleva dos ventajas. En primer lugar, puedo escribir algo como quicksort(lista);, en cuyo caso el criterio de comparación es el operador relacional “menor que” invocado sobre el tipo de elementos que maneja la lista. El segundo, y esto es grandioso, puedo escribir una función de primer orden para especificar el criterio de ordenamiento. Supongamos que tenemos una lista DynList que guarda registros de tipo Persona y que deseo ordenar por un campo llamado apellido. Podría escribirlo así:
quicksort(lista, [] (const Persona & p1, const Persona & p2)
{
return p1->apellido < p2->apellido;
});
En previos posts hablé sobre una limitación que tiene la partición sobre listas enlazadas, cual es la dificultad para seleccionar un buen pivote en tiempo constante. Con una lista sólo podemos mirar en tiempo constante los primeros elementos de la lista o exactamente el último.
Recordemos que la eficiencia del quicksort con listas enlazadas depende más de la suerte conque venga la permutación y no hay mucho que podamos hacer al respecto sin pagar tiempo adicional O(n).
Asumiendo que el pivote es el primer elemento, la partición se realizaría del siguiente modo:
Snodenc<T> * pivot = (Snodenc<T> *) list.remove_first();
HTList smaller, bigger; // listas de menores y mayores que pivot
while (not list.is_empty())
{
Snodenc<T> * p = (Snodenc<T> *) list.remove_first();
if (cmp(p->get_data(), pivot->get_data()))
smaller.append(p);
else
bigger.append(p);
}
Plantéate como ejercicio el seleccionar como pivote el último elemento de la lista. Es fácil.
Con buena suerte, el quicksort será O(nlgn). Con mala suerte puede tender a O(n2), coste tan terrible que amerita revisar las cosas. Al respecto tenemos dos alternativas:
- Mejorar la selección del pivote
- Utilizar un método más seguro; por instancia, el mergesort.
El pivote idóneo es la mediana de la secuencia. Muchos programadores “perfeccionista” han tratado de calcular este pivote y han caído en algunas trampas que vale la pena señalarlas.
Podemos hacer una barrido de toda la secuencia y encontrar la mediana en nlgn. Hay básicamente dos maneras, ambas innecesarias para esta situación, de acometer el problema puntual de encontrar la mediana. Una primera es usar un árbol binario de búsqueda, en cuyo caso ya con el árbol podemos obtener la secuencia ordenada. La segunda es con dos heaps, la cual, aunque también es O(n lgn) es mucho más rápida que con un árbol binario. Pero en dos casos pagamos O(n) en espacio adicional.
Ahora la trampa: si estamos dispuestos a pagar el consumo en espacio de O(n), entonces es preferible olvidarnos de calcular la mediana y valernos de un heap para ordenar. Hacemos un primer barrido para almacenar todos los elementos en un heap; luego vaciamos el heap y obtenemos la secuencia ordenada. Esta tercera alternativa hace innecesarias las dos anteriores u es mucho más eficiente, pero no olvides que pagas O(n) en espacio. Esta es una versión lista del heapsort.
Espero que hayas entendido las trampas.
Si aceptamos una mediana no tan perfecta, o sea de mediana calidad, entonces podemos seleccionar un buen pivote en O(n), cual es una mejor complejidad que O(n ŋ n)). Para ello decidimos un tamaño de muestra, realizamos un barrido que cuesta O(n) y seleccionamos una muestra al azar durante el barrido. Una vez que tenemos la muestra, escogemos como pivote su mediana, la cual tenderá a ser buena.
El coste esperado del quicksort se puede desglosar del siguiente modo:
| Fase | Coste |
| Selección del pivote | O(n) |
| Partición | O(n) |
| Invocación recursiva | ≈ 2 T(n/2)) |
| Total | O(n lgn) |
A pesar de que la selección del pivote es O(n) el método sigue siendo O(n lgn). Si se optase por el quicksort como método general para ordenar listas, opción que personalmente no recomiendo, entonces es altamente recomendable pagar este O(n) y seleccionar un buen pivote, pues si no nos arriesgamos a tener desempeños cuadráticos. Pero aquí se nos aparece otra consideración: si pagamos este coste O(n) para seleccionar un buen pivote entonces el mergesort deviene competitivo, pues su estructura de ejecución contiene exactamente la misma cantidad de iteraciones: O(n) + 2T(n/2) + O(n) con la notable diferencia de que es un tiempo determinista y no esperado como en el caso del quicksort.
4 Mergesort
Al igual que el quicksort, el mergesort es un método dividir/combinar el cual se estructura del siguiente modo:
template <class Tlist, class Compare> inline
void mergesort(Tlist & list, Compare & cmp)
{
if (list.is_unitarian_or_empty())
return; // una lista vacía o unitaria está ordenada
Tlist l, r;
list.split_list(l, r); // dividir en dos listas l y r respectivamente
mergesort <Tlist, Compare> (l, cmp); // ordenar l
mergesort <Tlist, Compare> (r, cmp); // ordenar r
// en este punto, l y r ya están ordenadas
merge_lists <Tlist, Compare> (l, r, list, cmp); // mezclar l con r
}
Antes de adentrarnos a explicar las partes del método, conviene señalar que esta versión funciona para listas simples y dobles. La condición es que las listas posean los métodos is_unitarian_or_empty() y split_list().
4.1 Partición de listas
La solución cándida consiste en efectuar una primera pasada para contar la cantidad de elementos n. Luego se eliminan los n/2 primeros nodos de la lista y listo. Esta solución es O(n) pero requiere examinar 3/2 n nodos.
Hay dos formas de particionar una lista en dos listas equitativas en tamaño.
4.1.1 Método 1
Supongamos dos corredores p y q arrancan simultáneamente en carrera desde el mismo punto hacia un destino común. Sin embargo, el corredor q se mueve al doble de velocidad que el corredor p. Cuando q llegue al destino p se encontrará en el punto intermedio del trayecto. Este es el principio de partición el cual se instrumenta del siguiente modo:
void split_list(HTList & l, HTList & r)
{
if (is_empty())
return;
if (is_unitarian())
{
swap(l);
return;
}
Slinknc * p = head;
Slinknc * q = head;
while (q != tail and q != NULL)
{
q = NEXT(q); ++count;
if (q == tail or q == NULL)
break;
p = NEXT(p);
q = NEXT(q);
}
l.head = head;
l.tail = p;
r.head = NEXT(p);
r.tail = tail;
head = tail = NULL;
}
Este es el método de Aleph-w porque preserva el orden original de los elementos. Adicionalmente, la versión de Aleph-w cuenta la cantidad de elementos revisados.
4.1.2 Método 2
Si aprehendemos que mientras haya desorden el orden de los elementos no importa para el método, entonces podemos diseñar una partición ligeramente más eficiente:
void split_list(HTList & l, HTList & r)
{
while (not this->empty())
{
l.append(this->remove_first());
if (not this->is_empty())
r.append(this->remove_first());
}
}
4.1.3 Mezcla de listas
Toda la maquinaria necesaria para la mezcla la ofrece la interfaz de HTList:
template <class Tlist, class Compare> inline
void merge_lists(Tlist & l1, Tlist & l2, Tlist & result, Compare & cmp)
{
while (not l1.is_empty() and not l2.is_empty())
if (cmp(l1.get_first(), l2.get_first()))
result.append(l1.remove_first());
else
result.append(l2.remove_first());
if (l1.is_empty())
result.concat_list(l2);
else
result.concat_list(l1);
}
Observa sin embargo que este método también funciona para listas dobles.
5 ¿Cuál utilizar: quicksort o mergesort?
La pregunta se puede reformular en términos de desempeño como: ¿qué es mejor, un probable O(n lgn) del quicksort o un completamente seguro O(n lgn) del mergesort? Yo diría que la respuesta depende de responder ¿cuán probable es el rendimiento esperado del quicksort?.
Si tuviésemos la certeza de que la partición fuese aleatoria, entonces la degradación del quicksort en O(n2) sería muy poco probable. Puesto que es difícil garantizar esta aleatoriedad y que aún en ese caso usar el quicksort como método general conlleva un riesgo, yo transo por el mergesort como método general de ordenamiento de una lista enlazada, pues tengo determinismo y el coste cuadrático que podría acarrear es demasiado alto, especialmente para secuencias de alta escala.
Una lección/recomendación colateral de este post es que el ordenamiento no constituye un pretexto para usar listas enlazadas dobles.
This document was translated from LATEX by HEVEA.
