algorithm - 在伪代码中使用动态二维数组或 HashMap ？

Question

我有一个网络算法，我应该有一个结构来存储每个节点在每个时钟滴答的位置。由于新节点可以随时加入网络，因此节点数量不是先验知识。此外，时钟滴答集不是先验已知的，并且随着时间的推移添加了新的时钟滴答条目。

要将此信息存储在我的伪代码中，我有两个选择:

1. 使用动态二维数组并具有类似的东西:

   array[i][t]=location of node i at time t
   

2. 使用二维 hashmap 并具有如下内容:

   map.set(i,t,location of node i at time t) 
   

其中 i 和 t 都是 HashMap 的键。

但在这两种情况下，我都不知道如何用伪代码遍历结构的所有元素，因为我不知道时钟滴答的范围和节点。我想我可以将添加的每个节点的 ID 和每个时钟滴答存储在两个不同的集合中，但我认为应该有更明智的方法来做到这一点。

所以，如果我使用一个二维数组，我想要这样的东西:

For all i in (set of node IDs for which we have stored locations)
    For all t in (set of times for which we have stored locations)
        if x < array[i][t] then return true,

如果我使用 HashMap ，

    For all i in (set of node IDs for which we have stored locations)
        For all t in (set of times for which we have stored locations)
             if x < map.get(i,t) then return true,

哪种结构更可取，我怎样才能以一种更明智的方式遍历所有元素，即一种较短的方式，因为我没有太多空间(最好不要添加额外的变量，例如用于存储时钟滴答的两组和节点 ID)并且易于理解？当然，只要可以用简短易懂的伪代码编写，关心内存使用或检索速度的解决方案都是受欢迎的。

Answer 1

首先，有一个滴答时间数组。这为您提供了从连续的整数值“滴答指数”到相应滴答时间的映射。

对于每个节点，存储它们加入网络时的滴答索引。

同样对于每个节点，存储一个位置样本数组，自它们加入以来每个 tick 一个。

(每个节点的信息可以存储在从节点 ID 到节点数据的映射中。)

遍历所有位置样本很简单:只需遍历节点，并针对每个节点遍历其位置样本。节点数组中每个位置样本的位置，再加上节点的基本刻度索引，将使您能够将该位置样本与其对应的刻度时间相关联。

这种方法最大限度地减少了内存使用，避免了哈希表容易出现的内存间接寻址，并允许沿任何维度轻松迭代和查找。