0

将以std::map最少的数据为例。
我有2张地图如下：

map<string, Object*> map_ShortKey; // keys are single English words
map<string, Object*> map_LongKey; // keys are concatenated English words

在map_ShortKey程序开始时填充了大约 50 个元素，并且始终保持不变。但是在map_LongKey整个程序中不断增加，它可能会达到 1000-10000 个元素。

当我想在这些地图中搜索一个词时，最好的方法是什么？

(1) 先在 中搜索map_ShortKey，如果没有则在 中搜索m_LongKey。
(2) 添加map_ShortKey到m_LongKey然后搜索

4

3 回答 3

2

你的意思是搜索一个词，还是搜索一个键？

如果map_LongKey包含连接的单词，则搜索连接的第一个单词将不成功。

但是，如果您正在搜索实际上是其中一张地图中的关键的东西，那么 (2) 的答案取决于很多事情 - 需要更多信息。

如果您关心速度，那么首先在最有可能包含密钥的地图中搜索。

如果速度不是您关心的问题，那么为了清晰起见构建您的代码 - 这是否涉及将地图合并在一起或以其他方式取决于您的情况。

于 2013-02-01T13:30:11.287 回答
1

这取决于成功查找的可能性map_Shortkey——如果很有可能，那么您只需在此搜索中花费 6 个“步骤”[log2(n)]，其中map_LongKey列表中的搜索平均为 10-13 个“步骤”。

另一方面，如果您不太可能在 中找到您要查找的内容map_shortKey，那么在大集合中的另外 50 个元素中进行搜索的额外负载不会产生太大影响。

由于我们不知道成功的统计数据，因此很难说哪种方法更好。

于 2013-02-01T13:30:27.673 回答
1

如果您喜欢最坏情况的复杂性并且对您的搜索一无所知（例如，在一张地图中比在另一张地图中更可能找到密钥），那么我会选择方法 1）。

在 an 中查找std::map具有对数的最坏情况复杂性，因此在第一种情况下，您最终会遇到log(n) + log(m)查找的最坏情况复杂性（假设您的地图分别具有n和m元素）。因此，k查找将花费您k * (log(n) + log(m))。

映射中的插入也具有对数复杂性，因此在第二种情况下，您将强制m从一个映射插入另一个映射，然后在带有m + n元素的映射中查找。因此，对于k查找（假设您只是第一次进行插入），您将获得m * log(n) + k * log(n + m)最坏情况的复杂性。

因此，如果您关心最坏情况的复杂性，则方法 1) 是可取的，只要：

k * (log(n) + log(m)) < m * log(n) + k * log(n + m)

k您可以根据您的工作量n和输入的大小进行估算m，然后进行数学运算以找出最好的（然后通过测量来仔细检查）。

于 2013-02-01T13:34:42.593 回答