Realloc Vs Linked List Scanning

linked-list

Question

Tengo que leer de un archivo un número desconocido de filas y guardarlas en una estructura (me gustaría evitar un pre-procesamiento para contar la cantidad total de elementos). Después de la fase de lectura, tengo que hacer algunos cálculos sobre cada uno de los elementos de estas filas.

Me di cuenta de dos maneras:

1. Use realloc cada vez que leo una fila. De esta manera, la fase de asignación es lenta, pero la fase de cálculo es más fácil gracias al acceso al índice.

2. Use una lista vinculada cada vez que leo una fila. De esta manera, la fase de asignación es más rápida, pero la fase de cálculo es más lenta.

¿Qué es mejor desde el punto de vista de la complejidad?

Answer 1

¿Con qué frecuencia recorrerá la lista enlazada? Si es solo una vez, vaya a la lista enlazada. Algunas otras cosas: ¿habrá muchas asignaciones pequeñas? Podrías hacer algunos búferes más pequeños para digamos 10 líneas y unir esos togeteher. Pero eso es todo una cuestión de perfilar.

Haría lo más simple primero y vería si eso se ajusta a mis necesidades solo entonces pensaría en optimizar.

A veces uno pierde demasiado tiempo pensando en el óptimo incluso cuando la segunda mejor solución también se adapta perfectamente a las necesidades.

Answer 2

Sin más detalles sobre cómo va a utilizar la información, es un poco difícil comentar la complejidad. Sin embargo, aquí hay algunos pensamientos:

• Si usa realloc, probablemente sería mejor agregar "algunos" elementos más (en lugar de uno cada vez). Típicamente, un buen algoritmo es duplicar el tamaño cada vez.
• Si usa una lista vinculada, puede acelerar el acceso en un simple paso de postproceso. Asigne una matriz de punteros a los elementos y recorra la lista una vez que establezca los elementos de la matriz en cada elemento de la lista.
• Si los artículos tienen un tamaño fijo en el archivo, puede precalcular el tamaño simplemente buscando hasta el final del archivo, determinando el tamaño, dividiendo por el tamaño del artículo y obtendrá el resultado. Incluso si no es un tamaño fijo, posiblemente podría usar esto como un cálculo para "acercarse" al tamaño necesario y reducir el número de reasignaciones requeridas.

Answer 3

como otros usuarios ya han declarado:

La optimización temprana es la raíz de todo mal

Donald Knuth

Tengo una propuesta diferente usando realloc : en C ++ STL, el contenedor std::vector crece cada vez que se inserta un objeto y no hay suficiente espacio disponible. El tamaño del crecimiento depende del tamaño actual preasignado, pero es específico de la implementación. Por ejemplo, puede guardar la cantidad real de objetos preasignados. Si el tamaño se agota, se llama reallocate con la doble cantidad de espacio asignada actualmente. ¡Espero que esto sea algo comprensible!

El caveeat es, por supuesto, que usted asignará probablemente más espacio del que realmente consumirá y necesitará.