Quelle est l'Efficacité de Mémoire de Liste Doublement chaînée en C?

Question

J'étais tombé sur le terme "Efficacité de Mémoire de Liste Doublement chaînée" lors de la lecture d'un livre sur la C structures de Données. Il a juste eu une ligne en disant que l'efficacité de mémoire de liste doublement chaînée utilise moins de mémoire qu'un normal liste doublement chaînée, mais fait le même travail. Rien de plus a été expliqué, et aucun exemple n'a été donnée. Seulement il a été répondu que cela a été pris à partir d'un journal, et "Sinha" entre Parenthèses.

Après recherche sur Google, le plus proche que je suis venu a cette. Mais, je n'arrivais pas à comprendre quoi que ce soit.

Quelqu'un peut-il m'expliquer quel est l'Efficacité de Mémoire de Liste Doublement chaînée en C? Comment est-il différent d'un autre Liste Doublement chaînée?

EDIT: Ok, j'ai fait une grave erreur. Voir le lien que j'avais posté ci-dessus, a été la deuxième page de l'article. Je n'ai pas vu qu'il y a une première page, et de la pensée, le lien a été donné la première page. La première page de l'article, de fait, donne une explication, mais je ne pense pas que c'est parfait. Il parle seulement des concepts de notions de base de l'Efficacité de Mémoire Liés Liste ou XOR Liste Liée.

Answer 1

Je sais que c'est ma deuxième réponse, mais je pense que l'explication que j'ai à fournir ici peut-être mieux, que la dernière réponse. Mais notez que, même que la réponse est correcte.

---

---

Un Efficace de la Mémoire Liée Liste est plus souvent appelé un XOR Liste Liée , comme cela est totalement dépendant de la XOR Porte Logique et de ses propriétés.

---

Est-ce différent d'une Liste Doublement chaînée?

Oui, il est. Il est en train de faire presque le même travail qu'une Liste Doublement chaînée, mais c'est différent.

Une Liste à double liaison est de stocker des deux pointeurs qui pointent à l'autre et le nœud précédent. En gros, si vous voulez revenir en arrière, vous allez à l'adresse pointée par l' back pointeur. Si vous voulez aller de l'avant, vous allez à l'adresse pointée par l' next pointeur. C'est comme:

Un Efficace de la Mémoire Liée Liste, ou à savoir le XOR Liste chaînée est de n'avoir qu'un seul pointeur au lieu de deux. Il stocke l'adresse précédente (addr (prev)) XOR (^) à l'adresse suivante (addr (suivant)). Lorsque vous souhaitez déplacer vers le nœud suivant, vous faire certains calculs, et de trouver l'adresse du nœud suivant. C'est la même chose pour aller au nœud précédent.C'est comme:

---

Comment ça fonctionne?

Le XOR Liste Liée, comme vous pouvez le faire à partir de son nom, est très dépendante de la porte logique XOR (^) et de ses propriétés.

Ses propriétés sont:

|-------------|------------|------------|
|    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      |
|-------------|------------|------------|

Maintenant, nous allons laisser cela de côté, et de voir ce que chaque nœud stocke:

Le premier nœud, ou de la tête, de magasins, 0 ^ addr (next) comme il n'y a pas de nœud précédent ou de l'adresse. Il ressemble:

Ensuite, le deuxième nœud stocke addr (prev) ^ addr (next). Il ressemble:

L'image ci-dessus montre le nœud B, ou le second nœud. A et C sont de l'adresse de la troisième et le premier nœud. Tous le nœud, à l'exception de la tête et de la queue, sont comme ci-dessus, on.

La queue de la liste, n'a pas de nœud suivant, de sorte qu'il stocke addr (prev) ^ 0. Il ressemble:

Avant de voir comment nous nous déplaçons, nous allons voir la représentation d'un XOR Liste Liée de nouveau:

Quand vous voyez

il signifie clairement il y a un lien de terrain, à l'aide duquel vous déplacer vers l'arrière et l'avant.

Aussi, à noter que lors de l'utilisation d'un XOR Liste Liée, vous devez avoir une variable temporaire (pas dans le nœud), qui stocke l'adresse du noeud qui vous étiez avant. Lorsque vous vous déplacez vers le nœud suivant, vous jetez l'ancienne valeur, et de stocker l'adresse du nœud étaient dans les premiers.

Le déplacement de la Tête vers le nœud suivant

