Ir al contenido



Foto

Reubicar el índice por defecto de una lista ante una eliminación

algoritmo listas indices

  • Por favor identifícate para responder
24 respuestas en este tema

#1 Delphius

Delphius

    Advanced Member

  • Administrador
  • 6.262 mensajes
  • LocationArgentina

Escrito 01 septiembre 2016 - 09:24

Buenas, vengo por una tontera pero mi cabeza si sigue viendolo se va a trabar (más).

Les explico: tengo una clase llamemosle ClaseA que maneja una lista (me ayudo de un TObjectList como atributo privado) de una clase ClaseB.

ClaseB tiene puede ser de dos tipos: B1, y B2.

No hay subclases para manejar estos tipos. El diseño no lo amerita. Se maneja por un atributo simple.

 

Esta lista tiene la particularidad que puede estar llena, vacía, o más comunmente: parcialmente llena. ¿Cómo es eso? Si: ClaseA tiene como atributos y propiedades la cantidad total de items que va a tener, y se establece al momento de crearla.

En cualquier otro momento de su tiempo de vida, puede ir alterando la cantidad y por tanto es de esperarse que no en todo momento tenga todos los items cargados en ella. Es más, lo habitual es que tenga a medias.

 

Es de interés, que cuando se opere con los items, el índice se vaya "actualizando". Por ejemplo, ante una nueva agregación (.Add, no está contemplado ni se espera poder insertar en ciertas posiciones intermedias... por lo que no habrá .Insert()) el índice se cambia para apuntar al último elemento y nuevo elemento agregado. Hay un caso particular: Si la lista se encuentra completamente cargada, este Add() hace que se incremente la cantidad total.

 

De forma analoga pasa cuando uno quiere modificar algún item: existe tanto un Modify() sobrecargado que recibe el índice sobre el cual ubicarse, como también hay un Modify() que lee el actual valor del índice.

Es decir, cualquier "ABM" debe a la par, cambiar el valor del índice.

Los items estarán desordenados, por lo que no necesariamente estarán los de un tipo ubicados primero y luego los otros.

 

Esto lo llevo de buena manera... y aquí es donde se pone peliaguda: la eliminación... sea total, parcial, de un tipo u otro de B.

Tengo un Clear() que recibe como parámetro el tipo de B a eliminar. En esta situación no es problemática. Ya que se espera que el índice o bien apunte a 0, si es que queda al menos un item del otro tipo, o bien en -1 indicando que no hay items.

Con el ClearAll() no hay problema tampoco... indice pasa a -1.

El problema es un Delete(index) o su versión sobrecargada Delete(). Es decir... borrar un solo item.

 

Ustedes se preguntarán, ¿y cual es el problema? Recuerdan que dije que la lista puede que esté parcializada... pues eso me marea.

Internamente tengo dos contadores: uno para B1 y otro para B2. El contador no es más que un record:


delphi
  1. TCounter = record
  2. Total, Parcial: integer;
  3. end;

Tengo también dos funciones:

 

ActualCount, y TotalCount. La primera me dice la cantidad total parcial (y actual) de items: B1.Parcial + B2.Parcial. Y Total, bueno se entiende: total de totales.

 

En mi Delete() debo actualizar este contador parcial, dependiendo del tipo claro. Y ahí es donde ya me hace dudar... ¿Cómo determinar el nuevo indice?

A ver si tiran ideas del posible algoritmo... porque hay que evaluar muchas cosas... si es el último, el primero, el del medio, si la lista ya quedó vacia...

 

Saludos,


  • 0

#2 Agustin Ortu

Agustin Ortu

    Advanced Member

  • Moderadores
  • PipPipPip
  • 831 mensajes
  • LocationArgentina

Escrito 01 septiembre 2016 - 09:53

No es posible usar una lista por cada tipo de b?
  • 0

#3 Delphius

Delphius

    Advanced Member

  • Administrador
  • 6.262 mensajes
  • LocationArgentina

Escrito 01 septiembre 2016 - 10:47

No es posible usar una lista por cada tipo de b?

 

No. Necesito de tenerlos en una misma lista.

 

Para ir ampliando un poco, y quizá ayude a entender el proceso, tengo mi procedimiento DecCounters() que se dispara en Clear()


delphi
  1. procedure TClassA.DecCounters(BType: TBType);
  2. begin
  3. if BType = Bt1;
  4. then begin
  5. if FB1Counter.Parcial > 0
  6. then Dec(FB1Counter.Parcial, 1);
  7.  
  8. end
  9. else begin
  10. if FB2Counter.Parcial > 0
  11. then Dec(FB2Counter.Parcial, 1)
  12. end;
  13. end;


delphi
  1. procedure TClassA.Clear(ABType: TBType);
  2. var i: integer;
  3. begin
  4. for i := FList.Count - 1 downto 0
  5. begin
  6. if TClassB(FList.Items[i]).BType = ABType
  7. then begin
  8. FList.Delete(i);
  9. DecCounters(ABType);
  10. end;
  11. end;
  12. // DONE: ¿No debería ser con ActualCount? ¿O con ambos?
  13. if TotalCount > 0
  14. then begin
  15. if ActualCount >= 1
  16. then FIndex := 0
  17. else FIndex := -1;
  18. end
  19. else FIndex := -1;
  20. end;

Y mi ClearList:


delphi
  1. procedure TClassA.ClearList;
  2. begin
  3. FList.Clear;
  4. FIndex := -1;
  5. FB1Counter.Parcial := 0;
  6. FB2Counter.Parcial := 0;
  7. end;

Y como dije, tengo dos Delete() sobrecargados, uno que recibe el nuevo índice sobre el cual borrar, y otro que borra el actual. Esto tengo actualmente:


