当前位置： 文江博客话题详情

nedtries的作者所说的“就地”是什么意思？

发布于 2024-10-12 04:58:27 字数 223 浏览 5 评论 0原文


I.刚刚实现了一种按位trie（基于nedtries），但我的代码做了很多 内存分配（针对每个节点）。 与我的实现相反， nedtries 据称速度很快，除此之外， 因为它们的内存分配数量很少（如果有的话）。 作者声称他的实现是“就地”，但在这种情况下它的真正含义是什么？ 而nedtries是如何实现如此少量的动态内存分配的呢？

PS：我知道源代码是可用的，但代码很难理解，我无法弄清楚它是如何工作的

原文

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

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（4）

云淡月浅 2024-10-19 04:58:27

我是作者，所以这是为了谷歌所说的许多在使用 nedtries 时同样遇到困难的人的利益。我要感谢 stackflow 上的人们没有像其他一些关于 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;



静态 size_t fookeyfunct(const foo_t *RESTRICT r)
{
  返回 r-> 键；
NEDTRIE_GENERATE



 (静态, foo_tree_s, foo_s, 链接, fookeyfunct, NEDTRIE_NOBBLEZEROS(foo_tree_s));



 int 主函数（无效）
{
  foo_t a、b、c、*r；
  NEDTRIE_INIT(&foottree);
  a.key=2；
  NEDTRIE_INSERT(foo_tree_s, &footree, &a);
  b.键=6；
  NEDTRIE_INSERT(foo_tree_s, &footree, &b);
  r=NEDTRIE_FIND(foo_tree_s, &footree, &b);
  断言(r==&b);
  c.key=5；
  r=NEDTRIE_NFIND(foo_tree_s, &footree, &c);
  断言(r==&b); /* NFIND 找到下一个最大的。反转关键函数以反转此 */
  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);
  返回0；
}

您声明您的项目类型 - 这里是 struct foo_s。您需要在其中包含 NEDTRIE_ENTRY()，否则它可以包含您喜欢的任何内容。您还需要一个密钥生成函数。除此之外，它是相当样板的。

我自己不会选择这种基于宏的初始化系统！但它是为了与 BSD rbtree.h 兼容，因此 nedtries 很容易交换到使用 BSD rbtree.h 的任何东西。

  1. 关于我对“就地”的使用
    算法，好吧，我想我缺乏
    计算机科学培训节目
    这里。我称之为“到位”
    当你只使用内存时
    传递到一段代码中，所以如果
    你把 64 字节交给一个就地的
    算法只会触及64
    字节，即它不会使用
    额外的元数据，或分配一些
    额外的内存，或者确实写入
    全局状态。一个很好的例子是
    “就地”排序实现在哪里
    仅正在排序的集合
    （我想是线程堆栈）
    被触动。

    因此不，nedtries 不需要
    内存分配器。它存储了所有
    NEDTRIE_ENTRY 中所需的数据
    和 NEDTRIE_HEAD 宏扩展。
    换句话说，当你分配
    你的结构 foo_s，你做了所有的
    nedtries 的内存分配。

  2. 关于理解“宏观”
    天哪”，这要容易得多
    如果你编译就理解逻辑
    它作为 C++，然后调试它:)。这
    C++ 构建使用模板和
    调试器将清楚地向您显示状态
    在任何给定时间。事实上，所有
    我的调试发生在
    C++构建，我精心打造
    将 C++ 更改转录为
    宏化C。

  3. 最后，在新版本发布之前，我
    在 Google 上搜索有以下情况的人
    我的软件有问题，看看是否
    我可以解决问题，而且我通常都是这样
    惊讶于人们的评价
    我和我的自由软件。首先，
    为什么那些人没有
    有困难直接问我
    帮助？如果我知道有
    那么文档有问题
    我可以修复它们 - 同样，询问
    stackoverflow 不让我知道
    立即有一个文档
    问题在于我要
    找到它的下一个版本。所以我愿意
    说的是如果有人发现
    我的文档有问题，请这样做
    给我发电子邮件并这么说，即使有
    是这样的讨论
    stackflow。

尼尔

I'm the author, so this is for the benefit of the many according to Google who are similarly having difficulties in using nedtries. I would like to thank the people here on stackflow for not making unpleasant comments about me personally which some other discussions about nedtries do.

  1. I am afraid I don't understand the difficulties with knowing how to use it. Usage is exceptionally easy - simply copy the example in the Readme.html file:

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

You declare your item type - here it's struct foo_s. You need the NEDTRIE_ENTRY() inside it otherwise it can contain whatever you like. You also need a key generating function. Other than that, it's pretty boilerplate.

