Postgrado de Computación de la Universidad de Los Andes
Contents
1 El trabajo
El fin de este trabajo es instrumentar versiones del quicksort de alto desempeño. Para medir objetivamente las bondades de tus instrumentaciones se elaborarán los productos enunciados en las subsecciones siguientes.
Para una evaluación objetiva y en pos del enriquecimiento del curso, es esencial que los productos sean en y para la biblioteca ℵω. En este sentido, debes emplear las siguientes clases:
- Slink
- Dlink
- DynArray<T>
Las evaluación del proyecto se realizará con la versión 1.1-a, la cual se puede descargar del siguiente enlace:
Toma muy seriamente en consideración que la evaluación se hará en función del desempeño de tu programa. En ese sentido, se te recomienda estudies muy bien el quicksort, especialmente sus mejoras: escogencia del pivote, manejo de claves repetidas, minimización del consumo de pila, eliminación de la recursión y uso de otros métodos de ordenamiento para particiones pequeñas.
Eventualmente, puedes considerar aprovechar el paralelismo.
1.1 Quicksort sobre arreglos
1.1.1 Arreglos estáticos
En este caso debes instrumentar la siguiente primitiva:
template <typename T, class Compare> void fquicksort(T a[], size_t n, Compare & cmp); template <typename T, class Compare> void fquicksort(T a[], size_t n, Compare && cmp = Compare);
La cual ordena el arreglo comprendido entre 0 y n-1.
1.1.2 Quicksort sobre arreglos dinámicos
En este caso debes instrumentar las siguientes primitivas:
template <typename T, class Compare> void fquicksort(DynArray<T> & a, Compare & cmp); template <typename T, class Compare> void fquicksort(DynArray<T> & a, Compare && cmp = Compare());
La cual ordena el arreglo dinámicos entre 0 y a.size() -1).
1.2 Quicksort sobre listas
A efectos de lograr versiones generales, el ordenamiento sobre listas se efectúa desde enlaces (simples o dobles) y no desde nodos.
Los datos de los nodos se acceden cuando se requiere comparar. Esto se hace mediante la clase Compare.
1.2.1 Quicksort sobre listas simples
En este caso debes instrumentar las siguientes primitivas:
template <class Compare>
void fquicksort(Slink & list, Compare & cmp);
template <class Compare>
void fquicksort(Slink & list, Compare && cmp = Compare);
La cual ordena la lista simplemente enlazada cuyo nodo cabecera es list.
En este caso, la clase de comparación sigue el siguiente esquema:
class Mi_Compare
{
public:
bool operator () (Slink * link1, Slink * link2);
};
Desde el operador () se acceden los datos de los nodos y se comparan. Examine en la biblioteca el fuente de la clase quicksort(Dlink & list, Compare && cmp) para tener una mejor idea de su utilización.
1.2.2 Quicksort sobre listas dobles
En este caso debes instrumentar las siguientes primitivas:
template <class Compare>
void fquicksort(Dlink & list, Compare & cmp);
template <class Compare>
void fquicksort(Dlink & list, Compare && cmp = Compare);
La cual ordena la lista doblemente enlazada cuyo nodo cabecera es list.
En este caso, la clase de comparación sigue el siguiente esquema:
class Mi_Compare
{
public:
bool operator () (Dlink * link1, Dlink * link2);
};
Desde el operador () se acceden los datos de los nodos y se comparan.
1.3 Conjuntos
Como mencionado en clase, el proceso de partición del quicksort puede usarse para instrumentar el problema fundamental mediante arreglos.
En este caso, debes instrumentar el tipo DynSetDynArray<T><,> el cual representa un conjunto dinámico de elementos de tipo Key, Compare.
Para esta clase debes sustentarte sobre la clase DynArray<T>.
Salvando las partes pertinentes a la estructura de dato, la interfaz de DynSetDynArray<T><d>ebe ser idéntica a al tipo DynSetTree. Estudia los fuentes para que entiendas la interfaz.
2 Evaluación
La Evaluación se hará según la tabla 1.
Problema Velocidad % Memoria % Diseño % Totales % Arreglos 13 3 4 20 Listas dobles 17 3 4 24 Listas simples 20 3 5 28 Conjunto 10 11 7 20 Totales 60 20 20 100
Table 1: Ponderaciones y perspectivas de evaluación
Por cada problema se ejecutarán tres pruebas variando la escala de la entrada logarítmicamente. Los tres tipos de pruebas se dividen en
- Claves únicas
- Claves repetidas
- Permutaciones pseudoordenadas o sesgadas
Cada prueba se repetirá varias veces. En lo que atañe a la velocidad se tomará el mejor tiempo. En cuanto a la memoria, se tomará mayor consumo (el cual es penalizante).
A efectos de que puedas afinar tu proyecto, los archivos de prueba junto con algunas muestras de entrada se repartirán prontamente.
El diseño se efectuará mediante inspección del fuente. En el caso del conjunto, es imperativo que entregues un documento corto que explique las principales decisiones de diseño.
Las evaluaciones sobre velocidad y consumo de memoria son exactamente proporcionales al rendimiento. El trabajo con mayor velocidad de ejecución tendrá 20 ptos y los restantes se calificarán proporcionalmente. El mismo criterio ocurrirá con el mínimo consumo de memoria.
El diseño será evaluado por el profesor.
3 Condiciones
- El proyecto es individual.
- Aunque puedes discutir tus criterios de diseño con tus compañeros, no está permitido intercambiar código fuente.
- La fecha de entrega es el lunes 4 de junio hasta las 11:59 pm. Puedes enviar el trabajo por email a leandro.r.leon@gmail.com con el subject AYDA: proyecto 2. Por favor, no olvides especificar este subject porque si no arriesgas que no se localice el trabajo al momento de la corrección.
- La penalidad por el retardo es de un punto por día hasta un máximo de 7 días. Esto se debe a que no se pueden calificar los proyectos hasta no tener la totalidad de ellos. A partir del lunes 11 de junio no se aceptarán más proyectos.
- Los métodos de ordenamiento y el conjunto deben realizarse sobre y con las clases especificadas de ℵω.
This document was translated from LATEX by HEVEA.
No hay comentarios:
Publicar un comentario
Siéntete libre de dejar comentarios, preguntas, dudas, sugerencias, correcciones y opiniones de cualquier tipo