delphi
  1. procedure TClassA.Delete(AIndex: integer);
  2. begin
  3. Index := AIndex; // Paso por propiedad. SetIndex() verifica que esté en rango
  4. Delete;
  5. end;


delphi
  1. procedure TClassA.Delete;
  2. var ABType: TBType;
  3. begin
  4. if FIndex >= 0
  5. then begin
  6. ABType := TClassB(FList.Items[FIndex]).BType;
  7. FList.Delete(FIndex);
  8. DecCounters(ABType);
  9. // TODO: actualizar el index dentro de los límites
  10.  
  11. ReallocateIndex;
  12. end;
  13. end;

Dentro de ReallocateIndex() es mi intención hacer el "trabajo duro" de ubicar el índice. Entre el mar de ifs que estaba probando... me hice bolas, y paré al llegar a esto:


delphi
  1. procedure TClassA.ReallocateIndex;
  2. begin
  3. // TODO: mejorar algoritmo!
  4. if TotalCount > 0
  5. then begin
  6. if ActualCount = 0
  7. then FIndex := -1
  8. else begin
  9. if FIndex > (ActualCount - 1)
  10. then FIndex := ActualCount - 2;
  11. else
  12. end;
  13. end
  14. else FIndex := -1;
  15. end;

Necesito una siesta :D No se si me estoy haciendo lio inncesariamente en esa parte o que... Si hay algo que no me gusta mucho, y que evito en lo posible, es llegar a tener muchos IFs encadenados... la complejidad V(G) se dispara ni bien se llega a 3 IFs encadenados... Hay una regla que dice que si V(G) = 7, ¡piensalo dos veces!

 

Afortundamente esto no tiene apuro, ahora me tengo que poner a hacer otros trabajos que tienen más prioridad.

 

Saludos,

PD: Y si... marche siesta. :D


  • 0

#4 giulichajari

giulichajari

    Advanced Member

  • Miembros
  • PipPipPip
  • 433 mensajes

Escrito 01 septiembre 2016 - 02:29

¿Porque no creas otra lista auxiliar e insertas todos los objetos nuevamente? De esta forma obtendras una nueva lista sin saltos en los indices..


  • 0

#5 Delphius

Delphius

    Advanced Member

  • Administrador
  • 6.262 mensajes
  • LocationArgentina

Escrito 01 septiembre 2016 - 03:05

¿Porque no creas otra lista auxiliar e insertas todos los objetos nuevamente? De esta forma obtendras una nueva lista sin saltos en los indices..

 

Lo estaba considerando en mis pre-análisis pero debo descartar esa vía. Esta lista va a ser muy usada, tiene alta demanda de acceso. Y no es que tendré una única lista, como para estar haciendo una "copia en limpio". Serán tantas las operaciones que sería impráctico.

Esta claseA que actúa de lista forma parte (es un atributo) de una clase "mayor". Y de esta clase mayor tendré muchas instancias.

Imaginate que por cada instancia de esta clase "mayor" tengo que tener su lista... estar generando copias en limpio de cada una es un escenario aparatoso.

Debe hacerse el trabajo "localmente".

 

Saludos,


  • 0

#6 giulichajari

giulichajari

    Advanced Member

  • Miembros
  • PipPipPip
  • 433 mensajes

Escrito 01 septiembre 2016 - 03:38

Lo estaba considerando en mis pre-análisis pero debo descartar esa vía. Esta lista va a ser muy usada, tiene alta demanda de acceso. Y no es que tendré una única lista, como para estar haciendo una "copia en limpio". Serán tantas las operaciones que sería impráctico.
Esta claseA que actúa de lista forma parte (es un atributo) de una clase "mayor". Y de esta clase mayor tendré muchas instancias.
Imaginate que por cada instancia de esta clase "mayor" tengo que tener su lista... estar generando copias en limpio de cada una es un escenario aparatoso.
Debe hacerse el trabajo "localmente".

Saludos,

Claro es una especie de composicion digamos que un objeto tiene una lista de otros...Y la documentacion de TObjectList la revisaste? O la de generics.collections? No creo que exista un metodo que compacte los indices.
Saludos

Enviado desde mi SM-G530M mediante Tapatalk
  • 0

#7 Delphius

Delphius

    Advanced Member

  • Administrador
  • 6.262 mensajes
  • LocationArgentina

Escrito 01 septiembre 2016 - 04:35

Claro es una especie de composicion digamos que un objeto tiene una lista de otros...Y la documentacion de TObjectList la revisaste? O la de generics.collections? No creo que exista un metodo que compacte los indices.
Saludos

Enviado desde mi SM-G530M mediante Tapatalk

 

Pues, si es un caso de composición. El diagrama de clase real y completo es más complejo pero salvando ciertas distancias, es algo así:

 

ClaseCliente -1---1--> ClaseA <>-------- ClaseB

 

La clase cliente, mantiene un atributo de tipo ClaseA, que es la lista, formada por items de la clase B.

 

En vista a que existirán muchas clases clientes, pongamos que son N, y cada uno tendrá su listado... siendo M1 la cantidad para el 1ro, M2 para el segundo... y así hasta MN.

Imagínate tener que estar creando otras N listas adicionales.

 

Pero creo que entediste un poco mal sobre el índice. No es que TObjectList cuando libera deja "huecos" y ese índice apunta a nada... TObjectList mantiene bien su lista. Por ejemplo: hagamos de cuenta que la lista fuera de enteros (la clase B es más que eso obviamente, pero servirá) y tengo 10 items, por simplicidad los numeraremos así:

Lista = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Se va a borrar el 5to item, por tanto el índice es 4. Recuerda que en Object Pascal el sistema es 0-based. Quedará:

Lista = {1, 2, 3, 4, 6, 7, 8, 9, 10}

 

Creo que lo que tu estabas entendiendo es que la situación quedaba así:

Lista = {1, 2, 3, 4, x, 6, 7, 8, 9, 10}

