Foros Club Delphi

Foros Club Delphi (https://www.clubdelphi.com/foros/index.php)
-   Varios (https://www.clubdelphi.com/foros/forumdisplay.php?f=11)
-   -   Metodos de Ordenamiento. QuickSort vs Burbuja Mejorado (https://www.clubdelphi.com/foros/showthread.php?t=22926)

Delphius 01-07-2005 06:39:11

Metodos de Ordenamiento. QuickSort vs Burbuja Mejorado
 
1 Archivos Adjunto(s)
Hola foristas, de nuevo yo... ahora no con dudas sino con un debate que yo he sostenido conmigo mismo (yo me entiendo:D ).
Hace un tiempo dejé un hilo con una duda sobre el rendimiento del TStringList. La duda ya fue resuelta, pero ahora me he puesto a pensar en los métodos de ordenamiento.
Recuerden aquellas clases de estructuras de datos y algoritmos...
La pregunta ¿Cuál es el mejor? siempre va y viene... aunque muchos digan: QuickSort. A mi entender para determinar cual es el mejor se tiene que tener en cuenta:
1. Los tiempos de ejecución
2. Estabilidad: el desempeño en el mejor, peor y promedio.
3. El tamaño de la lista, arreglo o lo que se desee ordenar.
4. Frecuencia e Importancia de uso. Por ejemplo, ¿Para qué usar QickSort en un sistema X si esta funcionalidad sólo se va ha usar escasamente?
5. Memoria
6. Comparaciones
7. Intercambios
8. Que se desea ordenar (esto puede ser obviado)

En el hilo anterior (Rendimiento TStringList) Lepe me recomendó que haga uso del QickSort y me quedé pensando en si debo usarlo o no. Por un lado tiene razón, pero por otro lado tal vez no valga la pena. Y se me ocurrió abrir este hilo para que a manera de debate (más que como duda) opinen al respecto... Se que mucho para discutir no hay.

Bueno, la cosa es que lo que se pretende es ordenar una playlist (se puede ordenar por: Artista, Tema, Duración, Género, Directorio, Album en forma Ascendente y Descendente) y yo actualmente hago empleo del método de Burbuja Mejorado.
Para responderme a mi mismo seguí los puntos anteriores. Para hacer un examen más sencillo hice el supuesto de que ningún factor es más importante que otro; todos tienen igual importancia en el análisis, por tanto poseen igual ponderación o peso sobre la decisión.
1. Tiempos de Ejecución:
Las pruebas demuestran que QucikSort es más rápido, obvio. PUNTAJE: QuickSort 1 - Burbuja Mejorado 0.
2. Estabilidad:
2.1 Mejor Caso: QickSort O(n * log n), Burbuja: O(n^2) (en burbuja no me acuerdo bien si es asi)
2.2 Peor Caso: QickSort O(n^2), Burbuja: O(n^2)
2.2 Promedio: QickSort O(n * log n), Burbuja: O(n/2^2)
Entonces en cuanto a Estabilidad podemos decir que el Burbuja es mucho mas estable ya que la diferencia entre el mejor y el peso caso no es demasiada. PUNTAJE: 1 - 1

3. Tamaño:
No hay mucho que decir, pero basta con decir que el QickSort es más conveniente a medida que se aumenta el tamaño. PUNTAJE: 2 - 1
4. Frecuencia/Importancia de Uso:
Para lo que está pensado (ordenar Playlist) cabe decir que no es muy frecuente. Generalmente un usuario ya deja la lista ordenada según sus gustos, y rara vez la ordenará de nuevo con otro criterio. Por tanto, para que malgastar QuickSort por algo que rara vez se usará, PUNTAJE: 2 - 2, esto está parejo...
5. Memoria:
Al ser QickSort un algoritmo recursivo, necesita un manejo de memoria que depende de la arquitectura del computador y esto hace que consuma más memoria que el Burbuja. PUNTAJE: 2 - 3.
6. Comparaciones:
Si bien las comparaciones (para decir si es major o menor: ascendente o descendente) son proporcionales al tamaño, QickSort demuestra que debe realizar menos comparaciones que el burbuja. PUNTAJE: 3 - 3.
7. Intercambios:
QuickSort tiene un punto debil, cuanto más grande sea la distribución de los elementos (es decir cuanto mas mezclados estén) mayor intercambios debe hacer. Si bien el burbuja también sufre de ello, el crecimiento de dichos intercambios es más notable en QickSort. PUNTAJE: 3 - 4

Entonces he llegado a que PARA EL USO EN MI SISTEMA me conviene hacer uso del Burbuja Mejorado. ¿Que opinan ustedes?¿Pondrían otros factores a tener en cuenta, o usarían otra ponderación para hacer estos "cálculos"?¿O pondrían en el "partido" otros algoritmos?

PD: No es por hacer spam pero para el que lo desea, aquí les dejo la versión 1.21 de la unidad UPlayList:) . Se han hecho algunos cambios menores.

rafita 01-07-2005 12:02:33

Buenas compañero,
la verdad es que no soy la persona más adecuada para responderte, pero tu hilo me ha recordado a "algoritmos + estructuras de datos = programas" que es uno de los mejores libros de informática que he leido, y me he puesto melancolico recordando aquellos tiempos...

Teniendo en cuenta que la lista de canciones no se ordenará con mucha frecuencia, y que las máquinas de hoy en día son potentísimas, yo no me complicaría la vida y utilizaría el método de ordenación que más cómodo me resultase de implementar.

Sé que es una posición demasiado cómoda, pero con 20 en el tema de la programación he escrito demasiadas líneas de código que jamás han llegado a utilizarse (o aplicaciones que me han costado 20 veces más trabajo que el que quitaban).

Motivos personales aparte (y perdona mis lloros de abuelo chocho), el método de la Burbuja Mejorado siempre me ha gustado, y según tus divagaciones es el que te interesa.

PD. Sigue complicandote la vida en hacer un código óptimo... llegarás lejos y ESTARÁS SATISFECHO CONTIGO MISMO.

Saludos.

Lepe 01-07-2005 14:37:47

Como aludido, y sin corroborar todos los datos propuestos :D :D propongo detectar cuantos temas hay en la lista, si es menor que X usar burbuja mejorado, si es mayor usar QuickSort.

Ea, debate acabado :D

Un saludo.

Casimiro Notevi 01-07-2005 15:42:41

También podías usar un dbgrid enlazado a una tabla en memoria, sería rapidísimo y podrías ordenar cómodamente por cualquier campo. Aunque tendrías que modificar "un poco" tu programa :confused:

unreal4u 01-07-2005 23:15:15

o no me acuerdo bien, o a mi parecer entre burbuja mejorada y shell, el más rápido y el que gasta menos en memoria es shell. No es tan rápido como Quicksort, pero si me acuerdo que era BASTANTE más rápido que burbuja mejorada. Me acuerdo que cuando di el curso de algoritmos, hice un programa DOS, usando gráficos a 1024*768, donde cada "gráfica" era un pixel que iba desde 0-255, donde se ordenaban los elementos por los dintintos métodos de ordenamiento (burbuja, burbuja mejorada, shell y unos cuantos más, a burbuja le tomo MUCHÍSIMO TIEMPO). El claro vencedor fue shell, quicksort lamentablemente no lo implementé en ese programa, por falta de tiempo.

Para mi opinión, en estos días, el usuario quiere algo instantáneo siempre, y hay que ponerse en todos los casos: pueden haber 2 canciones, como también pueden haber 200.540.160 canciones, por lo tanto, aunque se gaste un poco más de memoria en un método de ordenamiento rápido, yo creo que ese sería el más óptimo. Como estaba dicho en un post anterior, puedes hacer que si el número de canciones es una determinada cantidad, implementar uno u otro método de ordenamiento. Sería lo más óptimo, ya que no todos los métodos son necesariamente los más rápidos con pocos o muchos datos. (MySQL es más rápido que Oracle con pocos datos, por ejemplo, pero lentísimo cuando hay hartos datos, y Oracle es cada vez más rápido mientras más datos tenga). No sería mala idea pedirles una ayudadita a los de oracle jajajaja ...

mamcx 02-07-2005 03:31:51

Todo depende de que es lo que quieras....

Pero a menos que necesites moler muchos datos, no me quebraria la cabeza (bueno de hecho me la estoy quebrando con MUTIS mutis.sourceforge.net)

Mira si tienes la clase TBucketList en tu version de Delphi que es una lista tipo Hash.

Tambien date una mirada a http://dennishomepage.gugs-cats.dk/FastCodeProject.htm y sobre todo a los reemplazos al administrador de memoria... (no tiene una respuesta directa PERO las mejoras a las funciones expuestas pueden mejorar el resultado de los algoritmos en general).

Por otro lado, si quieres la manera mas rapida de mostrar listas/arboles no busques mas alla de este control:

http://www.delphi-gems.com/VirtualTreeview/VT.php

Segun lo que dicen (y no es en broma) puede insertar 1 millon de nodos en 700 ms y en 0.5 se camina todo el millon de nodos....

Es un poco mas complicado porque hay que enlazar con Pointers y el hecho que sea virtual implica que el estilo es diferente, pero luego de guerrearle un par de horas veras que va muy bien.

Delphius 02-07-2005 06:17:02

gracias....
 
Muchas gracias a los que respondieron.
Aprovecharé estas mini vacaciones que tengo para evaluar sus propuestas.
Cita:

Empezado por rafita
PD. Sigue complicandote la vida en hacer un código óptimo... llegarás lejos y ESTARÁS SATISFECHO CONTIGO MISMO.

Gracias, pero tampoco es mi intención complicarme la vida... sino que es algo propio de mi: trato en lo posible de mejorar mis códigos hasta que no pueda encontrar algo mejor.
Se que mi unidad es muy factible de mejoras... todavía está en beta:rolleyes: :rolleyes:

Lepe 02-07-2005 11:58:43

Cita:

Empezado por mamcx
Por otro lado, si quieres la manera mas rapida de mostrar listas/arboles no busques mas alla de este control:

http://www.delphi-gems.com/VirtualTreeview/VT.php

Segun lo que dicen (y no es en broma) puede insertar 1 millon de nodos en 700 ms y en 0.5 se camina todo el millon de nodos....

Es un poco mas complicado porque hay que enlazar con Pointers y el hecho que sea virtual implica que el estilo es diferente, pero luego de guerrearle un par de horas veras que va muy bien.

- Trabajo con el VirtualTreeView, y doy fé de lo rápido y versatil que es, No echas en falta ninguna propiedad, método o evento.
- Enlazar con pointers[...] . Hay rutinas para evitar el uso de punteros, en mi código no escribo un solo operador ^., unicamente en la definición de tipos.
- Implica más trabajo, Si, ya que tienes que especificar por código que se va a pintar en cada columna; no se puede hacer en tiempo de diseño (al menos todavía). Además reune todas las características de un Treeview y DBGrid convencional juntos.

Un saludo

sakuragi 21-07-2005 17:57:59

hola que tal

no tienen un manual o guia como usar el "Virtual Treeview"

de hante mano gracias

rastafarey 22-07-2005 03:37:50

Resp
 
El mas rapido qu e existe es quicksort.

Y cual es el peo de la memoria.

Ahorita las maquinas posees mucha memoria eso era cuando se program solo con la memoria base.

Ahorita lo que se uqiere es velocidad cosas optimas y seguras.

Para que ua recursion en quicksort se desborde la pila tienes que ser una cantidad de datos descomunalmente grande.

Osea es esta epoca casi imposible.

Es mas primero te da problema el sistema operativo ante que la recusion se coma la heat.


La franja horaria es GMT +2. Ahora son las 12:55:20.

Powered by vBulletin® Version 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Traducción al castellano por el equipo de moderadores del Club Delphi