读取二维矩阵的最快方法

Question

我正在使用嵌套字典来存储二维矩阵，该矩阵在启动时具有已知值，但我发现它读取速度太慢。有没有更快的？

更新

我不是在寻找我的代码是 "not working" 的任何原因。它工作正常 - 但我想知道任何让它更快的方法。下面的详细信息是为了提供上下文。

我还尝试使用自定义 class 作为键来展平嵌套字典，但速度更慢。

详情

我有一个包含 500 - 7,000 个对象的列表，我需要为每个可能的组合 (250,000 - 49,000,000) 存储一个值。

每个可能的组合都有一个默认值。该值将根据对象之间的依赖关系而变化，并且每个对象平均有 1 个依赖关系。对于每个依赖项，将有 1 - 100 个更新。平均每次更新将读取 5 次值。

因此，对于 1 个示例，我有 1,700 个对象，用于 2,890,000 种可能的组合，具有 1,900 个依赖项，这意味着 9,500 - 95,000 次读取。本例计算时间超过 90 秒！

这是初始化代码。我对这部分非常满意，因为它在不到一秒的时间内构建完成。

var allCombinations = new Dictionary<int, Dictionary<int, int>>();
foreach (var thisObject in allObjects)
{
    var comboFor1Object = new Dictionary<int, int>();
    foreach (var otherObject in allObjects)
    {
        comboFor1Object.Add(otherObject.Id, (thisObject.Id == otherObject.Id ? 0 : 100));
    }
    allCombinations.Add(thisObject.Id, comboFor1Object);
}

这是代码的简化更新部分 - 这是非常慢的部分。根据 Visual Studio Performance Profiler - 它特别是在第 9,10 和 11 行读取字典。该方法耗时75%，其中mscorlib.ni.dll占52.9%

foreach (var myObject in myDependency.Objects)
{
    foreach (var otherObject in myMatchingObjects)
    {
        if (myObject.Id == otherObject.Id)
        {
            continue;
        }
        var existingValue = allCombinations[myObject.Id][otherObject.Id];
        var minValue = allCombinations[myObject.Id][myDependency.FromObjectId] + allCombinations[myDependency.ToObjectId][otherObject.Id] + myDependency.MinValue;
        var maxValue = allCombinations[myObject.Id][myDependency.ToObjectId] + allCombinations[myDependency.FromObjectId][otherObject.Id] -myDependency.MaxValue;
        allCombinations[myObject.Id][otherObject.Id] = Math.Max(Math.Max(existingValue, minValue), maxValue);
    }
}

Answer 1

根据我对原始问题的评论，我将创建一个值类型（或者，如果您的 C#/.NET 版本支持 ValueTuple<int, int>，请使用它）：

struct IdById
{
    public int Id1, Id2;

    public IdById(int a, int b)
    {
        Id1 = a; Id2 = b;
    }
}

这样，您的初始化代码应如下所示：

var allCombinations = new Dictionary<IdById, int>();

foreach (var thisObj in allObjects)
{
    foreach (var otherObj in allObjects)
    {
        var ids = new IdById(thisObj.Id, otherObj.Id);
        allCombinations[ids] = (ids.Id1 == ids.Id2 ? 0 : 100);
    }
}

还有你的'stinky slow part'：

foreach (var myObj in myDependency.Objects)
{
    foreach (var otherObj in myMatchingObjects)
    {
        if (myObj.Id != otherObj.Id)
        {
            var ids = new IdById(myObj.Id, otherObj.Id);
            var existingValue = allCombinations[ids];
            var minValue =
                allCombinations[new IdById(myObj.Id, myDependency.FromObjectId)] +
                allCombinations[new IdById(myDependency.ToObjectId, otherObj.Id)] +
                myDependency.MinValue;
            var maxValue =
                allCombinations[new IdById(myObj.Id, myDependency.ToObjectId)] +
                allCombinations[new IdById(myDependency.FromObjectId, otherObj.Id)] -
                myDependency.MaxValue;
            allCombinations[ids] =
                Math.Max(Math.Max(existingValue, minValue), maxValue);
        }
    }
}

最终是否会更快，这是您必须测试的……

Answer 2

使用 dumetrulo 在评论中建议的二维数组比使用嵌套字典进行读取快两倍。不过，对任何事情都持开放态度！

for (int i = 0; i < allObjects.Count; i++)
{
    //new property to record the index in the array
    allObjects[i].Index = i;
}

var allCombinations = new int[allObjects.Count, allObjects.Count];
foreach (var thisObj in allObjects)
{
    foreach (var otherObj in allObjects)
    {
        allCombinations[thisObj.Index, otherObj.Index] = (thisObj.Id == otherObj.Id ? 0 : 100);
    }
}

这使得慢速代码像这样：

void DoUpdates(int[,] allCombinations)
{
    .
    .
    foreach (var myObject in myDependency.Objects)
    {
        foreach (var otherObject in myMatchingObjects)
        {
            .
            .
            var existingValue = allCombinations[myObject.Index, otherObject.Index];
            .
            .

读取二维矩阵的最快方法

Fastest way to read 2D matrix

c#

performance

profiling

dictionary

multidimensional-array

更新

详情