Y que el índice no puede referenciar a este lugar.

 

El diseño de la clase motiva que cuando se inserte, o se elimine se actualice el valor del indice para apuntar al nuevo elemento en cuestión. Por ejemplo, si hago un Add() y antes eran 10, ahora tendré 11... el índice debo ponerlo en 10 para que señale al 11vo item. De forma análoga, si quiero proceder a hacer un Delete(9) (es decir el 10mo y último elemento de la lista) ahora el índice debo ubicarlo en el nuevo último (8). Si eliminara el primer elemento (indice = 0), no hay demasiado análisis, siempre será 0 a menos que ya no queden items y pasará a valer -1.

Y si quisiera hacer un Modify(index) me muevo a esa posición y el valor de índice asumirá ese valor.

 

Quizá les parezca un comportamiento extraño, pero las necesidades motivan este trabajo. Cuando se "selecciona" un item (un objeto de tipo clase B convengamos) sobre el cual operar, es habitual que se realicen un par de operaciones sobre y con este item un buen rato, hasta que se decida trabajar con otro item. La clase B es una clase que también tiene sus métodos y operaciones, no es un mero "repositorio de valores".

La clase A, no es solo una lista... delega también algunas cosas a los B.

 

El escenario sería algo así:

- Riggg--- Aló... ¿jefecito? ¿Que necesita que 9 haga eso? Perfecto. Che, vos número 9 vení y hace todo esto. Te voy a tener a full.

*tiempo después*

-Nro9: listo.

...

-¿Hola? Si, señor clase cliente. Ya agrego al chico nuevo...

-Chico nuevo: Hola, soy número 20.

-Entendido.

-Ringgg.... ¿Si señor cliente? Perfecto...

-Nuevecito... ¡Tienes trabajito!

 

Entonces, como puedes ver, hay un buen par de condiciones que evaluar cuando se está procediendo a eliminar objetos. Puedes ver en la muestra de ese código el ReallocateIndex() y como se va adquiriendo complejidad. Y mi cabeza está apagada para evitar una sobrecalentura :D

 

El índice debe estar apuntando al último item con el se ha estado trabajando constantemente.

 

Espero que con esto se me entienda mejor lo que pretendo hacer.

 

Saludos,


  • 0

#8 Agustin Ortu

Agustin Ortu

    Advanced Member

  • Moderadores
  • PipPipPip
  • 831 mensajes
  • LocationArgentina

Escrito 01 septiembre 2016 - 05:37

No se podría evitar eliminar físicamente? De esta forma los índices nunca cambian. Cuando borras mete un null object en esa posición

Por qué necesitas el índice? Una referencia no te sirve?

Editado por Agustin Ortu, 01 septiembre 2016 - 05:38 .

  • 0

#9 Delphius

Delphius

    Advanced Member

  • Administrador
  • 6.262 mensajes
  • LocationArgentina

Escrito 01 septiembre 2016 - 08:14

No se podría evitar eliminar físicamente? De esta forma los índices nunca cambian. Cuando borras mete un null object en esa posición

Por qué necesitas el índice? Una referencia no te sirve?

 

Es una alternativa que no he considerado, pero no la veo posible.

El borrado de todas formas es a nivel "lógico", a pesar de que físicamente se eliminen items. Los datos que son pasados a los objetos cuando son materializados provienen de una base de datos. En ocasiones se tomarán algunos datos, (lista parcial), en otras todos... Luego durante la ejecución es posible que se descarten elementos, es decir, que de la parcial va sacar, pero no se va a realizar un DELETE sobre la base de datos.

Nullear el item es sólo una manera de esconder el problema.

 

Si bien mayormente se necesita mantener referencia al último item en trabajo (lo que motiva una posible propiedad LastItemInUse por darle un nombre que apunte al objeto en cuestión) necesito tener referencia.

Necesito el índice, puesto que si bien los items pueden venir en cualquier orden, se tiene que dejar la posibilidad de que se pueda hacer un Swap entre dos posiciones. El usuario debe tener la libertad de moverlos, intercambiarlos, etc. Por ejemplo, intercambia el 6to por el 2do...

Verás, esta lista es una abstracción de un detalle de movimientos de informes y trabajos que constantemente van cambiando de lugar. Hoy hay 59 items, mañana habrá 61. Pero también he detectado casos durante mi análisis (y ultimamente los veo más seguidos) en los que por error humano, o que, no cambia la cantidad sino que se cambian de lugar los items y debo actuar en consecuencia y que permita modificarse.

En cierta forma, el índice también me facilita las cosas...

 

Es una forma rara de trabajo, pero debo replicarla.

Saludos,


  • 0

#10 Delphius

Delphius

    Advanced Member

  • Administrador
  • 6.262 mensajes
  • LocationArgentina

Escrito 01 septiembre 2016 - 08:34

Fuck... ¡me acado de dar cuenta mientras escribí el post anterior que si tengo que contemplar la posibilidad de un Insert(item, indice)! :o  8o|

En el momento en que el usuario desee hacer una "auditoría" a la lista, debo dejar la posibilidad de que pueda meter items en el medio. Vaya... esto que parecía medio simple, tiene sus cosillas. ¡Joder!

La cosa es así, los items B1 son "procesos" que se pueden llevar de forma automática, mientras que los B2 son dados por órdenes manuales. El sistema es lo suficiente autónomo para detectar cuando debe meter más elementos, de hecho está programado para que de vez en cuando hacer eso. Mayormente y para ciertas actividades el sistema sólo necesitará cargar los B1, e incluso ¡puede que no todos!. Y para otras actividades... va a necesitar tanto B1 como B2.

Una de las funcionalidades previstas para el sistema es la hacer una "auditoría" sobre la lista. ¿En que consiste? Se compara la lista completa (tanto B1 como B2), con la que proviene de una fuente externa. A causa de los cambios externos (que están fuera de mi alcance) sobre esa lista externa es que el usuario considerará hacer las correcciones pertinentes sobre su lista "local".

