para nodo listas lista lenguaje fuente enlazadas enlazada eliminar ejercicios doblemente completo codigo c data-structures memory-efficient xor-linkedlist mem.-efficient-linkedlist

nodo - listas doblemente enlazadas c#



¿Qué es una lista doblemente vinculada a la memoria eficiente en C? (5)

De acuerdo, entonces has visto la lista vinculada de XOR, que te ahorra un puntero por artículo ... pero esa es una estructura de datos fea y fea, y está lejos de ser lo mejor que puedes hacer.

Si le preocupa la memoria, casi siempre es mejor usar una lista doblemente vinculada con más de 1 elemento por nodo, como una lista de matrices enlazada.

Por ejemplo, mientras que una lista vinculada XOR cuesta 1 puntero por artículo, más el artículo en sí, una lista doblemente vinculada con 16 elementos por nodo cuesta 3 punteros por cada 16 elementos, o 3/16 punteros por artículo. (el puntero adicional es el costo del entero que registra cuántos elementos hay en el nodo) Eso es menos que 1.

Además del ahorro de memoria, obtienes ventajas en la localidad porque los 16 elementos en el nodo están uno al lado del otro en la memoria. Los algoritmos que iteran a través de la lista serán más rápidos.

Tenga en cuenta que una lista vinculada a XOR también requiere que asigne o libere memoria cada vez que agregue o elimine un nodo, y esa es una operación costosa. Con la lista enlazada a una matriz, puede hacerlo mejor permitiendo que los nodos estén completamente llenos. Si permite 5 ranuras de elementos vacíos, por ejemplo, solo tendrá memoria asignada o libre en cada 3ª inserción o eliminará en el peor.

Existen muchas estrategias posibles para determinar cómo y cuándo asignar o liberar nodos.

Me encontré con el término "Lista doblemente vinculada a la memoria eficiente" mientras leía un libro sobre las estructuras de C Data. Simplemente tenía una línea que decía que una lista doblemente unida con memoria eficiente usa menos memoria que una lista doblemente enlazada normal, pero hace el mismo trabajo. No se explicó nada más, y no se dio ningún ejemplo. Solo se dio que esto ha sido tomado de un diario, y "Sinha" en Corchetes.

Después de buscar en Google, lo más cerca que encontré fue this . Pero, no pude entender nada.

¿Puede alguien explicarme qué es una Lista doblemente vinculante para la memoria eficiente en C? ¿En qué se diferencia de una lista normal doblemente enlazada?

EDITAR: Bien, cometí un grave error. Ver el enlace que publiqué arriba, era la segunda página del artículo. No vi que había una primera página, y pensé que el enlace era la primera página. La primera página del artículo en realidad da una explicación, pero no creo que sea perfecta. Solo habla de los conceptos básicos de Lista enlazada eficiente en memoria o Lista enlazada XOR.

Este es un viejo truco de programación que le permite guardar memoria. No creo que se use mucho más, ya que la memoria ya no es un recurso tan estricto como lo era en los viejos tiempos.

La idea básica es esta: en una lista convencional doblemente vinculada, tiene dos punteros a elementos de lista adyacentes, un puntero "siguiente" que apunta al siguiente elemento y un puntero "anterior" que apunta al elemento anterior. Por lo tanto, puede recorrer la lista hacia adelante o hacia atrás utilizando los punteros apropiados.

En la implementación de memoria reducida, reemplaza "next" y "prev" con un valor único, que es el O exclusivo en modo bit (XOR bit a bit) de "next" y "prev". Por lo tanto, reduce el almacenamiento para los punteros de elementos adyacentes a la mitad.

Usando esta técnica, aún es posible recorrer la lista en cualquier dirección, pero necesita conocer la dirección del elemento anterior (o siguiente) para hacerlo. Por ejemplo, si está atravesando la lista en la dirección de avance, y tiene la dirección de "prev", entonces puede obtener "next" tomando el bit-XOR de "prev" con el valor de puntero combinado actual, que es "prev" XOR "siguiente". El resultado es "prev" XOR "prev" XOR "siguiente", que es solo "siguiente". Lo mismo se puede hacer en la dirección opuesta.

