Nedtriesの著者は「In-Place」とはどういう意味ですか？

Question

I.一種のビットワイズトリエを実装しました（ネットトリーに基づいて）が、私のコードは（各ノードに対して）多くのメモリ割り当てを実行します。私の実装とは反対に、彼のメモリの割り当ての数が少ないため（もしあれば）、オセットの間では、nedtriesが速いと主張されています。著者は、自分の実装が「インプレース」であると主張していますが、この文脈ではそれは本当に何を意味しますか？そして、Nedtriesはどのようにしてこのような少数の動的なメモリ割り当てを達成しますか？

PS：ソースが利用可能であることは知っていますが、コードをフォローするのがかなり難しく、どのように機能するかを理解できません

Answer 1

Nedtrie.hソースコードを見てみました。それが「屋内」である理由は 君 トライブックキーピングデータを保存したいアイテムに追加する必要があります。

nedtrie_entryマクロを使用して、親/子/次のリンクをデータ構造に追加し、そのデータ構造をさまざまなTrieルーチンに渡すことができます。

したがって、既存のデータ構造とトライコードのピギーバックを補強するという意味で、「在籍」です。

少なくともそれがどのように見えるかです。そのコードにはマクロの良さがたくさんあるので、私は自分自身を混乱させることができたでしょう（：

Answer 2

私は著者なので、これは、同様にnedtryを使用するのが難しいGoogleによると、多くの人々の利益のためです。私は、私について個人的に不快なコメントをしてくれなかったことをStackflowの人々に感謝したいと思います。

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 *制限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（＆letree）; A.Key = 2; nedtrie_insert（foo_tree_s、＆letree、＆a）; B.Key = 6; nedtrie_insert（foo_tree_s、＆letree、＆b）; r = nedtrie_find（foo_tree_s、＆letree、＆b）; assert（r ==＆b）; C.Key = 5; r = nedtrie_nfind（foo_tree_s、＆letree、＆c）; assert（r ==＆b）; /* nfindは次の最大を見つけます。重要な関数を反転してこの */ nedtrie_remove（foo_tree_s、＆letree、＆a）; nedtrie_foreach（r、foo_tree_s、＆letree）{printf（ "％p、％u  n"、r、r-> key）; } nedtrie_prev（foo_tree_s、＆letree、＆a）; 0を返します。 }

アイテムの種類を宣言します - ここではstruct foo_sです。それ以外の場合は、その中にnedtrie_entry（）が必要です。また、キー生成関数も必要です。それ以外は、それはかなりのボイラープレートです。

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

1. 「In Inthe」アルゴリズムの使用に関して、コンピューターサイエンスのトレーニングの欠如がここに示されていると思います。私が「所定の位置に」と呼ぶのは、メモリをコードの一部にのみ使用する場合です。したがって、64バイトを所定のアルゴリズムに渡すと、64バイトのみに触れます。つまり、余分なメタデータは使用できません。 、またはいくつかの余分なメモリを割り当てるか、実際にグローバルな状態に書き込みます。良い例は、コレクションのみがソートされている（そして、スレッドスタックが触れられると思われる）「In In In In In」ソート実装です。

   したがって、Nedtriesはメモリアロケーターを必要としません。 Nedtrie_EntryおよびNedtrie_headマクロ拡張に必要なすべてのデータを保存します。言い換えれば、struct foo_sを割り当てると、nedtoryのすべてのメモリ割り当てを行います。

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

3. 最後に、新しいリリースの前に、私はソフトウェアに問題がある人をGoogleを検索して、物事を修正できるかどうかを確認します。私と私のフリーソフトウェアについて誰かが言うことに驚かされます。第一に、なぜ彼らの人々が私に直接助けを求めなかったのですか？ドキュメントに何か問題があることを知っていれば、それらを修正することができます - 同様に、Stackoverflowで尋ねることは、次のリリースを見つけるために私に依存しているドキュメントの問題があることをすぐに知らせません。だから私が言うことは、誰かが私のドキュメントに問題を見つけた場合、私にメールして、Stackflowについてのような議論があるとしても、そう言ってください。

ニール

Answer 3

所定の位置に 元の（入力）データを操作することを意味するため、入力データが出力データになります。 在庫がありません 個別の入力データと出力データがあり、入力データが変更されていないことを意味します。 所定の位置に 操作には多くの利点があります - より小さなキャッシュ/メモリフットプリント、より低いメモリ帯域幅、したがって通常はパフォーマンスの低下などがありますが、それらは破壊的であるという不利な点があります。ユースケースについて）。

Answer 4

インプレースとは、入力データを操作し、（おそらく）更新することを意味します。意味は、入力データのコピーや移動がないということです。これにより、入力データの元の値が失われる可能性があり、特定のケースに関連する場合は考慮する必要があります。