Como podrán hacerse una idea, esta clase debe brindarme muchas libertades...

 

Saludos,


  • 0

#11 escafandra

escafandra

    Advanced Member

  • Moderadores
  • PipPipPip
  • 3.857 mensajes
  • LocationMadrid - España

Escrito 02 septiembre 2016 - 01:07

Quisiera hacer algunas consideraciones.

1. Una lista como la que usas no es otra cosa que una lista de punteros con lo que reordenarla (pasar a limpio) es muy rápida, no mueves elementos, sólo punteros.
2. Con lo que expones lo que necesitas es llevar el índice del elemento sobre el que estás trabajando.
3. En el caso de un borrado, el índice debes colocarlo sobre el elemento anterior, o siguiente si existen.
4. En el caso de insertar, parece lógico que el índice sea el del nuevo elemento.

5. LastItemInUse no es otra cosa que el índice que quieres llevar en todo momento.

6. Si el usuario quiere intercambiar elementos, lo hará sobre tu índice sobre otro, aquí tendrás que decidir, lo lógico es que el nuevo índice corresponda al elemento que acabas de cambiar de lugar, no el del cambio. Es decir, si cambio el elemento 1 por el 3, ahora el índice es 3 que sigue apuntando al elemento de trabajo.

 

 

Saludos.


  • 0

#12 Agustin Ortu

Agustin Ortu

    Advanced Member

  • Moderadores
  • PipPipPip
  • 831 mensajes
  • LocationArgentina

Escrito 02 septiembre 2016 - 05:58

Se me ocurre una última alternativa "sana", tomando parte de lo que dice escafandra: la lista es rápida para mover y buscar cosas. A menos que tengas muchos objetos.

Mantendría la referencia al último. Si necesitas el índice, se lo pedís a la lista, usando lista.IndexOf

Si te resulta ineficiente, hay vueltas para darle. Los índices no cambian a menos que borres o agregues, y ni siquiera en todos los casos. En los casos que cambia, podés poner tu índice en un valor imposible o usar algún flag; o incluso actualizarlo lanzándole un IndexOf. De ese modo solo lo calculas cuando cambia.

Que sabe el cliente del index? Es como por ejemplo un listview que de cada ítem se sabe su índice? O solo el actual?

Otra cosa, a menos que sea necesario, no veo por qué exponer al cliente un método delete(index), yo prefería exponer delete(objeto), cosa que la lista ya puede resolver (método remove(objeto))
  • 0

#13 Delphius

Delphius

    Advanced Member

  • Administrador
  • 6.262 mensajes
  • LocationArgentina

Escrito 02 septiembre 2016 - 07:38

Quisiera hacer algunas consideraciones.

1. Una lista como la que usas no es otra cosa que una lista de punteros con lo que reordenarla (pasar a limpio) es muy rápida, no mueves elementos, sólo punteros.
2. Con lo que expones lo que necesitas es llevar el índice del elemento sobre el que estás trabajando.
3. En el caso de un borrado, el índice debes colocarlo sobre el elemento anterior, o siguiente si existen.
4. En el caso de insertar, parece lógico que el índice sea el del nuevo elemento.

5. LastItemInUse no es otra cosa que el índice que quieres llevar en todo momento.

6. Si el usuario quiere intercambiar elementos, lo hará sobre tu índice sobre otro, aquí tendrás que decidir, lo lógico es que el nuevo índice corresponda al elemento que acabas de cambiar de lugar, no el del cambio. Es decir, si cambio el elemento 1 por el 3, ahora el índice es 3 que sigue apuntando al elemento de trabajo.

 

 

Saludos.

 

Llevas mucha razón amigo.

En un primer momento pensé en hacerlo por medio de una lista dinámica, empleando punteros. La buena razón de porqué hacerlo es como dices, permite tener mucha más libertades y es un trabajo que se realiza muy rápido.

Luego me dije que es más "aparatoso" de manejarlo en código y de mantener esa clase y me fui por lo "fácil". Ahora me lo estoy replanteando, y quizá hay un argumento de buen peso para ir por esta vía.

En el borrado también lo estaba considerando como que si el item está en el medio, también se podría justificar que el indice quede en el mismo lugar. Es decir, por ejemplo al borrar el 7mo elemento (indice = 6), el índice sigue en la misma posición... son los items "superiores" los que se mueven un lugar abajo. El caso especial es cuando el item a borrar sea el último.

 

Repasando las palabras que estoy escribiendo, y leyéndolos todo hace pensar en una lista dinámica referenciada.

 

Se me ocurre una última alternativa "sana", tomando parte de lo que dice escafandra: la lista es rápida para mover y buscar cosas. A menos que tengas muchos objetos.

Mantendría la referencia al último. Si necesitas el índice, se lo pedís a la lista, usando lista.IndexOf

Si te resulta ineficiente, hay vueltas para darle. Los índices no cambian a menos que borres o agregues, y ni siquiera en todos los casos. En los casos que cambia, podés poner tu índice en un valor imposible o usar algún flag; o incluso actualizarlo lanzándole un IndexOf. De ese modo solo lo calculas cuando cambia.

Que sabe el cliente del index? Es como por ejemplo un listview que de cada ítem se sabe su índice? O solo el actual?

Otra cosa, a menos que sea necesario, no veo por qué exponer al cliente un método delete(index), yo prefería exponer delete(objeto), cosa que la lista ya puede resolver (método remove(objeto))

 

IndexOf es una buena alternativa, en varias ocasiones las uso. Pero acá me dije que podría evitarlo.