Lo malo es que no puedes hacer cosas como eliminar un elemento, dar un puntero a ese elemento, sin conocer la dirección del elemento "anterior" o "siguiente", ya que no tienes contexto para decodificar el puntero combinado valor.

El otro inconveniente es que este tipo de truco de puntero evita el mecanismo normal de comprobación de tipos de datos que un compilador puede esperar.

Es un truco ingenioso, pero honestamente, veo muy pocas razones para usarlo en estos días.

Recomendaría ver mi segunda respuesta a esta pregunta, ya que es mucho más clara. Pero no estoy diciendo que esta respuesta sea incorrecta. Esto también es correcto

Una lista enlazada eficiente en memoria también se denomina lista enlazada XOR .

Como funciona

Una lista vinculada XOR (^) es una lista de enlaces en la que, en lugar de almacenar los punteros next y back , solo usamos un puntero para hacer el trabajo de los punteros next y back . Veamos primero las propiedades de puertas lógicas de XOR:

|-------------|------------|------------| | Name | Formula | Result | |-------------|------------|------------| | Commutative | A ^ B | B ^ A | |-------------|------------|------------| | Associative | A ^ (B ^ C)| (A ^ B) ^ C| |-------------|------------|------------| | None (1) | A ^ 0 | A | |-------------|------------|------------| | None (2) | A ^ A | 0 | |-------------|------------|------------| | None (3) | (A ^ B) ^ A| B | |-------------|------------|------------|

Tomemos ahora un ejemplo. Tenemos una lista doblemente vinculada con cuatro nodos: A, B, C, D. Así es como se ve:

Si ve, cada nodo tiene dos punteros y 1 variable para almacenar datos. Entonces estamos usando tres variables.

Ahora bien, si tiene una Lista doblemente enlazada con muchos nodos, la memoria que utilizará será demasiado. Demasiado para que sea más eficiente, utilizamos una lista doblemente vinculante de memoria eficiente .

Una Lista Doblemente Vinculada con la Memoria Eficiente es una Lista Vinculada en la que usamos solo un puntero para movernos hacia adelante y hacia atrás usando XOR y sus propiedades.

Aquí hay una representación pictórica:

¿Cómo te mueves hacia adelante y hacia atrás?

Usted tiene una variable temporal (solo una, no en el nodo). Digamos que estás atravesando el nodo de izquierda a derecha. Entonces comienza en el nodo A. En el puntero del nodo A, almacena la dirección del nodo B. Luego se mueve al nodo B. Mientras se mueve al nodo B, en la variable temporal, almacena la dirección del nodo A.

La variable de enlace (puntero) del nodo B tiene la dirección de A ^ C Tomaría la dirección del nodo anterior (que es A) y XOR con el campo de enlace actual, dándole la dirección de C. Lógicamente, esto se vería así:

A ^ (A ^ C)

Simplifiquemos ahora la ecuación. Podemos eliminar los paréntesis y reescribirlos debido a la propiedad Asociativa como:

A ^ A ^ C

Podemos simplificar aún más esto a

0 ^ C

debido a la segunda propiedad ("Ninguno (2)" como se indica en la tabla).

Debido a la primera propiedad ("Ninguno (1)" como se indica en la tabla), esto es básicamente

C

Si no puede entender todo esto, simplemente vea la tercera propiedad ("Ninguno (3)" como se indica en la tabla).

Ahora, tienes la dirección del nodo C. Este será el mismo proceso para volver.

Digamos que ibas desde el nodo C al nodo B. Guardarías la dirección del nodo C en la variable temporal, haz el proceso indicado arriba nuevamente.

NOTA: Todo como A , B , C son direcciones. Gracias a Bathsheba por decirme que lo deje en claro.

Desventajas de la lista enlazada de XOR

  • Como mencionó Lundin, todas las conversiones deben hacerse desde / a uintptr_t .

  • Como mencionó Sami Kuhmonen, debes comenzar desde un punto de inicio bien definido, no solo un nodo aleatorio.

  • No puedes simplemente saltar un nodo. Tienes que ir en orden.

También tenga en cuenta que una lista vinculada XOR no es mejor que una lista doblemente enlazada en la mayoría de los casos.

Referencias

