c++ - 使用双键高效缓存整数

Question

我的代码从在不同范围之间具有不同精度的设备获取测量值。测量值以 double 的形式接收，我想将其转换为 int，它是我的内部数组的索引，它存储所有可能的值，它们之间没有间隙。

目前的代码是:

struct Range
{
    double  FirstVal;
    double  Precision;
}

class Measure
{
    std::vector<Range> mRangeList;   // Gets filled with ascending ranges
    int* mStartIdxAtRange = nullptr; // Gets filled with starting incides for each range

    int ValToIdx(double val) const
    {
        // Find the precision for the current range
        int rangeAffinity = static_cast<int>(mRangeList.size()) - 1;
        for (int i = rangeAffinity - 1; i >= 0; i--)
        {
            if (val< mRangeList[i+ 1].FirstVal)
            {
                rangeAffinity = i;
            }
            else
            {
                break;
            }
        }

        double howMuchBigger = val- mRangeList[rangeAffinity].FirstVal;
        int retIdx = mStartIdxAtRange[rangeAffinity] + howMuchBigger / mRangeList[rangeAffinity].Precision + 0.5;
        return retIdx;
    }
}

问题是 ValToIdx 被调用了很多次，并且是分析后最昂贵的函数。我想缓存这些值，所以我尝试了这个:

mutable std::unordered_map<double, int> Measure::mValToIdxCache;

int Measure::ValToIdx(double val) const
{
    auto it = mValToIdxCache.find(val);
    if (it != mValToIdxCache.end())
    {
        return it->second;
    }

    // Find the precision for the current range
    int rangeAffinity = static_cast<int>(mRangeList.size()) - 1;
    for (int i = rangeAffinity - 1; i >= 0; i--)
    {
        if (val< mRangeList[i+ 1].FirstVal)
        {
            rangeAffinity = i;
        }
        else
        {
            break;
        }
    }

    double howMuchBigger = val- mRangeList[rangeAffinity].FirstVal;
    int retIdx = mStartIdxAtRange[rangeAffinity] + howMuchBigger / mRangeList[rangeAffinity].Precision + 0.5;
    mValToIdxCache[val] = retIdx;
    return retIdx;
}

但是，这会使函数慢 3 倍。我如何缓存每个值的索引，以便访问缓存比从头开始计算更快？ 对于软件的任何给定运行，可以假设测量值将在 vector 中约 10 个可用范围中的 1 到 3 个范围内。

Answer 1

你能加上“int startIdx;”吗？到 Range 结构并从 Measure 中删除 mStartIndexAtRange？我怀疑这会提高缓存性能。

此外，您能否将 1.0/Precision 存储在 Range 而不是 Precision 中。这样你就可以使用乘法而不是除法，例如:

int retIdx = mStartIdxAtRange[rangeAffinity] + howMuchBigger *
                mRangeList[rangeAffinity].ReciprocalPrecision + 0.5;