代码之家 › 专栏 › 技术社区 › JumpingJezza

读取2D矩阵的最快方法

profiling multidimensional-array dictionary performance c#

-1

JumpingJezza · 技术社区 · 8 年前

我使用嵌套字典来存储2D矩阵,该矩阵在初始化时具有已知值,我发现它太慢,无法读取。还有更快的吗?

使现代化

我不想寻找我的代码“不工作”的任何原因。它工作正常-但我想知道任何方法,使它更快。下面的细节是为了提供上下文。

细节

我有一个500-7000个对象的列表,我需要为每个可能的组合(250000-49000000)存储一个值。

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

例如,我有1700个对象,用于2890000个可能的组合,有1900个依赖项,这意味着9500-95000次读取。这个例子需要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行,它读取字典。这种方法花费了mscorlib的75%时间。镍。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);
    }
}

2 回复 | 直到 8 年前

dumetrulo 8 年前

根据我对原始问题的评论,我将创建一个值类型(或者,如果您的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);
    }
}

还有你的“臭慢部分”:

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);
        }
    }
}

这最终是否会更快,这是你必须测试的

JumpingJezza 8 年前

按照建议使用2D阵列 杜米特鲁洛 在注释中,读取的速度是使用嵌套字典的两倍。但对任何更快的想法都持开放态度!

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];
            .
            .