Es muy cierto como dices que al cliente no le interesa el índice... Yo lo estaba viendo como un "ayuda memoria" para hacerse una idea de como ubicarse al momento de presentarle la lista visualmente. Internamente los items se manejan pre-ordenados por fechas ascendente y por defecto así se muestran.

Pero claro, cuando hay un Swap() hay que ver estas fechas para ver que mantenga coherencia, la vía directa es modificarles las fechas.

En última es a efectos de presentación la forma en como se cambian los items.

 

Lo que si me acabo de dar cuenta esta mañana es que más que hacer un Insert(item, indice) es un InsertBetween() de entre dos elementos consecutivos. Ya que como dije, al venir pre-ordenados por fechas ascendentes, el caso de pretender insertar implica ubicar un item entre esas dos fechas. Al usuario se le debe pedir una fecha-hora estimada entre ambas.

 

Un cambio de lugar, implica tocar fechas realmente. O más decir, que un Modify() sobre un item que toque la fecha implicará un cambio de lugar.

 

La operación más común es un Add de B1, y la 2da más común es la de modificar y/o operar con el último. Pero como dije, estoy notando que en los últimos días esa lista externa la estan toqueteando de una manera muy desprolija y andan cambiando valores y no necesariamente es el último, estan siendo movimientos de unas fechas anteriores. No quisiera que esa práctica se haga muy común... porque implicaría tener que estar explorando toda vez que se consulte la lista entera, cuando lo habitual es ver si hay algo nuevo, o bien que hayan modificado lo último.

 

A causa de esas anomalías me hace implementar un proceso de auditoría para que de vez en cuando se tenga que comprobar que las cosas estén en orden. Naturalmente esa lista externa es solamente B1, la B2 son los agregados manuales que da el usario.

Afortunadamente me resulta relativamente fácil saber si a esa lista externa la toquetean agregando o borrando. Es cosa de verificar cuantos items tiene y compararlo con los que tengo almacenado. El asunto es cuando toquetean en el medio.

Por momentos me digo que están haciendo esos cambios para joder a mi sistema. :@

 

Es bastante probable que, tenga que ir por una alternativa basada en lista dinámica referenciada como ustedes están sugiriendo. Por ir a la fácil, no siempre es la más viable... me lo recuerdan la próxima vez *-)  :D 

 

Saludos,


  • 0

#14 escafandra

escafandra

    Advanced Member

  • Moderadores
  • PipPipPip
  • 3.857 mensajes
  • LocationMadrid - España

Escrito 02 septiembre 2016 - 07:50

En un primer momento pensé en hacerlo por medio de una lista dinámica, empleando punteros. La buena razón de porqué hacerlo es como dices, permite tener mucha más libertades y es un trabajo que se realiza muy rápido.

Luego me dije que es más "aparatoso" de manejarlo en código y de mantener esa clase y me fui por lo "fácil". Ahora me lo estoy replanteando, y quizá hay un argumento de buen peso para ir por esta vía.

 

En su día escribí una clase Lista de punteros, con lo que me servía para manejar cualquier lista. No es nada complicado y no requiere muchas líneas. Pero te repito, TObjectList, es derivada de TList que no es otra cosa que una clase lista de punteros, muy similar a la que yo escribí, por lo que te puedes ahorrar el trabajo. En mi caso la escribí para aplicaciones que prescindían de la VCL.

 

 

Saludos,


  • 0

#15 Delphius

Delphius

    Advanced Member

  • Administrador
  • 6.262 mensajes
  • LocationArgentina

Escrito 02 septiembre 2016 - 08:10

En su día escribí una clase Lista de punteros, con lo que me servía para manejar cualquier lista. No es nada complicado y no requiere muchas líneas. Pero te repito, TObjectList, es derivada de TList que no es otra cosa que una clase lista de punteros, muy similar a la que yo escribí, por lo que te puedes ahorrar el trabajo. En mi caso la escribí para aplicaciones que prescindían de la VCL.

 

 

Saludos,

 

Si, ya se que TObjectList maneja internamente la lista de punteros.

Nomás me ando preguntando hasta que punto por defecto sus operaciones públicas me facilitan el trabajo y en que partes deberé hacer un trabajo extra para llegar al resultado y sin recurrir a un manejo basado en índices.

 

Saludos,


  • 0

#16 Delphius

Delphius

    Advanced Member

  • Administrador
  • 6.262 mensajes
  • LocationArgentina

Escrito 05 septiembre 2016 - 08:48

Estoy realizando un re-análisis de los casos que estoy detectando.

Y se me hace que puede que tenga que alterar algunas cosas.

 

No descarto que aplique otro enfoque, algo no basado en índices. Lo que si me animo a confirmar es que las manos que meten a esa lista externa, y que debo replicar (más los propios items manuales que ingrese el usuario) podría dar para todo...

Mi nuevo enfoque espera poner orden. Ya que he detectado que por más manos que meten, hay algo que se respeta (o al menos tratan de cuidar): los items van ordenados por fecha ascendente.

Por lo que si cambian la fecha y/o hora a un item del medio, debe ser tal que no sea posterior al siguiente, ni anterior al que lo precede. Aunque de última estoy considerando que si lo hacen, que se "reubique" (tendré que examinar bien puntillosamente en cada lista externa si es que efectivamente detecto esto)

Mi error fue haber interpretado algunos cambios como intercambios de pases. Eran coincidencias debido al resto de la información contenida y eso me hizo sospechar que se alteraron de orden. Esto se debe a que los items tienen información relacionada.

El diseño más completo es así:

 

ClaseCliente -1----1-> ClaseLista <>----- ClaseItem -*-----1- ClaseCategoria

 

