ciò che l'autore di nedtries mezzi da “in-place”?

Question

I. appena implementato una sorta di bit a bit trie (sulla base di nedtries), ma il mio codice fa molto Di allocazione di memoria (per ciascun nodo). Contrariamente al mio Implementazione, nedtries sono rivendicati per essere veloce, tra le cose othet, A causa del loro piccolo numero di allocazione di memoria (se presente). L'autore reclama la sua implementazione di essere "in-place", ma che cosa realmente significa in questo contesto? E come fa nedtries raggiungere un piccolo numero di allocazione dinamica della memoria, quali?

Ps: mi sa che le fonti sono disponibili, ma il codice è piuttosto difficile da seguire e non posso figura come funziona

Answer 1

Ho preso uno sguardo al codice sorgente nedtrie.h. Sembra che il motivo è "in-place" è che devono aggiungere i dati trie di contabilità per gli elementi che si desidera memorizzare.

È possibile utilizzare la macro NEDTRIE_ENTRY aggiungere padre / figlio / successivo / i collegamenti prev alla struttura dei dati, e si può quindi passare tale struttura di dati per le varie routine trie, che estrarre e utilizzare quei membri aggiunti.

Quindi è "in-place", nel senso che si aumentano il vostro strutture di dati esistenti e le PiggyBack codice trie su questo.

Almeno questo è quello che sembra. C'è un sacco di macro bontà che il codice così ho potuto ottenere me confuso (:

Answer 2

Sono l'autore, quindi questo è per il bene dei molti Secondo Google che stanno simile avendo difficoltà nell'uso nedtries. Vorrei ringraziare le persone qui in stackflow per non fare commenti spiacevoli su di me personalmente, che alcune altre discussioni su nedtries fanno.

1. Temo che non capisco le difficoltà di sapere come usarlo. L'uso è estremamente semplice - è sufficiente copiare l'esempio nel file 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;
}

È dichiarare il tipo di voce - qui è foo_s struct. È necessario il NEDTRIE_ENTRY () al suo interno altrimenti può contenere quello che vuoi. È inoltre necessario un funzione generatrice chiave. Oltre a questo, è piuttosto boilerplate.

non avrei scelto questo sistema di macro basato inizializzazione me stesso! Ma è per la compatibilità con la rbtree.h BSD in modo nedtries è molto facile scambiare per qualcosa utilizzando BSD rbtree.h.

1. Per quanto riguarda il mio utilizzo di "in luogo" algoritmi, beh credo che la mia mancanza di spettacoli di formazione informatica Qui. Quello che chiamerei "a posto" è quando si utilizza solo la memoria passato in un pezzo di codice, quindi se che la mano 64 byte a un posto algoritmo toccherà solo 64 byte cioè esso non farà uso di metadati in più, o destinare un po ' memoria aggiuntiva, o addirittura in scrittura a stato globale. Un esempio è un buon "In atto" l'attuazione sorta dove solo la raccolta da ordinare (E suppongo che la pila filo) viene toccato.

   Quindi un no, nedtries non ha bisogno allocatore di memoria. Memorizza tutte le i dati di cui ha bisogno nel NEDTRIE_ENTRY e NEDTRIE_HEAD macro espansioni. In altre parole, quando si assegnano i vostri foo_s struct, si fanno tutto il allocazione di memoria per nedtries.

2. Per quanto riguarda la comprensione del "macro bene", è molto più facile capire la logica se si compila come C ++ e quindi eseguire il debug it :). Il C ++ usa costruire modelli e la debugger in modo pulito vi mostrerà lo stato in qualunque momento. In realtà, tutto debug dal mio fine accade in un C ++ accumulo e ho meticolosamente trascrivere modifiche del C ++ in macroised C.

3. Infine, prima di una nuova release, ho ricerca di Google per le persone che hanno problemi con il mio software per vedere se Posso sistemare le cose e io sono in genere stupito quello che qualcuno dice la gente di io e il mio software libero. In primo luogo, perché quelle persone non avendo difficoltà mi chiedono direttamente Aiuto? Se so che non c'è qualcosa che non va con la documentazione, quindi Posso risolvere - allo stesso modo, chiedendo su StackOverflow non fatemi sapere subito che c'è una documentazione problema fresa piuttosto si affida a me trovarlo prossima release. Quindi tutto quello che sarebbe dire è che se qualcuno trova un problema con i miei documenti, si prega di fare email me e dire così, anche se ci è un dire discussione come qui su stackflow.

Niall

Answer 3

In-luogo mezzi operate con i dati originali (input), quindi i dati di ingresso diventa i dati di uscita. Non-in-place significa che hai i dati di ingresso e di uscita separate, ei dati di input non viene modificato. In-luogo le operazioni di avere una serie di vantaggi - più piccola orma cache / memoria, banda di memoria inferiore, quindi in genere una migliore performance, ecc, ma hanno lo svantaggio che essi sono distruttivi, per esempio, si perde l'ingresso originale dati (che può o meno sostanze, a seconda del caso d'uso).

Answer 4

In-place mezzi per operare sui dati di ingresso e (eventualmente) aggiornarlo. L'implicazione è che non c'è la copia e / spostamento dei dati di input. Questo può portare a perdere i dati di input valori originali che si dovranno prendere in considerazione se è rilevante per il vostro caso particolare.