was der Autor von nedtries Mitteln durch „in-place“?

Question

I. Nur implementiert eine Art bitweise trie (basierend auf nedtries), aber mein Code macht viel Die Speicherzuweisung (für jeden Knoten). Im Gegensatz zu meiner Implementierung, nedtries beansprucht, schnell zu sein, unter othet Dingen, Aufgrund ihrer geringen Anzahl der Speicherzuweisung (falls vorhanden). Der Autor behauptet seine Implementierung als „in-place“, aber was bedeutet es wirklich bedeutet in diesem Zusammenhang? Und wie nedtries erreichen so eine kleine Anzahl von dynamischer Speicherzuweisung?

Ps: Ich weiß, dass die Quellen zur Verfügung stehen, aber der Code ist ziemlich schwer zu folgen, und ich kann nicht verstehen, wie es funktioniert

Answer 1

habe ich einen Blick auf die nedtrie.h Quellcode. Es scheint, dass der Grund, warum es „in-place“ ist, dass Sie haben die Trie-Buchhaltungsdaten, um die Elemente hinzufügen, dass Sie speichern möchten.

Sie verwenden das NEDTRIE_ENTRY Makro Eltern / Kind / next / prev Links zu Ihrer Datenstruktur hinzuzufügen, und Sie können dann diese Datenstruktur an die verschiedenen Trie-Routinen übergeben, die diese hinzugefügt Mitglieder extrahieren und verwenden.

Es ist also „in-place“ in dem Sinne, dass Sie Ihre vorhandenen Datenstrukturen und den Trie-Code huckepack auf, dass erweitern.

zumindest das ist, wie es aussieht. Es gibt viele Makro Güte in diesem Code, so hätte ich mich bekommen verwirrt (:

Answer 2

Ich bin der Autor, so dass diese zum Wohle der vielen nach Google ist, die sich mit der nedtries ähnlich Schwierigkeiten haben werden. Ich möchte die Leute hier auf stackflow danken für nicht unangenehm Kommentare über mich machen persönlich die einige andere Diskussionen über nedtries tun.

1. Ich fürchte, ich verstehe nicht, die Schwierigkeiten mit zu wissen, wie es zu benutzen. Die Benutzung ist denkbar einfach - einfach kopieren Sie das Beispiel in der Readme.html-Datei:

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

Sie deklarieren Elementtyp - hier ist es die Struktur foo_s. Sie müssen die NEDTRIE_ENTRY () im Inneren sonst kann es, was Sie wollen enthalten. Sie müssen auch eine Schlüsselerzeugungsfunktion. Other than that, es ist ziemlich vorformulierten.

würde ich dieses System nicht von Makro Initialisierung selbst basiert gewählt haben! Aber es ist für die Kompatibilität mit dem BSD rbtree.h so nedtries ist sehr einfach zu tauschen, um etwas BSD rbtree.h verwendet wird.

1. In Bezug auf meine Verwendung von "in place" Algorithmen, gut schätze ich meinen Mangel an Informatik Ausbildung zeigt Hier. Was würde ich „in place“ nennen Nur wenn Sie den Speicher verwenden in ein Stück Code übergeben, so dass, wenn Sie Hand 64 Bytes an einen an Ort und Stelle Algorithmus wird es berührt nur, dass 64 Bytes das heißt, es wird nicht Gebrauch machen zusätzliche Metadaten oder zuteilen einig Zusätzliche Speicher oder in der Tat schreiben zu globaler Zustand. Ein gutes Beispiel ist ein „In place“ Art Implementierung, bei der nur die Sammlung sortiert werden (Und ich nehme den Thread-Stack) wird berührt.

   Daher nein, nicht nedtries nicht brauchen ein Zu. Es speichert alle Daten braucht es in der NEDTRIE_ENTRY und NEDTRIE_HEAD Makroerweiterungen. Mit anderen Worten, wenn Sie zuweisen Ihre Struktur foo_s, tun Sie alle Speicherzuweisung für nedtries.

2. Im Hinblick auf das Verständnis der „Makro Güte“, es ist viel einfacher, verstehe die Logik, wenn Sie kompilieren es wie C ++ und dann Debug-it :). Das C ++ Build verwendet Vorlagen und die Debugger werden Sie sauber Zustand zeigen zu einem bestimmten Zeitpunkt. In der Tat, alle Debuggen von meinem Ende geschieht in einem C ++ Build und ich akribisch transkribieren die C ++ Änderungen in macroised C.

3. Schließlich, bevor ein neues Release, ich Google-Suche für Menschen mit Probleme mit meiner Software zu sehen, ob Ich kann Dinge reparieren und ich bin normalerweise Leute erstaunt, was jemand sagen ich und meine freie Software. Zuerst, warum nicht die Leute, die Schwierigkeiten fragen Sie mich direkt für Hilfe? Wenn ich weiß, dass es etwas falsch mit den Dokumenten, dann Ich kann sie beheben - ebenso, fragen auf Stackoverflow nicht lassen Sie mich wissen, sofort, dass es ein docs Problem bur verlässt sich eher auf mich finden es nächste Release. Also alles, würde ich sagen wir, dass, wenn jemand eine findet Problem mit meiner docs, bitte mailen Sie mir und sagen, so, auch wenn es ist eine Diskussion sagen, wie hier auf stackflow.

Niall

Answer 3

In-place Mittel Sie auf dem Original (Eingang) Daten arbeiten, so dass die Eingangsdaten die Ausgangsdaten werden. Nicht-in-place bedeutet, dass Sie separate Ein- und Ausgangsdaten haben, und die Eingangsdaten werden nicht geändert. In-place Operationen haben eine Reihe von Vorteilen - kleiner Cache / Speicherbedarf, geringere Speicherbandbreite, also typischerweise eine bessere Leistung, etc., aber sie haben den Nachteil, dass sie destruktiv, dh Sie den ursprünglichen Eingang verlieren Daten (die können oder auch nicht Sache, auf dem je nach Anwendungsfall).

Answer 4

In-Place-Mittel an den Eingangsdaten zu arbeiten und (möglicherweise) aktualisieren. Die Implikation ist, dass es kein Kopieren und / Verschieben der Eingangsdaten. Dies kann dazu führen, die Eingangsdaten ursprünglichen Werte in zu verlieren, die Sie berücksichtigen müssen, wenn sie für Ihren speziellen Fall relevant ist.