La clase diseñada para tener los items es una especie de "wrapper", contiene un atributo que apunta a esta ClaseCategoria. Al momento de crear un item, se le asigna (o mejor dicho, se le asocia) un objeto de ClaseValor. Y al momento de liberar los items simplemente se deshace ese vínculo asignandole nil. La clase items tiene un atributo fecha que es lo que me permite darle la ordenación. ¿Porqué no libero ClaseCategoria? Porque se espera que éstas sean reusables. Es más, el contexto lo dice: están relacionadas a los items. Existe una cantidad ya fijada y conocida (aunque se deja abierta para nuevas categorías, que de hecho el usuario es libre de agregar para dar forma y clasificar sus ingresos manuales)

Como pueden ver del diseño, se espera que exista una especie de relación (m,m) entre una ClaseLista, y ClaseValor. Esa relación intermedia esta dada por los items de la lista.

 

Mi error fue de lectura al momento de examinar las listas externas y había notado una serie de anotaciones repetidas, y al comparar la lista a días posteriores noté ciertos cambios que dieron esa confusión.

 

Mi re-análisis me indica que en realidad, se trabaja con el último item B1 ingresado por defecto. Un cambio en los anteriores no afecta el curso de trabajo (o mejor dicho... no debería... porque ellos ya fueron procesados y usados para trabajar). En cuanto se detecta que la lista externa (que solo contiene B1) tiene nuevos elementos se procede a agregar estos, y por cada uno de los items ingresados realiza ciertos procesos.

Cuando en la lista externa no hay nuevos elementos se toma el último B1 y se procede a reusarlo en su proceso.

Naturalmente, esto no evita que aparezcan cambios en los items B1 anteriores. Y eso es lo que estoy observando ultimamente.

 

Luego el usuario puede meter items manuales en cualquier momento y lugar, los llamado B2. Y estos también deben respetar el criterio de fecha. El sistema "ignora" los B2, estos no son para procesar... sólo son agregados a modo de anotación y ayuda memoria para su agenda diaria que el usuario considera oportuno.

 

Lo que estoy considerando es la forma de trabajar con los items. Como mayormente la lista no estará cargada totalmente, y tendrá contenido parciales (e incluso es más probable que tenga sólo uno, el último B1) estoy considerando que nuevos itemes que se deban agregar o bien que se decida cargar la lista completa (por ejemplo, el usuario quiere ver el detalle complejo de la lista) deberá examinar las fechas item a item para determinar que "posición" le corresponde. Un InsertionSort() para ser el caso.

¿Donde entra el tema de contenido parciales? Pues, justamente, la situación ideal indica que solamente hace falta mantener "activo" el último item B1 y no los anteriores. Es una forma de ganar tanto en memoria como en procesamiento. Cuando se detecta que la lista externa tiene más estos se agregan.

La situación que complica el escenario es cuando se detecta que no hay nuevo item en la lista externa, un cambio en ese item es motivo de sospecha a que se haya modificado también items anteriores a éste. El sistema por defecto no contempla un examen completo...

 

Son muchos los items, como así también son varias las clases clientes. Por cada objeto de esta clase cliente, hay una lista. Y por consiguiente, una liste externa que consultar.

Al no estar cargados va a ser necesario leer desde la base de datos y volcarlos. Esto es lo que motiva la existencia de una "auditoria", y como tal la tengo pensada para que sea llevada manualmente.

 

A esta alturas, a modo paréntesis, quizá ustedes se estén preguntando y porqué no hago que la clase cliente y la clase lista sea una sola. Pues, queridos amigos no es tan simple... la clase cliente hace más cosas... la lista es solo una parte. Justamente delega en ClaseLista el complejo trabajo de lidiar con eso... ClaseCliente tiene otras clases delegadas que hacen otra serie de operaciones. Esas operaciones ya las tengo bien trabajadas... comparado con esto, fue por lejos mucho más llevadero. El grueso del trabajo cae en esta estapa. Es lo que más se usa de todo el sistema.

 

Volviendo al tema:

Esta "re-carga" de items, más el proceso de auditoría me da a entender que el objeto que utilice para administrar mi lista deba tener alguna facilidad para ingresar objetos en orden... un InsertionSort() basado en fechas.

 

Quisiera escuchar sus novedades y percepciones, a ver si en una de esas sus inquietudes y visiones me ayudan a poner más luz a este diseño.

 

Saludos,


  • 0

#17 Agustin Ortu

Agustin Ortu

    Advanced Member

  • Moderadores
  • PipPipPip
  • 831 mensajes
  • LocationArgentina

Escrito 05 septiembre 2016 - 09:00

Si no me falla la memoria en el constructor de TObjectList podés pasar como parámetro un objeto que implementa IComparer, que tiene un solo método que recibe los dos objetos a comparar. Debe devolver uno de tres valores, -1, 0 o 1, como todos los comparadores, indicando menor, igual o mayor, respectivamente

De esta forma la lista se mantiene ordenada sola incluso cuando hay inserciones o bajas. Ojo con el tema de las modificaciones! No hay forma de que detecte que cambiaste el valor del criterio de ordenación de un objeto
  • 0

#18 Delphius

Delphius

    Advanced Member

  • Administrador
  • 6.262 mensajes
  • LocationArgentina

Escrito 05 septiembre 2016 - 09:12

Si no me falla la memoria en el constructor de TObjectList podés pasar como parámetro un objeto que implementa IComparer, que tiene un solo método que recibe los dos objetos a comparar. Debe devolver uno de tres valores, -1, 0 o 1, como todos los comparadores, indicando menor, igual o mayor, respectivamente

De esta forma la lista se mantiene ordenada sola incluso cuando hay inserciones o bajas. Ojo con el tema de las modificaciones! No hay forma de que detecte que cambiaste el valor del criterio de ordenación de un objeto

 

Al menos en Lazarus, y en las versiones anteriores a XE el TObjectList no tiene un constructor que reciba eso.

Lo que tu dices es para un método Sort(), que recibe como parámetro un puntero a un método para efectuar las comparaciones.

 

