2

当我尝试分析一个缓慢的优化算法时，我发现以下方法花费的时间比预期的要长得多：

protected virtual bool Dominates(ILInArray<double> p1, ILInArray<double> p2, int nObjectives)
{
    using (ILScope.Enter(p1, p2))
    {
        ILArray<double> p1In = p1;
        ILArray<double> p2In = p2;
        bool strong = false;
        for (int i = 0; i < nObjectives; i++)
        {
            using (ILScope.Enter())
            {
                if (p1In[i] > p2In[i])
                    strong = true;
                else if (p1In[i] < p2In[i])
                {
                    return false;
                }
            }
        }
        return strong;
    }
}

然后我用下面的实现替换了它，速度增加了很多倍。

protected virtual bool DominatesSys(double[] p1, double[] p2, int nObjectives)
{
    bool strong = false;
    for (int i = 0; i < nObjectives; i++)
    {
        if (p1[i] > p2[i])
            strong = true;
        else if (p1[i] < p2[i])
        {
            return false;
        }
    }
    return strong;
}

我不明白它并试图编写一个测试来比较差异。下面是使用的测试代码：

[Test]
public void TestILNumericsSpeed()
{
    ILArray<double> p1Il = ILMath.rand(100);
    ILArray<double> p2Il = p1Il - 0.01;
    double[] p1 = p1Il.GetArrayForRead();
    double[] p2 = p2Il.GetArrayForRead();
    int length = p1.Length;
    Func<bool> func1 = () =>
        {
            Dominates(p1Il, p2Il, length);
            return true;
        };
    Func<bool> func2 = () =>
        {
            DominatesSys(p1, p2, length);
            return true;
        };
    var stats1 = CollectStats(func1, 20, 1000);
    var stats2 = CollectStats(func2, 20, 1000);
    log.InfoFormat("Mean time taken by ILNumerics = {0}.", stats1.Skip(1).Average(t => t.TotalSeconds));
    log.InfoFormat("Mean time taken by system array = {0}.", stats2.Skip(1).Average(t => t.TotalSeconds));
}

protected virtual IList<TimeSpan> CollectStats(Func<bool> func, int n = 100, int nPerRound = 100)
{
    Stopwatch watch = new Stopwatch();
    var stats1 = new List<TimeSpan>();
    watch.Reset();
    for (int i = 0; i < n; i++)
    {
        using (ILScope.Enter())
        {
            watch.Reset();
            watch.Start();
            for (int j = 0; j < nPerRound; j++)
            {
                bool ret = func();
                Assert.IsTrue(ret);
            }
            watch.Stop();
            stats1.Add(watch.Elapsed);
        }
    }
    return stats1;
}

我对得到的奇怪结果感到非常震惊。我希望 ILArray 在顺序索引方面比系统数组慢一点，但是 1000 次太多了。有人可以在这里帮助诊断我的问题：

[INFO ] | 14:38:19,974 | [odes] |         NumericsTest   383 | Mean time taken by ILNumerics = 0.294103963157895.
[INFO ] | 14:38:20,036 | [odes] |         NumericsTest   383 | Mean time taken by system array = 0.000271984210526316.

按照 Haymo 的建议，运行以下测试来比较不同实现的速度。我认为在这种情况下，由于不需要使用 DominatesSys 创建中间数组，因此它的性能是最快的。

