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

Question

我有一些数据结构:

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

该string_after(index, reverse)方法返回ordered_m引用的字符串之后 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向量内的字符串的位置(由它在第一个向量中的位置标识);
• 我无法在不更改大部分程序的情况下更改string_after接口.

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

编辑: 我试着做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相比之下，查找就像一只背上背着一块混凝土的死乌龟一样慢。我经常看到这些成为像这样的简单代码的瓶颈。

您可以尝试unordered_map使用 TR1 或 C++0x（ 的直接哈希表替换map），看看是否有区别。