Pero por defecto, el TObjectList no hace este trabajo de ordenación por inserción.

Tampoco tiene alguna propiedad que diga Sorted, como para entender que haga ese trabajo.

Y tampoco da para estar haciendo Sort() cada dos por tres.

 

Se que existen otros tipos de List, que básicamente son Colas y Pilas, tendré que explorar e investigar si por casualidad existe ya un TSortList o algo así... De última lo puedo implementar.

 

Saludos,


  • 0

#19 Agustin Ortu

Agustin Ortu

    Advanced Member

  • Moderadores
  • PipPipPip
  • 831 mensajes
  • LocationArgentina

Escrito 05 septiembre 2016 - 10:05

Seguramente que en la XE esta, porque en Delphi 2010 yo lo uso :p. Lo mas probable es que lo agregaron en Delphi 2009 cuando metieron todo lo de genericos y metodos anonimos

 

De hecho y para ser justos, yo nunca uso ni he visto un IComparer, sino IComparer<T>

 

--------

 

Por otra parte, yo creo que te estas pre-asustando por el tiempo de ejecucion. Ya conoces la regla: "premature optimization...". Yo te diria que primero lo pruebes y ahi realmente analices si es lento o es "suficiente". Es valido tener un algoritmo "no tan eficiente", sobre todo si mas o menos tenes una idea de la entrada (si podes acotar el valor de N, se que puede llegar cuanto mucho a X). 

 

Si resulta que no es lo suficientemente performante, podrias cambiar la estructura de datos internamente. Podes usar un arbol binario de busqueda por ejemplo; o si necesitas aun mas performance, un AVL (arbol binario de busqueda balanceado). El tema es, que yo sepa no hay nada ya hecho por ahi. El ABB es sencillo de implementar, el AVL es un poco mas dificil

 

Si cambias a arboles, el cliente ni se entera; expones el arbol como lista. Le haces un recorrido preorden y tenes la lista ordenada. O mejor aun podes usar enumeradores. Recien hice las pruebas en FPC y esto me parece mas viable. Se acerca un poco a lo que se programacion generica (que se que no te gusta mucho :)), pero vale la pena porque pasas a tener algoritmos "type-safe" y no tenes que andar pensando en punteros ni realizando casting sobre TObjects

 

El secreto de los enumeradores en Object Pascal esta en un poco de ayuda (magia) del compilador, que te permite escribir bucles for-in. El bucle for-in tiene la siguiente forma


delphi
  1. var
  2. Each: T; // puede ser lo que sea, puede ser primitivo, record, objetos, lo de abajo es todo valido
  3. Each: Integer;
  4. Each: string;
  5. Each: Char;
  6. Each: TAlgunRecord;
  7. Each: IAlgunaInterface;
  8. Each: TAlgunaClase;
  9. begin
  10. for Each in Instancia do
  11. begin
  12. // hacer algo con Each
  13. end;
  14. end;

Ahora obviamente hay que ver que requisitos tiene que cumplir el objeto "Instancia" para que eso funcione

 

El compilador necesita que la clase que contiene aquello que queres recorrer, implemente una funcion (en FPC debe ser publica) llamada GetEnumerator, que debe retornar un objeto, record o interface que debe cumplir el siguiente contrato:

 

- Debe tener una funcion publica MoveNext, que devuelva Boolean; el retorno es True cuando si se puede "avanzar" en la iteracion, False cuando termina

- Debe tener una propiedad publica Current de solo lectura, del tipo de la cosa que vamos a enumerar, implementada con una funcion GetCurrent

 

Con eso podes escribir for-in para cualquier clase. Fijate este ejemplo..


delphi
  1. unit Unit1;
  2.  
  3. {$mode objfpc}{$H+}
  4.  
  5. interface
  6.  
  7. uses
  8. Contnrs, Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls;
  9.  
  10. type
  11.  
  12. { TMedico }
  13.  
  14. TMedico = class
  15. private
  16. FNombre: string;
  17. public
  18. constructor Create(const ANombre: string);
  19. property Nombre: string read FNombre;
  20. end;
  21.  
  22. { TContainerEnumerator }
  23.  
  24. TContainerEnumerator = class
  25. private
  26. FList: TObjectList;
  27. FIndex: Integer;
  28. protected
  29. function GetCurrent: TMedico; inline;
  30. public
  31. constructor Create(AList: TObjectList);
  32. function MoveNext: Boolean; inline;
  33. property Current: TMedico read GetCurrent;
  34. end;
  35.  
  36. { TContainer }
  37.  
  38. TContainer = class
  39. private
  40. FList: TObjectList;
  41. public
  42. constructor Create(const Names: array of string);
  43. function GetEnumerator: TContainerEnumerator;
  44. end;
  45.  
  46. { TForm1 }
  47.  
  48. TForm1 = class(TForm)
  49. Memo1: TMemo;
  50. procedure FormCreate(Sender: TObject);
  51. private
  52. Medicos: TContainer;
  53. public
  54. end;
  55.  
  56. var
  57. Form1: TForm1;
  58.  
  59. implementation
  60.  
  61. {$R *.lfm}
  62.  
  63. { TForm1 }
  64.  
  65. procedure TForm1.FormCreate(Sender: TObject);
  66. var
  67. Each: TMedico;
  68. begin
  69. Memo1.Clear;
  70. Medicos := TContainer.Create(['Agustin', 'Marcelo', 'Eliseo']);
  71. try
  72. // ojo! quien libera al Enumerator? es mucho mas facil resolver esto con record o interfaces
  73. for Each in Medicos do
  74. begin
  75. Memo1.Lines.Add(Each.Nombre);
  76. end;
  77. finally
  78. Medicos.Free;
  79. end;
  80. end;
  81.  
  82. { TContainerEnumerator }
  83.  
  84. constructor TContainerEnumerator.Create(AList: TObjectList);
  85. begin
  86. inherited Create;
  87. FList := AList;
  88. FIndex := -1;
  89. end;
  90.  
  91. function TContainerEnumerator.GetCurrent: TMedico;
  92. begin
  93. Result := FList[FIndex] as TMedico;
  94. end;
  95.  
  96. function TContainerEnumerator.MoveNext: Boolean;
  97. begin
  98. Inc(FIndex);
  99. Result := FIndex < FList.Count;
  100. end;
  101.  
  102. { TMedico }
  103.  
  104. constructor TMedico.Create(const ANombre: string);
  105. begin
  106. inherited Create;
  107. FNombre := ANombre;
  108. end;
  109.  
  110. { TContainer }
  111.  
  112. constructor TContainer.Create(const Names: array of string);
  113. var
  114. I: Integer;
  115. begin
  116. inherited Create;
  117. FList := TObjectList.Create(True);
  118. for I := Low(Names) to High(Names) do
  119. FList.Add(TMedico.Create(Names[I]));
  120. end;
  121.  
  122. function TContainer.GetEnumerator: TContainerEnumerator;
  123. begin
  124. Result := TContainerEnumerator.Create(FList);
  125. end;
  126.  
  127. end.

