Se busca: Listas muy rápidamente Linked In C

Question

Estoy tratando de implementar una lista enlazada en C. Una aplicación común que se ve flotando alrededor de la Internet es algo así como

typedef struct { 
    int head; 
    Node *tail; 
} Node; 

con métodos como

Node cons(int head, Node tail) { 
    Node y; 
    y.head = head; 
    y.tail = malloc(sizeof(Node)); 
    *y.tail = tail; 
} 

El rendimiento es muy importante. ¿Hay alguna forma de implementar una lista enlazada en C que sea más rápida que esto? Por ejemplo, deshacerse de la asignación de memoria (y.tail = malloc(sizeof(Node))) debería proporcionar un aumento de velocidad significativo.

Answer 1

Sí, no ... Esto se conoce como grupo de memoria. Similar a un grupo de hilos. Básicamente se asigna un área de memoria al comienzo del programa de tipo Nodo. Los punteros a esta área se almacenan en una matriz. En su función de cons, todo lo que hace es obtener los punteros de la matriz. Esto no mejora la velocidad general, pero si tiene asignaciones frecuentes de memoria, esto aumentará la capacidad de respuesta del programa a costa de un espacio para el arreglo

Answer 2

¿Se agrega rápidamente a una lista vinculada? Un rope (no limitado a cadenas con pequeñas modificaciones) le permitiría asignar memoria por lotes (mejorando el rendimiento) sin penalizar la adición al final de la lista.

Answer 3

Si le preocupa la fragmentación de malloc, puede solicitar un gran múltiplo número de Nodo de tamaño y seguir incrementando un puntero por tamaño de (Nodo) cada vez que copia valores de Nodo.

Answer 4

¿Qué operación debe ser rápida: inserción, recuperación, todo? Siempre hay una compensación. ¿Su solución debe ser escalable? La lista enlazada no es

En caso de que desee/necesite adherirse a una lista vinculada, podría almacenarla en una matriz de estructuras con un campo que indique el índice de la siguiente entrada en la lista vinculada. La inserción será muy rápida, sin ninguna asignación, la desventaja es que debe saber la cantidad de elementos por adelantado o reasignar la tabla cuando esté completa.

Consulte la "Listas vinculadas usando matrices de nodos" subsección de the Wikipedia page on linked list.

Answer 5

Yo sugeriría que utilice la implementación de la lista Linux kernel:

http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;f=include/linux/list.h

(sin asignación de memoria adicional)

Answer 6

preocupaciones de memoria a un lado, algunas reflexiones sobre la elaboración de listas de enlace único más rápido.

Creo que hay un poco de confusión en su código. En él es el núcleo mismo de una lista enlazada es:

typdef struct _node { 
    ... 
    struct _node *next; 
} NODE; 

mayoría de las implementaciones tendrían un void * allí para colgar la carga útil en. Eso no es particularmente importante por ahora.

Las inserciones en la lista deben conectar los punteros. Para simplemente agregar el nodo (e ignorar el agregado de la carga útil) hay 1 asignación si el nodo va a la cabeza o la cola de una lista, y 2 si está yendo en el medio. No hay mucho que se pueda hacer para evitar eso.

Ocasionalmente, las listas simples solo usan estructuras de nodo, por lo que la inserción de cola requiere un recorrido transversal. Esto es costoso Tener una estructura de cabeza especial con conocimiento del primer y último nodo elimina ese costo.

Los recorridos se pueden hacer más rápido al implementar esto como una lista de omisiones (http://en.wikipedia.org/wiki/Skip_list). Aunque se debe tener cuidado durante la inserción del nodo para optimizar (y obtendrá más asignaciones del puntero durante la inserción).

Answer 7

Comprobar la velocidad de esta aplicación lista enlazada, así:

http://web.archive.org/web/20071103112712/http://stsdas.stsci.edu/bps/linked_list.html

Answer 8

Si las únicas operaciones que necesita está empujando, haciendo estallar y la iteración a continuación, en lugar de lista enlazada se puede poner elementos en una matriz. El elemento de empujar y hacer estallar solo es para modificar un número (índice del primer o último elemento). El frente y la parte posterior de la matriz se pueden conectar cíclicamente para que los elementos se puedan insertar libremente sin un problema de que la matriz finalice.