2010-04-06 35 views
5

Mi aplicación hace un uso intensivo de TList, por lo que me preguntaba si hay implementaciones alternativas que sean más rápidas u optimizadas para un caso de uso particular.¿Hay una implementación de TList más rápida?

Sé de RtlVCLOptimize.pas 2.77, que ha optimizado las implementaciones de varios métodos TList.

Pero me gustaría saber si hay algo más. Tampoco necesito que sea un descendiente TList, solo necesito la funcionalidad TList independientemente de cómo se implemente.

Es completamente posible, dada la funcionalidad bastante básica que proporciona TList, que no hay mucho margen de mejora, pero aún quisiera verificarlo, de ahí esta pregunta.

editar: En mi caso de uso particular, no hay listas ordenadas. Hay muchas listas, con diversos elementos. Reemplacé TList con mi propia clase para registrar el número de Agregar/Eliminar llamadas y el recuento de elementos. En ella se informa (toatal para todas las listas):

ListAdd = 15766012; ListRemove = 10630000; ListCount = 5136012 

también pude averiguar lo que el mayor número de elementos en una sola lista es.

No tengo ningún problema en particular, solo me pregunto si hay una manera de hacerlo más rápido, ya que con estos números incluso una pequeña mejora se sumaría.

+1

Cómo muchos artículos, ordenados o no, y ¿cuál es su preocupación en particular? es decir, demasiado lento con más de 10.000 filas? –

+0

¿Utiliza algún otro método que Agregar, Eliminar y Contar? – Harriv

+1

¿De qué versión de Delphi está usted, por cierto? –

Respuesta

8

Uno de los mayores cuellos de botella que conozco sobre TList es la eliminación/extracción en la lista grande. La eliminación del elemento [0] es mucho más lenta que la eliminación del elemento [Cuenta-1] debido al movimiento de la memoria que le sigue.

Para exemple, en una lista que contiene 65.536 elementos:

while list.Count > 0 do List.Delete(0) //Takes 2 mins to complete 

for I := List.Count-1 downto 0 do List.Delete(I) //Takes less than 1 sec 

Así que si usted tiene un TList con millones de elementos, la eliminación de un elemento de índice bajo puede ser costoso en cuanto al rendimiento.Además, considere que tener una lista que no está ordenada hace que sea muy lento encontrar un elemento en ella. IndexOf es muy lento en la lista grande. Es posible que desee considerar mantener ordenada la lista.

Además, teniendo en cuenta que el recuento de elementos puede ser bastante grande, puede considerar utilizar una lista de TList para almacenar sus elementos, lo que ayudará a reducir la sobrecarga de eliminación/extracción que ya mencioné.

1

La estructura de datos más rápida generalmente no es una estructura de datos en absoluto, sino un simulacro que extrae datos solo cuando es necesario, al igual que Virtual Treeview. Tal vez pueda escribir algún tipo de TVirtualList que llame a las funciones apropiadas para recopilar los datos requeridos cuando se soliciten los elementos.

+1

Desde el punto de vista del rendimiento que no puede ser una buena idea: TList lee de un bloque de memoria, llamar a un método de "callback" para compensar los datos a medida que se trabaja con la lista no puede ser más rápido. El segundo problema con esta idea es que generalmente los datos no están "inventados" y dudo que se puedan generar "sobre la marcha". Las GUI de tipo VirtualTree suponen que hay una estructura de datos subyacente que contiene los datos y llaman a un método para obtener los datos según sea necesario. Lo hacen para evitar la duplicación de datos en la memoria (y son más rápidos porque no duplican los datos). –

7

Parece que está haciendo muchas adiciones. No sé cuántas listas se han distribuido, pero si sus listas individuales crecen demasiado, es posible que desee implementar una lista que crezca más rápido.

Eche un vistazo a TList.Grow, que se invoca cuando intenta agregar un elemento a una lista donde todos sus elementos de matriz están en uso, y verá que crece un 25%. Esto es para mantener el uso de memoria a un nivel razonable. Pero si necesita listas realmente grandes, cree su propia clase descendiente y anule la opción Crecer para que en la segunda línea, en lugar de Delta := FCapacity div 4, indique Delta := FCapacity. Esto hace que su lista crezca el doble de grande cada vez, lo que significa menos reallocs y menos copias.

Pero lo que probablemente te está matando es eliminar llamadas. Eliminar tiene que encontrar el elemento antes de que pueda eliminarlo, lo que implica una llamada a IndexOf, que es un escaneo lineal de toda la matriz. Si tienes una lista grande y estás haciendo muchas eliminaciones, eso matará tu rendimiento.

¿Para qué estás utilizando estas listas, especialmente las grandes? Dependiendo de lo que esté haciendo con ellos, puede haber mejores estructuras de datos para el trabajo.

+3

Overriding Grow es una buena sugerencia. Alternativamente, se podría establecer List.Capacity cuando se crea la lista, lo que también ahorraría mucho realloc. –

+0

Sí, es una buena idea también, especialmente si tiene una buena estimación de cuántos elementos terminará en la lista. –

+1

Idea relacionada: puede haber una oportunidad para marcar elementos como eliminados y luego volverlos a usar en lugar de eliminarlos realmente. Solo es útil si no tiene que perder mucho tiempo buscando un elemento "abierto" (marcado eliminado). –

6

¿Está utilizando el procedimiento de la notificación? Si no, haga su propia implementación de TList. Debido al procedimiento Notify, TList.Clear (que se llama al momento de la destrucción) es una operación O (n). El método TList.Clear llama a SetCount, que a su vez llama a Delete para todos los elementos que contiene, por lo que se llamará al procedimiento Notify para cada elemento eliminado. Cuando no necesita sobrescribir el método Notify, puede ajustar el procedimiento SetCount para que no llame a Delete. Esto puede ahorrarle el tiempo de 15.766.012 - 10.630.000 = 5.136.012 Eliminar llamadas.

NB: la ganancia de rendimiento se obtiene nunca será tan grande como la ganancia de rendimiento que se obtiene al clasificar su lista y la optimización de su procedimiento de retiro, según lo sugerido por Mason Wheeler. A menos que la lista que tiene contenga una cantidad muy pequeña de elementos y la función de comparación lleva mucho tiempo.

+0

Buen punto, aunque vale la pena señalar que si se trata de una TObjectList y no solo un TList vainilla, esa notificación tiene que estar allí. Sin embargo, si no, probablemente no haya una buena razón para usar Notify. –

Cuestiones relacionadas