ce que l'auteur de nedtries entend par « en place »?

Question

I. Juste mis en œuvre une sorte de Trie bitwise (basé sur nedtries), mais mon code ne beaucoup D'allocation de mémoire (pour chaque noeud).  Contrairement à mon Implémentation, nedtries sont réclamés pour être rapide, parmi les choses othet, En raison de leur petit nombre d'allocation de mémoire (le cas échéant). L'auteur réclamer son application à être « en place », mais qu'est-ce que cela signifie vraiment dans ce contexte? Et comment nedtries atteindre un si petit nombre d'allocation dynamique de mémoire?

Ps: Je sais que les sources sont disponibles, mais le code est assez difficile à suivre et je ne peux pas comprendre comment cela fonctionne:

Answer 1

Je pris un coup d'oeil au code source nedtrie.h. Il semble que la raison pour laquelle il est « en place » est que devez ajouter les données de tenue de livres de Trie les éléments que vous souhaitez mémoriser.

Vous utilisez la macro NEDTRIE_ENTRY pour ajouter des liens parent / enfant / suivant / précédent à votre structure de données, et vous pouvez ensuite transmettre cette structure de données aux différentes routines TRIE, qui extraira et utiliser ces éléments ajoutés.

Il est donc « en place » dans le sens que vous augmenter votre structures de données existantes et les codes de greffe sur de Trie que.

Au moins, c'est à quoi il ressemble. Il y a beaucoup de bonté macro dans ce code, donc j'aurais pu me confondre (:

Answer 2

Je suis l'auteur, c'est donc au bénéfice des nombreux selon Google qui éprouvent des difficultés à utiliser de la même nedtries. Je voudrais remercier les gens d'ici sur stackflow pour ne pas faire des commentaires désagréables sur moi personnellement que d'autres discussions sur nedtries font.

1. Je crains que je ne comprends pas les difficultés à savoir comment l'utiliser. L'utilisation est extrêmement simple - il suffit de copier l'exemple dans le fichier Readme.html:

typedef struct foo_s foo_t;
struct foo_s {
  NEDTRIE_ENTRY(foo_t) link;
  size_t key;
};
typedef struct foo_tree_s foo_tree_t;
NEDTRIE_HEAD(foo_tree_s, foo_t);
static foo_tree_t footree;


static size_t fookeyfunct(const foo_t *RESTRICT r)
{
  return r->key;
}

NEDTRIE_GENERATE(static, foo_tree_s, foo_s, link, fookeyfunct, NEDTRIE_NOBBLEZEROS(foo_tree_s));

int main(void)
{
  foo_t a, b, c, *r;
  NEDTRIE_INIT(&footree);
  a.key=2;
  NEDTRIE_INSERT(foo_tree_s, &footree, &a);
  b.key=6;
  NEDTRIE_INSERT(foo_tree_s, &footree, &b);
  r=NEDTRIE_FIND(foo_tree_s, &footree, &b);
  assert(r==&b);
  c.key=5;
  r=NEDTRIE_NFIND(foo_tree_s, &footree, &c);
  assert(r==&b); /* NFIND finds next largest. Invert the key function to invert this */
  NEDTRIE_REMOVE(foo_tree_s, &footree, &a);
  NEDTRIE_FOREACH(r, foo_tree_s, &footree)
  {
    printf("%p, %u\n", r, r->key);
  }
  NEDTRIE_PREV(foo_tree_s, &footree, &a);
  return 0;
}

Vous déclarez votre type d'élément - ici, c'est foo_s struct. Vous avez besoin du NEDTRIE_ENTRY () à l'intérieur, sinon il peut contenir tout ce que vous aimez. Vous devez également une fonction de génération de clé. A part cela, il est assez passe-partout.

Je n'aurais pas choisi ce système de macro basé initialisation moi-même! Mais il est pour la compatibilité avec la rbtree.h BSD si nedtries est très facile d'échanger pour quoi que ce soit en utilisant rbtree.h BSD.

1. En ce qui concerne mon utilisation de "en place" algorithmes, eh bien je suppose que mon manque de spectacles de formation informatique ici. Ce que je qualifierais « en place » est lorsque vous utilisez uniquement la mémoire passé dans un morceau de code, de sorte que si vous la main 64 octets à un en place algorithme, il ne touche que 64 octets à-dire qu'il ne sera pas utiliser métadonnées supplémentaires ou allouer une partie la mémoire, ou encore écrire à état global. Un bon exemple est un la mise en œuvre de tri « en place » où seule la collection étant triée (Et je suppose que la pile de fil) obtient touché.

   Par conséquent, aucune, nedtries n'a pas besoin allocateur de mémoire. Il stocke toutes les les données dont il a besoin dans le NEDTRIE_ENTRY et NEDTRIE_HEAD extensions macro. En d'autres termes, lorsque vous allouez vos foo_s struct, vous faites tout le allocation de mémoire pour nedtries.

2. En ce qui concerne la compréhension de la « macro bonté », il est beaucoup plus facile de comprendre la logique si vous compilez comme C ++ et déboguer :). le utilisations de construction C modèles et de les la débogueur proprement vous montrer l'état n'importe quand. tout en fait, le débogage de ma fin se passe dans un C de la construction et je méticuleusement transcrire les modifications du C en macroised C.

3. Enfin, avant une nouvelle version, je recherche Google pour les personnes ayant problèmes avec mon logiciel pour voir si Je peux réparer les choses et je suis généralement étonné de ce que les gens disent à propos de quelqu'un moi et mon logiciel libre. Premièrement, pourquoi ne pas ces gens ayant difficultés me demandent directement Aidez-moi? Si je sais qu'il ya quelque chose de mal avec les docs, puis Je peux les corriger - également, demander sur stackoverflow ne me laisse pas savoir immédiatement qu'il ya un docs problème bur repose plutôt sur moi trouver la prochaine version. Donc, tout ce que je voudrais disons que si quelqu'un trouve un problème avec mes documents, s'il vous plaît faire Envoyez-moi et dire, même si est un exemple de discussion comme ici sur stackflow.

Niall

Answer 3

En place signifie que vous opérez sur les données d'origine (entrée), de sorte que les données d'entrée deviennent les données de sortie. Non en place signifie que vous avez entrée séparées et des données de sortie et les données d'entrée n'est pas modifiée. En place les opérations ont un certain nombre d'avantages - encombrement réduit cache / mémoire, bande passante mémoire plus faible, donc généralement de meilleures performances, etc., mais ils ont l'inconvénient qu'ils sont destructeurs, à savoir vous perdez l'entrée d'origine les données (qui peuvent être ou pas d'importance, en fonction du cas d'utilisation).

Answer 4

en place des moyens pour opérer sur les données d'entrée et (éventuellement) mettre à jour. L'implication est que la copie non et / déplacer des données d'entrée. Cela peut conduire à perdre les données d'entrée des valeurs d'origine que vous devez considérer si elle est pertinente pour votre cas particulier.