c# - 有效地存储数据以节省 ram 使用，而无需在 C# 中查找开销

Question

根据我的代理所处的位置及其旋转，我需要确定到墙的距离。由于此函数需要一点时间并且需要多次调用，我的想法是通过离散化位置 x 和 y 以及角度来存储距离。

因此，我的函数调用如下:

float GetWallDistance(int x, int y, int angle)
{
    return CalcWallDistance(x, y, angle);
}

其中x和y的范围是0到500，角度范围是0到360。我的第一个想法是将它存储在一个多维数组中，如下所示:

使用float[,,] saveArray = new float[500, 500, 360]; 在某处初始化数组

float GetWallDistance(int x, int y, int angle)
{

    float distance = 0;

    if(saveArray[x, y, angle] == 0)
    {
        distance = CalcWallDistance(x, y, angle);
        saveArray[x, y, angle] = distance;
    }
    else
    {
        distance = saveArray[x, y, angle];
    }

    return distance;

}

这极大地加快了计算时间，但这里的问题是 saveArray 占用了相当大的内存，代理很可能不会遍历整个 500 x 500 x 360 搜索空间。大量内存因此被白白占用。

因此，我使用字典来更高效地存储数据，如下所示:

使用Dictionary<double, float> saveDictionairy = new Dictionary<double, float>(); 在某处初始化字典

float GetWallDistance(int x, int y, int angle)
{
    double key = (double)x * 1000 + (double)y + (double)angle/1000
    float distance = 0;

    if(!saveDictionairy.TryGetValue(key, out distance))
    {
        distance = CalcWallDistance(x, y, angle);
        saveDictionairy.Add(key, distance);
    }

    return distance;
}

(我尝试使用字符串作为字典的键，但连接 x、y 和角度显然会占用相当长的时间)

这种方法确实更节省内存，但是对于索引多维数组而言，使用键项查找字典的时间增加了很多。

有谁知道如何以一种易于查找的方式有效地存储这些数据？

Answer 1

.NET Dictionary 使用快速算法，但开销仍然相当高。我刚才尝试让它更快。我发现通过删除不需要的内容和进行其他设计更改，可以使速度提高 6 倍。

例如，Dictionary 使用模运算符将哈希码映射到桶。 % 出奇的慢。我认为这需要 31 个 CPU 周期。当我用 hashCode & bucketCountMask 替换它时，其中桶计数是 2 的幂并且 bucketCountMask 是 buckets.Length - 1 我立即意识到巨大的性能提升。

我还删除了对删除项目和迭代器 version 功能的支持。我直接公开了 slots 数组，以便调用者可以直接改变其中的数据。

这种自定义类型要快得多，因为它更符合我的需求，而且它的 API 更难使用。

GitHub 上的 .NET 代码包含供其内部使用的 DictionarySlim 类型。也许你可以使用它。