6


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

Ps：我知道资源是可用的，但是代码很难理解，我不知道它是如何工作的

4

4 回答 4

10

我是作者，所以这是为了谷歌的许多人的利益，他们在使用 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;



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 兼容，所以 nedtries 很容易使用 BSD rbtree.h 换成任何东西。

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

    因此，不，nedtries 不需要内存分配器。它将所需的所有数据存储在 NEDTRIE_ENTRY 和 NEDTRIE_HEAD 宏扩展中。换句话说，当您分配 struct foo_s 时，您会为 nedtries 分配所有内存。

  2. 关于理解“宏观优点”，如果将其编译为 C++ 然后调试它，理解逻辑要容易得多:)。C++ 构建使用模板，调试器将在任何给定时间清晰地显示您的状态。事实上，我的所有调试都发生在 C++ 构建中，我小心翼翼地将 C++ 更改转录为宏化 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

于 2011-06-19T18:09:43.920 回答
4

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

于 2011-01-14T14:34:59.610 回答
4

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

您使用 NEDTRIE_ENTRY 宏将 parent/child/next/prev 链接添加到您的数据结构，然后您可以将该数据结构传递给各种 trie 例程，这些例程将提取并使用这些添加的成员。

因此，它是“就地”的，因为您可以扩充现有的数据结构并搭载 trie 代码。

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

于 2011-01-20T17:32:13.343 回答
-1

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

于 2011-01-14T14:53:07.250 回答