Disons que vous êtes maintenant sur le premier nœud, ou au niveau du nœud A. Maintenant, vous avez envie d'aller au nœud B. C'est la formule pour le faire:

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

Donc, ce serait:

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

Comme c'est la tête, l'adresse précédente, serait tout simplement 0, donc:

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

On peut supprimer les parenthèses:

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

À l'aide de l' none (2) de la propriété, nous pouvons dire qu' 0 ^ 0 sera toujours 0:

addr (next) = 0 ^ addr (next)

À l'aide de l' none (1) de la propriété, nous pouvons simplifier ainsi:

addr (next) = addr (next)

Vous avez obtenu l'adresse de la prochaine noeud!

Le déplacement d'un nœud au nœud suivant

Maintenant, nous allons dire que nous sommes dans un milieu nœud, ce qui a un précédent et suivant nœud.

Nous allons appliquer la formule:

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

Maintenant, remplacez les valeurs:

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

Supprimer Les Parenthèses:

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

À l'aide de l' none (2) de la propriété, nous pouvons simplifier:

addr (next) = 0 ^ addr (next)

À l'aide de l' none (1) de la propriété, nous pouvons simplifier:

addr (next) = addr (next)

Et vous l'obtenez!

Le déplacement d'un nœud du nœud que vous étaient dans les premiers

Si vous n'êtes pas à comprendre le titre, il signifie que si vous étiez au nœud X, et ont maintenant déplacé vers le nœud Y, vous voulez aller vers le nœud visité plus tôt, ou fondamentalement nœud X.

Ce n'est pas une tâche fastidieuse. Rappelez-vous que j'ai mentionné ci-dessus, que vous stockez l'adresse que vous avez été dans une variable temporaire. Donc l'adresse du noeud que vous voulez visiter, est couché dans une variable:

addr (prev) = temp_addr

Le déplacement d'un nœud au nœud précédent

Ce n'est pas le même que celui mentionné ci-dessus. Je veux dire que, vous avez au nœud Z, vous êtes maintenant au niveau du nœud Y, et que vous voulez aller vers le nœud X.

C'est presque la même que le déplacement d'un nœud au nœud suivant. Juste que c'est c'est vice-versa. Lorsque vous écrivez un programme, vous utilisez les mêmes étapes que je l'avais mentionné dans le déplacement d'un nœud au nœud suivant, c'est juste que vous êtes de trouver le plus tôt élément dans la liste que de trouver l'élément suivant.

Je ne pense pas que j'ai besoin de l'expliquer.

---

Avantages de la XOR Liste Liée

• Il utilise moins de mémoire que d'une Liste Doublement chaînée. Environ 33% de moins.

• Il utilise un seul pointeur. Cela simplifie la structure du nœud.

• Comme doynax dit, une sous-section d'un XOR peut être inversé en temps constant.

---

Les inconvénients de XOR Liste Liée

• C'est un peu délicat à mettre en œuvre. Il a plus de chances d'échec et de débogage, il est assez difficile.