Todo ese choclo fue para decirte que, si decidis cambiar la estructura interna, si los clientes usan  todos for-in, ni se enteran. Solamente vas a tener que cambiar el enumerador

 

Si aun asi los clientes necesitan la lista, el enumerador igual te sirve, la forma mas facil de construir la lista es usando justamente el enumerador:


delphi
  1. TTuContainer = class
  2. private
  3. FArbol: TArbolBinario;
  4. function GetLista: TList;
  5. public
  6. property Lista: TList read GetLista;
  7. end;
  8.  
  9. function TTuContainer.GetLista: TList;
  10. var
  11. Each: TTuClase;
  12. begin
  13. Result := TList.Create;
  14. for Each in FArbol do
  15. Result.Add(Each);
  16. end;


Editado por Agustin Ortu, 05 septiembre 2016 - 10:05 .

  • 0

#20 Delphius

Delphius

    Advanced Member

  • Administrador
  • 6.262 mensajes
  • LocationArgentina

Escrito 05 septiembre 2016 - 11:40

Mi mente este fin de semana estuvo divagando, como caso extremo, el uso de árboles como tu comentas. Y por ello tomé el libro de Estructuras de Datos que fotocopié hace un par de meses y me puse a revisarlo. No descarto su uso, aunque me la pienso si se vale la pena el esfuerzo llegar a ese punto.

No es cosa de pocos números, seguro, pero tampoco se si la cantidad justifique emplear árboles.

 

Lo que si es fundamental es hacer el trabajo de forma bien cuidadosa, razonablemente rápido, con pocos recursos y en lo posible con intervención mínima de usuarios.

 

No me puse a hacer números... Entre 0 y 1000 hay un buen rango.

Cada clase cliente tiene sus propias listas y la cantidad de items es abierta. No lo decido yo, simplemente mi sistema consume un servicio de terceros y de ahí todo se va dando... Hay casos en los que la lista tiene 10, 20 items... y si bien no he contado... de ojo culero me animo a decir que las hay de las que llegan a sus 100, aunque no descarto que para otros les sea más.

La cantidad de clases clientes, es abierta también. ¡Y creciente! :o

 

Para bajar más el contexto, y para evitar confusiones, cada una representa un trabajo... que traducido a tarea de oficina es un carpetón. Esa caperta pasa por muchas manos, y cada vez que cambia de manos se asienta un movimiento. Cada movimiento, es un proceso más por hacer, y puede que traiga reportes de correcciones y pedidos para el profesional.

Todo se registra y está a disposición Online de los profesionales para que vean como marchan sus trabajos. Ahora es Online, porque antiguamente y hasta no mucho tiempo, cada uno debía acercarse y consultarlo en persona.

 

Justamente acuden a mi, ya es un pedido que lo consideraría generalizado, para que les haga más llevadera su tortura diaria... Lo que comenzó siendo una cosa pequeña para dos tipos locos y algo para salir del paso, ahora es una cosa inmanejable y hay más interesados (¿bien? para mi  :D  )... Algunos profesionales generan 10 carpetas al mes, los hay que quizá llegan a 30 al año, y otros que las apilan y coleccionan hasta llegar a una altura que facilmente llegarían al metro y medio :o ¿Serán 100?. La mayoría estan desorganizados, otros tienen sus mini tablas excel... pero imagínate tener que estar a mano revisando si cada uno de sus trabajos ya ha sido revisado y pasado de manos. Si, que es Online pero para quienes tienen su buena pila...  Y eso lo tienen que hacer mínimo 1 vez cada día... aunque se ve que algunos prefieren acumularlo y hacer una revisión semanal... :| 

 

Hoy no hay novedades, mañana hay una, y pasado mañana te caen 10. Dos días después a otra carpetita te la marcan como rechazada... Y no te enteras de nada a menos que te pongas como b***** a revisar el "sistemita" Online. Y debe ser medianamente rapido, porque la agenda es apretada. Vos vives en Argentina, sabes lo que es lidiar con los organismos públicos y su burocracia. :@  Pasar a buscar carpetitas, responder pedidos, y volver a entregarlas es toda una tortura.

Y bue... aquí estoy, pensando en como traducir esa maraña de pases para que nada se pierda. 8o|

 

No se si el volumen justifica árboles, pero si debe ser eficiente, rápido. Debe trabajar bien con 10, 100, 1000, 5000....

Con los árboles se que se gana mucho... pero quizá sea un cañón cuando necesito una buena escopeta o un rifle... Una pistola evidentemente no me sirve.

 

Saludos,


  • 1





Etiquetado también con una o más de estas palabras: algoritmo, listas, indices