1

当我不断寻找相同的键时，我所知道的数据结构（例如 b-tree 或 rb-tree）不会改变。我正在寻找一种在运行时优化自身的数据结构，以便更快地查找常用键。现在我有一个像这样的天真的实现：

ValueType MyNaiveMap::get(KeyType key) {
  innerMap.addFreq(key);
  if (key == mostFreqUsedKey1) {
    return val1;
  } else if (key == mostFreqUsedKey2) {
    return val2;
  }
  else {
    return innerMap.get(key);
  }
}

钥匙总是int在我的情况下。

更新：

我忘了提到哈希图。因为地图可能会增长到非常大的大小，所以我试图避免调整大小，这在运行时是 O(n) 复杂的。

4

2 回答 2

2

如果您提前知道总大小，或者如果由于调整大小而导致的 O(n) 插入（但在平均情况下仍为 O(1) 摊销）对您来说是可以的，那么我认为哈希表是最好的选择。调整大小时复制整个表的一次性命中也可以通过使用增量调整大小分布到多个操作中。

您必须保持哈希表部分为空以避免冲突，这可能感觉像是在浪费内存。但是对于基于树的映射，通常每个项目至少有一个额外的指针，这也会“浪费”大量内存。此外，使用哈希表，您可以调整其中的多少以保持空白，部分交易性能以换取内存（反之亦然）。

但是还有一个基于树的数据结构优化用于查找最近访问的键：splay tree。它使用旋转将最近使用的键保持在根附近，同时仍保持 O(log n) 的分摊最坏情况以进行插入和搜索。（那个“摊销”位很重要，一些操作仍然可以是 O(n)）。

于 2013-01-22T19:57:57.393 回答
1

您可以在内部跟踪最常用的 X 值/键。对您首先检查的这些值进行快速缓存（在检查较大的数据树之前）。跟踪项目被访问/查看的次数。如果在视图中，该项目的查看次数超过列表中的最后一项，您可以确定在迷你列表中的位置。这样，要查看您是否将新项目添加到此快速查找中，您只需检查其中的最后一个值以查看是否需要替换它。

定期使用最高查找值。

于 2013-01-22T19:13:11.223 回答