7

我需要编写一个测试平台来测试特定的算法。该系统应该可以通过输入和 3 维来定义 - 类似于片上网络，它具有节点和链接元素来连接它们。由于节点之间的维度和链接，我在确定要使用的数据结构方面遇到了一些困难——像 array[x][y][z] 这样的 3 维数组很难作为指针处理，在添加链接时有缺点连接节点（在结构中留下几个空值孔）。二叉搜索树很难实现，因为它是网格类型。出于这个原因，我考虑过做一个链接更容易实现的链接列表。（最终的测试平台应该类似于下面的演示文稿）其中每个链接也被映射下来，因为它们包含通信时间表

01-------02-------03
| \      | \      | \
|  10----|--11----|--12
|  | \   |  | \   |  | \
|  |  19-|--|--20-|--|--21
04-------05-------06 |  |
| \   |  | \|  |  | \|  |
|  13----|--14----|--15 |
|  | \|  |  | \|  |  | \|
|  |  22-|--|--23-|--|--24
07-------08-------09 |  |
  \|  |    \|  |    \|  |
   16-------17-------18 |
     \|       \|       \|
      25-------26-------27

你们中的任何人都可以就c ++中哪种类型的结构适合这种任务提供一些帮助。给定 x、y 和 z 的维度参数，完成的程序应该能够生成这样的结构。

目前粗略的轮廓应该是这样的

>class Node{
>  public:
>   Link* north;
>   Link* east;
>   Link* south;
>   Link* west;
>   Link* up;
>   Link* down;
>   //will contain a node specific scheduler
>}
>
>class Link{
>
>   Node* A;
>   Node* B;
>   //will contain a link specific scheduler
>}

编辑 22.01.2013

首先，它是一个模拟三维网络片上多处理器系统的测试平台。该系统必须完成的任务是能够测试某些算法以帮助将任务映射到这些节点（每个节点都连接到一个处理器内核）。鉴于此，内存消耗可能不是问题，因为它仅用于测试，正如我所说，因此系统必须同时具有节点和链接，因为它们都不能被两个事件使用同时（链接上的通信将阻塞所有其他通信等，这就是我写类类型节点/链接将在其中包含调度程序的原因）

4

1 回答 1

11

这在很大程度上取决于您将在该结构上执行什么样的操作。你必须做搜索吗？如果是这样，是什么类型的：基于价值的还是基于位置的？您是否必须对其执行转换？您是否必须按顺序重复访问其所有元素？您是否必须根据元素在网格中的位置访问元素？你的结构是稀疏的还是密集的？

此外，您想尽量减少创建时间、搜索时间、导航时间或转换时间吗？这一切都为做出决定提供了基本信息。

我不会寻求基于节点和链接的解决方案，因为它是：

  1. 在内存消耗方面很昂贵（由于额外的链接指针）；
  2. 在复杂性方面很昂贵（导航所有节点需要跟踪所有链接，因此没有随机访问），并且；
  3. 在数据局部性方面代价高昂（节点将被单独分配并分布在不同地址的堆中，这将产生许多缓存未命中并减慢您的程序）；
  4. 容易出错（弄乱链接很容易，特别是如果您使用原始指针并且不想为智能指针的内存开销付费）

在不太了解您的要求的情况下，我可能会建议您查看Boost.MultiArray。

如果您想自己做事，那么（同样，在不太了解您的要求的情况下）我建议您使用 a vector<vector<vector<double>>>，它相对简单，没有固定大小并允许您在运行时调整大小，保证您O(1) 通过下标运算符访问以及数据的某些局部性（这里有几个向量，所以只要从一个向量访问数据就可以了）。

一个普通的 C 风格的多维数组也是一种可能，但它本质上是不安全的，如果我是你，这将使它成为最后的选择（另外，如果你的结构很大，分配一个连续的内存块可能是不可能的） .

于 2013-01-21T15:47:28.623 回答