nedtries的作者是什么意思"就地"？

Question

nedtries的作者是什么意思"就地"？

fok*_*ute 6 c binary-tree bit-manipulation trie patricia-trie

I.刚刚实现了一种按位trie(基于nedtries),但我的代码执行了很多内存分配(对于每个节点).与我的实现相反,在其他事物中声称nedtries很快,因为它们的内存分配数量很少(如果有的话).作者声称他的实施是"就地"的,但在这种情况下它的真正含义是什么？nedtries如何实现如此少量的动态内存分配？

Ps:我知道源代码可用,但代码很难遵循,我无法弄清楚它是如何工作的

Answer 1

Nia*_*las 10

我是作者,所以这是为了谷歌的许多人的利益,他们同样难以使用nedtries.我要感谢这里的人们在stackflow上没有对我个人做出令人不快的评论,其他一些关于nedtries的讨论也是如此.

我不知道知道如何使用它的困难.用法非常简单 - 只需复制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很容易交换到任何东西.


关于我对"就地"算法的使用,我想我在这里缺乏计算机科学培训.我称之为"就地"的是当你只使用传递给一段代码的内存时,所以如果你把64个字节移到一个就地算法,那么它只会触及64个字节,即它不会使用额外的元数据,或者分配一些额外的内存,或者确实写入全局状态.一个很好的例子是"就地"排序实现,其中只有被排序的集合(我认为线程堆栈)被触及.

因此,nedtries不需要内存分配器.它将所需的所有数据存储在NEDTRIE_ENTRY和NEDTRIE_HEAD宏扩展中.换句话说,当您分配struct foo_s时,您将为nedtries执行所有内存分配.
关于理解"宏观优点",如果将其编译为C++然后调试它,则更容易理解逻辑.C++构建使用模板,调试器将在任何给定时间干净地显示状态.事实上,我的所有调试都是在C++版本中进行的,我会将C++更改精心转录为宏观C.
最后,在新版本发布之前,我会搜索Google以查找我的软件有问题的人,看看我是否可以解决问题,而且我常常对别人对我和我的免费软件的看法感到惊讶.首先,为什么有困难的人不直接向我求助？如果我知道文档有问题,那么我可以修复它们 - 同样地,在stackoverflow上询问不会立即让我知道有一个文档问题,而是依赖于我在下一个版本中找到它.所以我要说的是,如果有人发现我的文档有问题,请给我发电子邮件并说出来,即使有关于stackflow的讨论也是如此.


尼尔

        
          
          
              我只想指出"就地"是一个非常含糊的术语.我认为人们在这里寻找的术语是"Intrusive",这是非常明确的,我已经看到它与许多其他数据结构一起使用,期望他们的书保持指针被分配在他们的数据中. (3认同)

Answer 2

jwd*_*jwd 4

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

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

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

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

是的，这通常被称为“侵入式”链表。 (2认同)

归档时间：	14 年，11 月前
查看次数：	1130 次
最近记录：	14 年，5 月前