c++ - 如何加速一个简单的方法(最好不改变接口(interface)或数据结构)？

Question

我有一些数据结构:

• all_unordered_m 是一个大 vector ，包含我需要的所有字符串(全部不同)
• ordered_m 是一个小 vector ，包含前一个 vector 中字符串子集(所有不同)的索引
• position_m 将对象的索引从第一个 vector 映射到它们在第二个 vector 中的位置。

string_after(index, reverse) 方法返回 ordered_m after all_unordered_m[index] 引用的字符串。

ordered_m 被认为是循环的，根据第二个参数以自然顺序或倒序进行探索。

代码如下:

struct ordered_subset {
    // [...]

    std::vector<std::string>& all_unordered_m; // size = n >> 1
    std::vector<size_t> ordered_m;             // size << n
    std::tr1::unordered_map<size_t, size_t> position_m;  

    const std::string&
    string_after(size_t index, bool reverse) const
    {
        size_t pos = position_m.find(index)->second;
        if(reverse)
            pos = (pos == 0 ? orderd_m.size() - 1 : pos - 1);
        else
            pos = (pos == ordered.size() - 1 ? 0 : pos + 1);
        return all_unordered_m[ordered_m[pos]];
    }
};

鉴于:

• 我确实需要所有数据结构用于其他目的；
• 我无法更改它们，因为我需要访问字符串:
  • 通过他们在 all_unordered_m 中的 id；
  • 按它们在各种ordered_m里面的索引；
• 我需要知道一个字符串在 ordered_m vector 中的位置(由它在第一个 vector 中的位置标识)；
• 我无法在不更改大部分程序的情况下更改 string_after 接口(interface)。

如何加快被调用数十亿次并占用大约 10% 执行时间的 string_after 方法？

编辑: 我尝试将 position_m 设为 vector 而不是 unordered_map 并使用以下方法避免跳转:

string_after(size_t index, int direction) const
{
  return all_unordered_m[ordered_m[
      (ordered_m.size()+position_m[index]+direction)%ordered_m.size()]];
}

position_m 的更改似乎是最有效的(我不确定消除分支有什么不同，我很想说代码更紧凑但在这方面同样有效)。

Answer 1

vector 查找非常快。 size() 调用和简单的算术运算速度非常快。相比之下，map 查找就像背上有一 block 混凝土的死乌龟一样慢。我经常看到这些成为像这样的简单代码的瓶颈。

您可以尝试使用 TR1 或 C++0x 中的 unordered_map(map 的嵌入式哈希表替换)，看看是否会有所不同。