I wouldn't have chosen this system of macro based initialisation myself! But it's for compatibility with the BSD rbtree.h so nedtries is very easy to swap in to anything using BSD rbtree.h.

  1. Regarding my usage of "in place"
    algorithms, well I guess my lack of
    computer science training shows
    here. What I would call "in place"
    is when you only use the memory
    passed into a piece of code, so if
    you hand 64 bytes to an in place
    algorithm it will only touch that 64
    bytes i.e. it won't make use of
    extra metadata, or allocate some
    extra memory, or indeed write to
    global state. A good example is an
    "in place" sort implementation where
    only the collection being sorted
    (and I suppose the thread stack)
    gets touched.

    Hence no, nedtries doesn't need a
    memory allocator. It stores all the
    data it needs in the NEDTRIE_ENTRY
    and NEDTRIE_HEAD macro expansions.
    In other words, when you allocate
    your struct foo_s, you do all the
    memory allocation for nedtries.

  2. Regarding understanding the "macro
    goodness", it's far easier to
    understand the logic if you compile
    it as C++ and then debug it :). The
    C++ build uses templates and the
    debugger will cleanly show you state
    at any given time. In fact, all
    debugging from my end happens in a
    C++ build and I meticulously
    transcribe the C++ changes into
    macroised C.

  3. Lastly, before a new release, I
    search Google for people having
    problems with my software to see if
    I can fix things and I am typically
    amazed what someone people say about
    me and my free software. Firstly,
    why didn't those people having
    difficulties ask me directly for
    help? If I know that there is
    something wrong with the docs, then
    I can fix them - equally, asking on
    stackoverflow doesn't let me know
    immediately that there is a docs
    problem bur rather relies on me to
    find it next release. So all I would
    say is that if anyone finds a
    problem with my docs, please do
    email me and say so, even if there
    is a discussion say like here on
    stackflow.

Niall

回复 原文
无言温柔 2024-10-19 04:58:27

我看了一下 nedtrie.h 源代码。
看来它是“就地”的原因是您必须将trie簿记数据添加到您想要存储的项目中。

您可以使用 NEDTRIE_ENTRY 宏将父/子/下一个/上一个链接添加到数据结构中，然后可以将该数据结构传递给各种 trie 例程，这些例程将提取并使用这些添加的成员。

因此，它是“就地”的，因为您可以增强现有的数据结构以及其上的 trie 代码。

至少看起来是这样。该代码中有很多宏观的优点，所以我可能会让自己感到困惑（：

I took a look at the nedtrie.h source code.
It seems that the reason it is "in-place" is that you have to add the trie bookkeeping data to the items that you want to store.

You use the NEDTRIE_ENTRY macro to add parent/child/next/prev links to your data structure, and you can then pass that data structure to the various trie routines, which will extract and use those added members.

So it is "in-place" in the sense that you augment your existing data structures and the trie code piggybacks on that.

At least that's what it looks like. There's lots of macro goodness in that code so I could have gotten myself confused (:

回复 原文
拥醉 2024-10-19 04:58:27

就地意味着您对原始（输入）数据进行操作，因此输入数据成为输出数据。 Not-in-place意味着你有单独的输入和输出数据，并且输入数据没有被修改。 就地操作有很多优点 - 较小的缓存/内存占用、较低的内存带宽，因此通常具有更好的性能等，但它们的缺点是具有破坏性，即您会丢失原始输入数据（这可能重要也可能不重要，具体取决于用例）。

In-place means you operate on the original (input) data, so the input data becomes the output data. Not-in-place means that you have separate input and output data, and the input data is not modified. In-place operations have a number of advantages - smaller cache/memory footprint, lower memory bandwidth, hence typically better performance, etc, but they have the disadvantage that they are destructive, i.e. you lose the original input data (which may or may not matter, depending on the use case).

回复 原文
月牙弯弯 2024-10-19 04:58:27

就地意味着对输入数据进行操作并（可能）更新它。这意味着不存在输入数据的复制和/移动。这可能会导致丢失输入数据原始值，如果它与您的特定情况相关，您需要考虑这些原始值。

In-place means to operate on the input data and (possibly) update it. The implication is that there no copying and/moving of the input data. This may result in loosing the input data original values which you will need to consider if it is relevant for your particular case.

回复 原文
~没有更多了~

关于作者

是你

暂无简介

0 文章
0 评论
22 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

留蓝

文章 0 评论 0

18790681156

文章 0 评论 0

zach7772

文章 0 评论 0

Wini

文章 0 评论 0

ayeshaaroy

文章 0 评论 0

初雪

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文