Club Delphi  
    FTP   CCD     Enlaces   Buscar   Trucos   Trabajo   Foros

Retroceder   Foros Club Delphi > Principal > Varios
Registrarse FAQ Miembros Calendario Guía de estilo Buscar Temas de Hoy Marcar Foros Como Leídos

Respuesta
 
Herramientas Desplegado
  #1  
Antiguo 01-07-2005
Avatar de Delphius
[Delphius] Delphius is offline
Miembro Premium
 
Registrado: jul 2004
Ubicación: Salta, Argentina
Posts: 5.303
Delphius Va camino a la fama
Post Metodos de Ordenamiento. QuickSort vs Burbuja Mejorado

Hola foristas, de nuevo yo... ahora no con dudas sino con un debate que yo he sostenido conmigo mismo (yo me entiendo ).
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.
Archivos Adjuntos
Tipo de Archivo: zip UPlayList_1_21.zip (7,3 KB, 426 visitas)
__________________
Delphius
[Guia de estilo][Buscar]
Responder Con Cita
  #2  
Antiguo 01-07-2005
rafita rafita is offline
Miembro
 
Registrado: ago 2003
Ubicación: Cuenca- España.
Posts: 309
rafita Va por buen camino
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.
__________________
Rafita.
Responder Con Cita
  #3  
Antiguo 01-07-2005
Avatar de Lepe
[Lepe] Lepe is offline
Miembro Premium
 
Registrado: may 2003
Posts: 7.330
Lepe cantidad desconocida en este momento
Como aludido, y sin corroborar todos los datos propuestos propongo detectar cuantos temas hay en la lista, si es menor que X usar burbuja mejorado, si es mayor usar QuickSort.

Ea, debate acabado

Un saludo.
__________________
Si usted entendió mi comentario, contácteme y gustosamente,
se lo volveré a explicar hasta que no lo entienda, Gracias.
Responder Con Cita
  #4  
Antiguo 01-07-2005
Avatar de Casimiro Notevi
Casimiro Notevi Casimiro Notevi is online now
Moderador
 
Registrado: sep 2004
Ubicación: Planeta Agua
Posts: 22.211
Casimiro Notevi Va camino a la fama
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
__________________
/* Saludos
*/
La otra guía de estilo | Búsquedas avanzadas | Etiquetas para código

$ sudo mv system > /dev/null

Responder Con Cita
  #5  
Antiguo 01-07-2005
Avatar de unreal4u
unreal4u unreal4u is offline
Miembro
 
Registrado: nov 2004
Ubicación: Temuco, Chile
Posts: 105
unreal4u Va por buen camino
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 ...
__________________
Código Delphi [-]
procedure Gracias; 
begin
 if Respuesta_a_Mensaje = TRUE then showmessage('Ojalá que te sirva')
 else showmessage('Gracias por responder... :-)');
end; // (c) unreal4u
Responder Con Cita
  #6  
Antiguo 02-07-2005
Avatar de mamcx
mamcx mamcx is offline
Moderador
 
Registrado: sep 2004
Ubicación: Medellín - Colombia
Posts: 2.665
mamcx Va por buen camino
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.
__________________
Nuevo Blog.
Ahora en Twitter!.
Responder Con Cita
  #7  
Antiguo 02-07-2005
Avatar de Delphius
[Delphius] Delphius is offline
Miembro Premium
 
Registrado: jul 2004
Ubicación: Salta, Argentina
Posts: 5.303
Delphius Va camino a la fama
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
__________________
Delphius
[Guia de estilo][Buscar]
Responder Con Cita
  #8  
Antiguo 02-07-2005
Avatar de Lepe
[Lepe] Lepe is offline
Miembro Premium
 
Registrado: may 2003
Posts: 7.330
Lepe cantidad desconocida en este momento
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
__________________
Si usted entendió mi comentario, contácteme y gustosamente,
se lo volveré a explicar hasta que no lo entienda, Gracias.
Responder Con Cita
  #9  
Antiguo 21-07-2005
Avatar de sakuragi
sakuragi sakuragi is offline
Miembro
 
Registrado: feb 2004
Ubicación: root
Posts: 1.435
sakuragi Va por buen camino
hola que tal

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

de hante mano gracias
__________________
OpenSuse OpenOffice.org icomputo
Responder Con Cita
  #10  
Antiguo 22-07-2005
Avatar de rastafarey
rastafarey rastafarey is offline
Miembro
 
Registrado: nov 2003
Posts: 888
rastafarey Va por buen camino
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.
__________________
Todos los dias sale un pendejo a la calle y el que se lo encuentra es del.
Responder Con Cita
Respuesta


Herramientas
Desplegado

Normas de Publicación
no Puedes crear nuevos temas
no Puedes responder a temas
no Puedes adjuntar archivos
no Puedes editar tus mensajes

El código vB está habilitado
Las caritas están habilitado
Código [IMG] está habilitado
Código HTML está deshabilitado
Saltar a Foro


La franja horaria es GMT +2. Ahora son las 15:44:52.


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