Realloc Vs Linked List Scanning

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 en 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í están algunas ideas:

• Si utiliza realloc, probablemente sería mejor realloc añadir "algo" más elementos (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 post-procesamiento. 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 elementos tienen un tamaño fijo en el archivo, puede precalcular el tamaño simplemente buscando hasta el final del archivo, determinando el tamaño, divida por el tamaño del elemento 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

que otros usuarios ya han declarado:

optimización prematura es la raíz de todo mal

Donald Knuth

Tengo una propuesta diferente utilizando realloc: en el 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, llame al 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á.