Sé que esta es mi segunda respuesta, pero creo que la explicación que proporciono aquí podría ser mejor que la última respuesta. Pero tenga en cuenta que incluso esa respuesta es correcta.

Una lista enlazada eficiente en memoria se denomina con frecuencia lista enlazada XOR, ya que depende totalmente de XOR Logic Gate y sus propiedades.

¿Es diferente de una lista doblemente enlazada?

Sí , lo es. En realidad, está haciendo casi el mismo trabajo que una Lista doblemente enlazada, pero es diferente.

Una Lista doblemente enlazada almacena dos punteros, que apuntan al nodo siguiente y al nodo anterior. Básicamente, si quiere regresar, vaya a la dirección que señala el puntero back . Si desea avanzar, vaya a la dirección señalada por el next puntero. Es como:

Una Lista Vinculada de Memoria Eficiente , o sea, la Lista Vinculada XOR está teniendo solo un puntero en lugar de dos. Esto almacena la dirección anterior (addr (prev)) XOR (^) la siguiente dirección (addr (siguiente)). Cuando desee pasar al siguiente nodo, realice ciertos cálculos y busque la dirección del siguiente nodo. Esto es lo mismo para ir al nodo anterior. Es como:

¿Como funciona?

La lista enlazada de XOR , como puede ver desde su nombre, depende en gran medida de la puerta lógica XOR (^) y sus propiedades.

Sus propiedades son:

|-------------|------------|------------| | Name | Formula | Result | |-------------|------------|------------| | Commutative | A ^ B | B ^ A | |-------------|------------|------------| | Associative | A ^ (B ^ C)| (A ^ B) ^ C| |-------------|------------|------------| | None (1) | A ^ 0 | A | |-------------|------------|------------| | None (2) | A ^ A | 0 | |-------------|------------|------------| | None (3) | (A ^ B) ^ A| B | |-------------|------------|------------|

Ahora vamos a dejar esto de lado, y veamos qué almacena cada nodo:

El primer nodo, o el encabezado , almacena 0 ^ addr (next) ya que no hay ningún nodo o dirección anterior. Parece que:

Entonces el segundo nodo almacena addr (prev) ^ addr (next) . Parece que:

La imagen de arriba muestra el nodo B o el segundo nodo. A y C son direcciones del tercer y primer nodo. Todo el nodo, excepto la cabeza y la cola, son como el anterior.

La cola de la lista no tiene ningún nodo siguiente, por lo que almacena addr (prev) ^ 0 . Parece que:

Antes de ver cómo nos movemos, veamos nuevamente la representación de una lista vinculada XOR:

Cuando veas

claramente significa que hay un campo de enlace, con el que retrocede y avanza.

Además, tenga en cuenta que al utilizar una lista vinculada XOR, necesita tener una variable temporal (no en el nodo), que almacena la dirección del nodo en el que estaba antes. Cuando se mueve al siguiente nodo, descarta el valor anterior y almacena la dirección del nodo en el que estaba antes.

Pasar de la cabeza al siguiente nodo

Digamos que ahora estás en el primer nodo o en el nodo A. Ahora quieres moverte al nodo B. Esta es la fórmula para hacerlo:

Address of Next Node = Address of Previous Node ^ pointer in the current Node

Entonces esto sería:

addr (next) = addr (prev) ^ (0 ^ addr (next))

Como esta es la cabeza, la dirección anterior simplemente sería 0, entonces:

addr (next) = 0 ^ (0 ^ addr (next))

Podemos eliminar los paréntesis:

addr (next) = 0 ^ 0 addr (next)

Usando la propiedad none (2) , podemos decir que 0 ^ 0 siempre será 0:

addr (next) = 0 ^ addr (next)

Usando la propiedad none (1) , podemos simplificarlo a:

addr (next) = addr (next)

¡Tienes la dirección del siguiente nodo!

Pasar de un nodo al siguiente nodo

Ahora digamos que estamos en un nodo intermedio, que tiene un nodo anterior y siguiente.

Vamos a aplicar la fórmula:

Address of Next Node = Address of Previous Node ^ pointer in the current Node

Ahora sustituya los valores:

addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))

Eliminar paréntesis:

