6


I. Just implemented a kind of bitwise trie (based on nedtries), but my code does lot Of memory allocation (for each node). Contrary to my implemetation, nedtries are claimed to be fast , among othet things, Because of their small number of memory allocation (if any). The author claim his implementation to be "in-place", but what does it really means in this context ? And how does nedtries achieve such a small number of dynamic memory allocation ?

Ps: I know that the sources are available, but the code is pretty hard to follow and I cannot figure how it works

4

4 に答える 4

10

私は著者なので、これは Google によると、同様に nedtries の使用に問題を抱えている多くの人々の利益のためです。ネドトリーに関する他のいくつかの議論がそうであるように、私について個人的に不快なコメントをしないために、スタックフローの人々に感謝したいと思います。

  1. 使用方法を知ることの難しさを理解していないのではないかと心配しています。使い方は非常に簡単です。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;
}

項目タイプを宣言します - ここでは struct foo_s です。その中に NEDTRIE_ENTRY() が必要です。それ以外の場合は、好きなものを含めることができます。鍵生成関数も必要です。それ以外は、かなりボイラープレートです。

このマクロベースの初期化システムを自分で選択することはなかったでしょう! ただし、これは BSD rbtree.h との互換性のためのものであるため、BSD rbtree.h を使用して nedtries を簡単に交換できます。

  1. 「インプレース」アルゴリズムの使用に関しては、コンピュータ サイエンスのトレーニングが不足していると思います。私が「インプレース」と呼ぶのは、コードの一部に渡されたメモリのみを使用する場合です。そのため、64 バイトをインプレース アルゴリズムに渡すと、その 64 バイトのみが処理されます。つまり、余分なメタデータは使用されません。 、または追加のメモリを割り当てるか、実際にグローバル状態に書き込みます。良い例は、ソートされているコレクション (そしておそらくスレッド スタック) だけが処理される "インプレース" ソートの実装です。

    したがって、いいえ、nedtries にはメモリ アロケータは必要ありません。必要なすべてのデータを NEDTRIE_ENTRY および NEDTRIE_HEAD マクロ展開に格納します。言い換えれば、構造体 foo_s を割り当てるとき、nedtries のすべてのメモリ割り当てを行います。

  2. 「マクロの良さ」の理解に関しては、C++としてコンパイルしてからデバッグすると、ロジックを理解するのがはるかに簡単になります:)。C++ ビルドはテンプレートを使用し、デバッガーはいつでも状態を明確に表示します。実際、私の側からのすべてのデバッグは C++ ビルドで行われ、C++ の変更を細心の注意を払ってマクロ化された C に書き起こします。

  3. 最後に、新しいリリースの前に、自分のソフトウェアに問題を抱えている人を Google で検索して、問題を修正できるかどうかを確認します。通常、誰かが私とフリー ソフトウェアについて何を言っているかに驚かされます。まず、なぜ困っている人は私に直接助けを求めなかったのですか？ドキュメントに何か問題があることがわかっている場合は、それらを修正できます。同様に、stackoverflow に問い合わせても、ドキュメントに問題があることをすぐに知ることはできません。だから私が言いたいのは、誰かが私のドキュメントに問題を見つけたら、私に電子メールを送ってそのように言ってください。

ニール

于 2011-06-19T18:09:43.920 に答える
4

インプレースとは、元の (入力) データを操作することを意味するため、入力データが出力データになります。Not-in-placeとは、入力データと出力データが別々であり、入力データが変更されていないことを意味します。インプレース操作には多くの利点があります - キャッシュ/メモリフットプリントが小さい、メモリ帯域幅が小さいため、通常はパフォーマンスが向上するなどですが、破壊的であるという欠点があります。つまり、元の入力データが失われる可能性がありますユースケースに応じて）。

于 2011-01-14T14:34:59.610 に答える
4

nedtrie.h のソース コードを調べました。「インプレース」である理由は、保存したいアイテムにトライ簿記データを追加する必要があるためのようです。

NEDTRIE_ENTRY マクロを使用して、親/子/次/前のリンクをデータ構造に追加します。その後、そのデータ構造をさまざまなトライ ルーチンに渡すことができます。トライ ルーチンは、追加されたメンバーを抽出して使用します。

したがって、既存のデータ構造を拡張し、トライ コードがそれに便乗するという意味で、「インプレース」です。

少なくともそのように見えます。そのコードには多くの優れたマクロが含まれているため、混乱する可能性がありました (:

于 2011-01-20T17:32:13.343 に答える
-1

インプレースとは、入力データを操作し、(場合によっては) 更新することを意味します。つまり、入力データのコピーや移動はありません。これにより、特定のケースに関連するかどうかを考慮する必要がある入力データの元の値が失われる可能性があります。

于 2011-01-14T14:53:07.250 に答える