• Toutes les conversions (dans le cas d'un int) ont lieu à / à partir de uintptr_t

• Vous ne pouvez pas simplement acquérir l'adresse d'un nœud, et le début de la traversée (ou autre) à partir de là. Vous devez toujours commencer par la tête ou la queue.

• Vous ne pouvez pas aller sauter, sauter ou d'autres nœuds. Vous devez aller un par un.

• Le déplacement nécessite plusieurs opérations.

• Il est difficile de déboguer un programme qui est à l'aide d'un XOR Liste Liée. Il est beaucoup plus facile à déboguer une Liste Doublement chaînée.

---

Références

• http://www.ritambhara.in/memory-efficient-doubly-linked-list/comment-page-1/

• https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/

Answer 2

C'est une vieille astuce de programmation qui vous permet d'économiser de la mémoire. Je ne pense pas que c'est utilisé beaucoup plus, puisque la mémoire n'est plus que serré une ressource que c'était dans les vieux jours.

L'idée de base est: "Dans un classique à double liaison de la liste, vous avez deux pointeurs à des éléments d'une liste, d'un "à côté" pointeur qui pointe sur l'élément suivant, et un "prev" pointeur qui pointe vers l'élément précédent. Vous pouvez donc parcourir la liste vers l'avant ou l'arrière en utilisant l'une des pointeurs.

La réduction de la mémoire mise en œuvre, vous remplacez le "next" et "prev" avec une seule valeur, qui est le bit à bit OU exclusif (au niveau du bit-XOR) de "next" et "prev". Par conséquent, vous pouvez réduire l'espace de stockage de l'élément adjacent pointeurs de moitié.

En utilisant cette technique, il est encore possible de parcourir la liste dans les deux sens, mais vous avez besoin de savoir l'adresse de la précédente (ou suivante) de l'élément pour le faire. Par exemple, si vous traversez la liste dans le sens de la marche, et vous avez l'adresse de "prev", alors vous pouvez obtenir "suivant" en prenant la bit-à-bit-XOR de "prev" avec le combiné actuel du pointeur de la valeur, qui est "prev" XOR "suivant". Le résultat est "prev" XOR "prev" XOR "suivant", ce qui est juste "à côté". La même chose peut être fait dans la direction opposée.

L'inconvénient est que vous ne pouvez pas faire des choses comme la suppression d'un élément, un pointeur vers l'élément, sans connaître l'adresse du "précédent" ou "suivant" élément, puisque vous n'avez pas de contexte permettant de décoder le combiné de la valeur du pointeur.

L'autre inconvénient, c'est que ce genre de pointeur truc contourne les données normales type de mécanisme de vérification qu'un compilateur peut s'attendre.

C'est une astuce, mais en toute honnêteté, je vois très peu de raison de l'utiliser de nos jours.

Answer 3

Je recommande de voir que ma deuxième réponse à cette question, car il est beaucoup plus claire. Mais je ne dis pas que cette réponse est fausse. C'est également correcte.

---

---

Un Efficace de la Mémoire Liée Liste est aussi appelé un XOR LISTE Liée.

Comment Ça Marche

Un XOR (^) Lié Liste est une Liste de liens dans lequel au lieu de stocker l' next et back des pointeurs, nous venons d'utiliser un pointeur pour faire le travail à la fois de l' next et back des pointeurs. Nous allons tout d'abord voir le XOR logique portes propriétés:

|-------------|------------|------------|
|    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      |
|-------------|------------|------------|

Permet maintenant de prendre un exemple. Nous avons une liste doublement chaînée avec quatre nœuds: A, B, C, D. Voici à quoi il ressemble:

Si vous le voyez, chaque nœud dispose de deux pointeurs, et 1 variable pour stocker des données. Nous sommes donc à l'aide de trois variables.

Maintenant, si vous êtes avez une Liste Doublement chaînée avec beaucoup de nœuds, de la mémoire, il sera à l'aide de sera trop. Trop de la rendre plus efficace, nous utilisons une Efficacité de Mémoire de Liste Doublement chaînée.

Une Efficacité de Mémoire de Liste Doublement chaînée est une Liste Liée dans lequel nous utilisons juste le pointeur de la déplacer à l'aide de XOR et ses propriétés.

Voici une représentation picturale:

Comment déplacer d'avant en arrière?

Vous avez une variable temporaire (un seul, pas dans le nœud). Disons que vous êtes traversant le nœud de gauche à droite. Si vous commencez au niveau du nœud A. Dans le pointeur d'Un nœud, vous pouvez stocker le nœud B de l'adresse. Ensuite, vous déplacez vers le nœud B. Tout en se déplaçant vers le nœud B, dans la variable temporaire, vous stockez Un nœud d'adresse.

Le lien (pointeur) de la variable de nœud B a l'adresse de l' A ^ C. Vous prendriez le nœud précédent adresse (qui est Une) et XOR avec le lien actuel de terrain , vous donnant l'adresse de C. Logiquement, cela devrait ressembler à:

A ^ (A ^ C)

Intéressons nous maintenant à simplifier l'équation. On peut supprimer les parenthèses et le réécrire en raison de l'associativité comme:

A ^ A ^ C

Nous pouvons simplifier cette à

0 ^ C

en raison de la seconde ("Aucun (2)", comme indiqué dans le tableau) propriété.

En raison de la première ("None (1)", comme indiqué dans le tableau), de la propriété, ce qui est essentiellement

C

Si vous ne pouvez pas comprendre tout cela, il suffit simplement de voir la troisième propriété ("None (3)", comme indiqué dans le tableau).

Maintenant, vous avez obtenu l'adresse de nœud C. Ce sera le même processus pour revenir à la charge.

Disons que vous alliez à partir du nœud C à nœud B. Vous permettrait de stocker l'adresse de nœud C dans la variable temporaire, effectuez la procédure donnée ci-dessus.

REMARQUE: Tout comme A, B, C sont des adresses. Grâce à bath-shéba pour me dire de le rendre clair.

Les inconvénients de XOR Liste Liée

• Comme Lundin cités, toutes les conversions ont à faire à partir de/à l' uintptr_t.

• Comme Sami Kuhmonen mentionné, vous devez commencer par bien définir le point de départ, pas seulement un nœud aléatoire.

• Vous ne pouvez pas simplement sauter d'un nœud. Vous devez aller dans l'ordre.

Notez également qu'un XOR Lié Liste n'est pas mieux qu'un doublement liste liée dans la plupart des cas.

Références

• https://en.wikipedia.org/wiki/XOR_linked_list
• https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/
• http://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-1/

Answer 4

OK, donc, vous avez vu le XOR liste liée, ce qui vous permet d'économiser un pointeur par article... mais c'est d'un laid, laid structure de données, et loin d'être le meilleur que vous pouvez faire.

Si vous êtes inquiet au sujet de la mémoire, il est presque toujours préférable d'utiliser une double liaison, avec plus de 1 élément par nœud, comme une liste chaînée de tableaux.

Par exemple, alors qu'un XOR liste liée frais 1 pointeur par article, en plus de l'élément lui-même, Une liste à double liaison avec 16 points par nœud coûts à 3 points pour chacune des 16 éléments, ou 3/16 pointeurs par article. (l'extra pointeur est le coût de l'entier qui enregistre le nombre d'éléments dans le nœud) est inférieur à 1.

En plus de la mémoire de l'épargne, vous bénéficiez d'avantages dans la localité, car tous les 16 points dans le noeud sont à côté les uns des autres dans la mémoire. Des algorithmes de parcourir la liste sera plus rapide.

Note qu'un XOR liste liée exige également de vous allouer ou libérer de la mémoire chaque fois que vous ajoutez ou supprimer un nœud, et qui est une opération coûteuse. Le tableau liste liée, vous pouvez faire mieux que cela en permettant aux nœuds à moins de complètement plein. Si vous permettez à 5 item vide fentes, par exemple, alors vous ne devez allouer ou libérer de la mémoire sur chaque 3ème d'insertion ou de suppression au pire.

Il existe de nombreuses stratégies possibles pour déterminer quand et comment allouer ou libérer des nœuds.

Answer 5

Vous avez déjà une jolie explication élaborée de XOR liste liée, je vais partager quelques idées sur l'optimisation de la mémoire.

1. Les pointeurs normalement de 8 octets, 64 bits machines. Il est nécessaire d'aborder n'importe quel point dans la RAM au-delà de 4 GO adressables avec 32 bits de pointeurs.

2. Les gestionnaires de mémoire traitent généralement les blocs de taille fixe, pas d'octets. E. g. C malloc alloue d'habitude dans les 16 octets de granularité.

Ces deux éléments impliquent que, si vos données est de 1 octet, correspondant de la liste doublement chaînée élément prendra de 32 octets (8+8+1, arrondi à 16 multiples). Avec XOR astuce vous pouvez obtenir jusqu'à 16.

Cependant, pour optimiser encore plus loin, vous pouvez envisager d'utiliser votre propre gestionnaire de mémoire, que: (a) traite avec des blocs à faible granuarity, tels que 1 octet ou peut-être même aller en morceaux, (b) a des limites plus strictes sur la taille globale. Par exemple, si vous savez que votre liste sera toujours s'adapter à l'intérieur d'un bloc continu de 100 MO, vous avez seulement besoin de 27 bits de l'adresse de n'importe quel octet dans le bloc. Pas 32 ou 64 bits.

Si vous n'êtes pas à l'élaboration d'une liste générique de la classe, mais vous connaissez les habitudes d'utilisation de votre application, dans de nombreux cas, la mise en œuvre de tels gestionnaire de mémoire peut être un travail facile. Par exemple, si vous savez que vous ne serez jamais allouer plus de 1000 éléments, et chaque élément prend 5 octets, vous pouvez mettre en mémoire le gestionnaire de 5000 octets tableau avec une variable qui contient l'index de la première octet, et que vous allouer un élément supplémentaire, il vous suffit de prendre que l'index et le déplacer vers l'avant par la taille allouée. Dans ce cas, votre pointeurs ne seront pas de vrais pointeurs (comme int*), mais sera juste l'index à l'intérieur de 5000-tableau d'octets.