addr (next) = addr (prev) ^ addr (prev) ^ addr (next)

Usando la propiedad none (2) , podemos simplificar:

addr (next) = 0 ^ addr (next)

Al usar la propiedad none (1) , podemos simplificar:

addr (next) = addr (next)

¡Y lo entiendes!

Pasar de un nodo al nodo en el que estuvo antes

Si no comprende el título, básicamente significa que si estuvo en el nodo X y ahora se movió al nodo Y, quiere volver al nodo visitado anteriormente, o básicamente al nodo X.

Esta no es una tarea engorrosa. Recuerde que he mencionado anteriormente, que almacena la dirección en la que estaba en una variable temporal. Entonces, la dirección del nodo que desea visitar se encuentra en una variable:

addr (prev) = temp_addr

Pasar de un nodo al nodo anterior

Esto no es lo mismo que se mencionó anteriormente. Quiero decir que estabas en el nodo Z, ahora estás en el nodo Y y quieres ir al nodo X.

Esto es casi lo mismo que pasar de un nodo al siguiente nodo. Solo que esto es es viceversa. Cuando escribe un programa, utilizará los mismos pasos que mencioné al pasar de un nodo al siguiente nodo, solo que está buscando el elemento anterior en la lista que encontrar el siguiente elemento.

No creo que deba explicar esto.

Ventajas de la lista enlazada de XOR

  • Esto usa menos memoria que una Lista doblemente enlazada . Aproximadamente 33% menos.

  • Utiliza solo un puntero. Esto simplifica la estructura del nodo.

  • Como dijo doynax, una subsección de un XOR se puede revertir en tiempo constante.

Desventajas de la lista enlazada de XOR

  • Esto es un poco complicado de implementar. Tiene mayores posibilidades de falla, y la depuración es bastante difícil.

  • Todas las conversiones (en el caso de una int) deben tener lugar a / from uintptr_t

  • No puede simplemente adquirir la dirección de un nodo y comenzar a atravesar (o lo que sea) desde allí. Siempre debes comenzar desde la cabeza o la cola.

  • No puedes ir a saltar, ni saltar nodos. Tienes que ir uno por uno.

  • Moverse requiere más operaciones.

  • Es difícil depurar un programa que está utilizando una lista vinculada XOR. Es mucho más fácil depurar una Lista doblemente enlazada.

Referencias

Ya tienes una explicación bastante elaborada de la lista vinculada XOR, voy a compartir algunas ideas más sobre la optimización de la memoria.

  1. Los punteros normalmente toman 8 bytes en máquinas de 64 bits. Es necesario abordar cualquier punto en la RAM más allá de 4 GB direccionable con punteros de 32 bits.

  2. Los administradores de memoria suelen tratar bloques de tamaño fijo, no bytes. Por ejemplo, C malloc generalmente asigna una granularidad de 16 bytes.

Estas dos cosas implican que si sus datos son de 1 byte, el elemento correspondiente de la lista doblemente enlazada tomará 32 bytes (8 + 8 + 1, redondeados al múltiplo 16 más cercano). Con el truco XOR puedes bajarlo a 16.

Sin embargo, para optimizar aún más, puede considerar usar su propio administrador de memoria, que: (a) se ocupa de bloques en granulos menores, como 1 byte o tal vez incluso en bits, (b) tiene un límite más estricto en el tamaño total. Por ejemplo, si sabe que su lista siempre cabe dentro de un bloque continuo de 100 MB, solo necesita 27 bits para direccionar cualquier byte dentro de ese bloque. No 32 o 64 bits.

Si no está desarrollando una clase de lista genérica, pero conoce patrones de uso específicos para su aplicación, en muchos casos implementar dicho administrador de memoria puede ser una tarea fácil. Por ejemplo, si sabe que nunca asignará más de 1000 elementos y cada elemento ocupa 5 bytes, puede implementar el administrador de memoria como una matriz de 5000 bytes con una variable que contiene el índice del primer byte libre, y cuando asigna elementos adicionales, simplemente tome ese índice y muévalo hacia adelante según el tamaño asignado. En este caso, sus punteros no serán punteros reales (como int *), sino que serán solo índices dentro de esa matriz de 5000 bytes.