9

我正在编写一个复杂的树数据结构，它存储了很多指针。指针本身占用了大量空间，这就是我期望保存的。

所以我在这里问是否有这方面的例子。例如：对于 64 位数据类型，如果它指向的数据肯定是连续的，我可以使用 32 位或更少的指针吗？

我找到了一篇名为Transparent Pointer Compression for Linked Data Structures的论文，但我认为可能有一个更简单的解决方案。

更新：

它是一个八叉树。一篇关于 GPU 的论文是GigaVoxels: A Voxel-Based Rendering Pipeline For Efficient Exploration Of Large and detailed Scenes，他们在 GPU 上使用 15 位指针

4

5 回答 5

5

不使用指针，而是使用数组的索引。short如果数组长度小于 65536，则索引可以是 a ，如果小于 2147483648 ，则索引可以是int32_t 。

任意指针实际上可以位于内存中的任何位置，因此无法将其缩短超过几位。

于 2013-01-23T04:03:17.170 回答
1

一种选择是编写自定义分配器来分配大块连续内存，然后将节点连续存储在那里。然后，您的每个节点都可以通过一个简单的索引来引用，该索引可以使用简单的指针算法（例如：）映射回内存node_ptr = mem_block_ptr + node_index。

很快您就会意识到拥有多个这样的内存块意味着您不再知道特定节点驻留在其中的哪个内存块中。这就是分区出现的地方。您可以选择水平和/或垂直分区。两者都大大增加了复杂性，并且都各有利弊（参见[1]和[2]）。

这里的关键是确保以可预测的方式拆分数据。

参考：

  1. 构建可扩展的数据库：各种数据库分片方案的优缺点
  2. 37signals - 摩尔先生开始关注分片
于 2013-01-23T05:46:03.180 回答
1

如果指针的使用占用大量空间：

使用指针数组，并用该数组中的索引替换指针。这只是增加了另一个间接性。使用少于 64k 的指针，您需要一个 [ short ] 数组 (Linux)

简单的实现

#define   MAX_PTR  60000

void *aptr[MAX_PTR];
short nb = 0;

short ptr2index(void *ptr) {
  aptr[nb] = ptr;
  return (short)nb++;
}

void *index2ptr(short index) {
  return aptr[index];
}

... utilization ...

... short next; // in Class

Class *c = new Class();
mystruct->next = ptr2index((void *)c);

...

Class *x = (Class *)index2ptr(otherstruct->next);
于 2013-01-23T05:47:16.337 回答
1

在某些情况下，您可以简单地使用数组来保存节点。一个二叉树节点 atarr[i]会有来自arr[(i*2)+1]to的子节点arr[(i+1)*2]。如果 i != 0，它的父级将位于arr[(i-1)/2]。当然，要计算真正的指针地址，您可以说&arr[i]。对于按规范填充的树（例如用于堆的树）来说，这实际上是一种相当常见的实现。

但是，为了让节点自己知道如何找到它的子节点，您可能需要一个索引或指向容器的指针。（即便如此，只有两件中的一件，你必须做一些跳圈；你真的需要两件才能轻松地做事. 但是必须计算而不是记住它，当你试图不记得太多时，你付出的代价有点大。）为了使数据保持合理的空间效率，你必须让节点变笨；使它们基本上成为结构，甚至只是值，并让树类完成所有节点查找工作。它只是分发指向节点的指针，而该指针将是容器计算节点索引所需的全部内容（因此，它的子节点将在哪里）。您还必须将树指针和节点指针都传递给任何想要遍历树的函数。

但是请注意，除非您的树始终接近满（也就是说，除非您的大多数/所有叶节点都在末尾），否则这不会节省太多空间。对于不在树底部（顶部是根）的每个叶节点，您会浪费 ((node size) * (tree size / i)) 字节。

如果您不能指望树已满，或者节点位于某个受限空间中，那么这里没有太多需要优化的地方。树的全部意义在于节点具有指向其子节点的指针；您可以使用数组来伪造它，但必须很容易以某种方式找到节点的子节点才能使树变得有价值。

于 2013-01-23T04:39:09.013 回答
0

处理您的问题的一个非常简单的方法就是使用更少的指针（看起来很傻）？

比较以下两种方法：

template <typename T>
struct OctreeNaiveNode {
    T value;
    Point center;
    OctreeNaiveNode* parent;
    std::unique_ptr<OctreeNaiveNode> children[8];
}; // struct OctreeNaiveNode

// sizeof(OctreeNaiveNode) >= sizeof(T) + sizeof(Point) + 9 * sizeof(void*)

template <typename T>
struct OctreeNode {
    T value;
    Point center;
    std::unique_ptr<OctreeNode[]> children; // allocate for 8 only when necessary
}; // struct OctreeNode

// sizeof(OctreeNode) >= sizeof(T) + sizeof(Point) + sizeof(void*)

它是如何工作的：

  • 父指针只对简单的迭代器是必需的，如果你的迭代器比节点少得多，那么拥有深度迭代器更经济：即，将一堆父节点保存到根的迭代器。请注意，在 RB-tree 中它不能很好地工作（平衡），但在八叉树中它应该更好，因为分区是固定的。
  • 单个子指针：建立一个指向子数组的指针，而不是一个指向子指针的数组。这不仅意味着 1 个动态分配而不是 8 个（堆碎片/开销更少），而且还意味着节点内的 1 个指针而不是 8 个。

高架：

  • Point = std::tuple<float,float,float>=> sizeof(T) + sizeof(Point) >= 64=> +100%
  • Point = std::tuple<double,double,double>=> sizeof(T) + sizeof(Point) >= 256=> +25%

因此，与其深入研究压缩指针策略，我建议您首先重新设计数据结构以减少指针/间接。

于 2013-01-25T08:04:04.690 回答