[Test]
public void TestILNumericsSpeed()
{
    ILArray<double> p1Il = ILMath.rand(1000);
    ILArray<double> p2Il = p1Il - 0.01;
    double[] p1 = p1Il.GetArrayForRead();
    double[] p2 = p2Il.GetArrayForRead();
    int length = p1Il.S[0];
    Func<bool> func1 = () =>
        {
            Dominates1(p1Il, p2Il, length);
            return true;
        };
    Func<bool> func2 = () =>
        {
            Dominates2(p1Il, p2Il, length);
            return true;
        };
    Func<bool> func3 = () =>
        {
            Dominates3(p1Il, p2Il, length);
            return true;
        };
    Func<bool> func4 = () =>
    {
        Dominates4(p1Il, p2Il, length);
        return true;
    };
    Func<bool> func5 = () =>
    {
        Dominates5(p1Il, p2Il, length);
        return true;
    };
    Func<bool> funcSys = () =>
        {
            DominatesSys(p1, p2, length);
            return true;
        };
    var stats1 = IO.CollectStats(func1, 10, 1000);
    var stats2 = IO.CollectStats(func2, 10, 1000);
    var stats3 = IO.CollectStats(func3, 10, 1000);
    var stats4 = IO.CollectStats(func4, 10, 1000);
    var stats5 = IO.CollectStats(func5, 10, 1000);
    var statsSys = IO.CollectStats(funcSys, 10, 1000);
    log.InfoFormat("Mean time taken by Dominates1 = {0}.", stats1.Skip(1).Average(t => t.TotalSeconds));
    log.InfoFormat("Mean time taken by Dominates2 = {0}.", stats2.Skip(1).Average(t => t.TotalSeconds));
    log.InfoFormat("Mean time taken by Dominates3 = {0}.", stats3.Skip(1).Average(t => t.TotalSeconds));
    log.InfoFormat("Mean time taken by Dominates4 = {0}.", stats4.Skip(1).Average(t => t.TotalSeconds));
    log.InfoFormat("Mean time taken by Dominates5 = {0}.", stats5.Skip(1).Average(t => t.TotalSeconds));
    log.InfoFormat("Mean time taken by system array = {0}.", statsSys.Skip(1).Average(t => t.TotalSeconds));
}

protected virtual bool Dominates1(ILInArray<double> p1, ILInArray<double> p2, int nObjectives)
{
    using (ILScope.Enter(p1, p2))
    {
        ILArray<double> p1In = p1;
        ILArray<double> p2In = p2;
        bool strong = false;
        for (int i = 0; i < nObjectives; i++)
        {
            using (ILScope.Enter())
            {
                if (p1In[i] > p2In[i])
                    strong = true;
                else if (p1In[i] < p2In[i])
                {
                    return false;
                }
            }
        }
        return strong;
    }
}

protected virtual bool Dominates2(ILInArray<double> p1, ILInArray<double> p2, int nObjectives)
{
    using (ILScope.Enter(p1, p2))
    {
        ILArray<double> n = p1[r(0, nObjectives - 1)] - p2[r(0, nObjectives - 1)];
        if (any(n < 0)) return false;
        return any(n > 0);
    }
}

protected virtual bool Dominates3(ILInArray<double> p1, ILInArray<double> p2, int nObjectives)
{
    using (ILScope.Enter(p1, p2))
    {
        ILArray<double> n = p1[r(0, nObjectives - 1)] - p2[r(0, nObjectives - 1)];
        var strong = false;
        foreach (var d in n)
        {
            if (d < 0) return false;
            if (d > 0) strong = true;
        }
        return strong;
    }
}

protected virtual bool Dominates4(ILInArray<double> p1, ILInArray<double> p2, int nObjectives)
{
    using (ILScope.Enter(p1, p2))
    {
        ILArray<double> p1In = p1;
        ILArray<double> p2In = p2;
        bool strong = false;
        for (int i = 0; i < nObjectives; i++)
        {
            using (ILScope.Enter()) {  // probably does not help with such tiny arrays ...
                if (p1In.GetValue(i) > p2In.GetValue(i))
                    strong = true;
                else if (p1In.GetValue(i) < p2In.GetValue(i))
                {
                    return false;
                }
            }
        }
        return strong;
    }
}

protected virtual bool Dominates5(ILArray<double> p1, ILArray<double> p2, int nObjectives)
{
    bool strong = false;
    for (int i = 0; i < nObjectives; i++)
    {
        if (p1.GetValue(i) > p2.GetValue(i))
            strong = true;
        else if (p1.GetValue(i) < p2.GetValue(i))
            return false;
    }
    return strong;
} 


protected virtual bool DominatesSys(double[] p1, double[] p2, int nObjectives)
{
    bool strong = false;
    for (int i = 0; i < nObjectives; i++)
    {
        if (p1[i] > p2[i])
            strong = true;
        else if (p1[i] < p2[i])
        {
            return false;
        }
    }
    return strong;
}

结果如下：

[INFO ] | 12:55:01,911 | [odes] |         NumericsTest   379 | Mean time taken by Dominates1 = 2.85064264444444.
[INFO ] | 12:55:01,976 | [odes] |         NumericsTest   380 | Mean time taken by Dominates2 = 0.0402656666666667.
[INFO ] | 12:55:01,977 | [odes] |         NumericsTest   381 | Mean time taken by Dominates3 = 0.173880833333333.
[INFO ] | 12:55:01,978 | [odes] |         NumericsTest   382 | Mean time taken by Dominates4 = 0.148000711111111.
[INFO ] | 12:55:01,979 | [odes] |         NumericsTest   383 | Mean time taken by Dominates5 = 0.0593142444444444.
[INFO ] | 12:55:01,980 | [odes] |         NumericsTest   383 | Mean time taken by system array = 0.00180445555555556.
4

1 回答 1

1

你的时间太小了。也可能是您的问题大小。增加两者（迭代次数，问题大小）以获得更可靠的结果。此外，不要忘记从测量中排除第一次迭代（因为 JIT 编译的开销要大得多）。

我怀疑，1000 的因子是否可靠。但总的来说，很明显，以您所做的方式迭代 ILArray 不能带来与迭代 double[] 相同的性能。ILNumerics 的工作方式（你应该适应）是矢量化。以整个数组而不是单个元素参与计算的方式重写您的算法。

如果这是不可能的，那么为这样的微内核突破 ILArray 并没有错。您使用 (GetArrayForRead(), GetArrayForWrite()) 的方式很好，以便访问底层系统数组并将其用于此类元素计算。

您可以尝试的另一种方法如下：

protected virtual bool Dominates(ILInArray<double> p1, ILInArray<double> p2, int nObjectives) {
    using (ILScope.Enter(p1, p2)) {
        ILArray<double> p1In = p1;
        ILArray<double> p2In = p2;
        bool strong = false;
        for (int i = 0; i < nObjectives; i++) {
            //using (ILScope.Enter()) {  // probably does not help with such tiny arrays ...
                if (p1In.GetValue(i) > p2In.GetValue(i))
                    strong = true;
                else if (p1In.GetValue(i) < p2In.GetValue(i)) {
                    return false;
                }
            //}
        }
        return strong;
    }
}

但更有希望的是，IMO 会是这样的：（期望代码在从 ILMath 派生的类的上下文中，所以 ILMath. 被省略）

protected virtual bool Dominates(ILInArray<double> p1, ILInArray<double> p2, int nObjectives) {
    using (ILScope.Enter(p1, p2)) {
        ILArray<double> n = p1 - p2;
        if (any(n < 0)) return false;
        return any(n > 0); 
    }
}

请再次测量并让我们知道您的结果！谢谢

@Edit：再想一想，还有另一种选择：

protected virtual bool Dominates(ILInArray<double> p1, ILInArray<double> p2, int nObjectives) {
    using (ILScope.Enter(p1, p2)) {
        ILArray<double> n = p1 - p2;
        var strong = false; 
        foreach (var d in n) {
            if (d < 0) return false;
            if (d > 0) strong = true; 
        }
        return strong; 
    }
}

如果p1.Length != p2.Length，您可以p1 - p2相应地调整...

于 2014-01-08T17:28:30.983 回答