2

我希望找到一种方法来用扩展函数的函数式编写下面的代码。理想情况下，与迭代/循环版本相比，这种功能风格会表现良好。我猜没有办法。可能是因为许多额外的函数调用和堆栈分配等。

从根本上说，我认为让它变得麻烦的模式是它既计算一个用于 Predicate 的值，然后又需要该计算值作为结果集合的一部分。

// This is what is passed to each function.
// Do not assume the array is in order.
var a = (0).To(999999).ToArray().Shuffle();

// Approx times in release mode (on my machine):
// Functional is avg 20ms per call
// Iterative is avg 5ms per call
// Linq is avg 14ms per call

private static List<int> Iterative(int[] a)
{
    var squares = new List<int>(a.Length);

    for (int i = 0; i < a.Length; i++)
    {
        var n = a[i];

        if (n % 2 == 0)
        {
            int square = n * n;

            if (square < 1000000)
            {
                squares.Add(square);
            }
        }
    }

    return squares;
}

private static List<int> Functional(int[] a)
{
    return
    a
        .Where(x => x % 2 == 0 && x * x < 1000000)
        .Select(x => x * x)
        .ToList();
}

private static List<int> Linq(int[] a)
{
    var squares =
        from num in a
        where num % 2 == 0 && num * num < 1000000
        select num * num;

    return squares.ToList();
}
4

4 回答 4

7

康拉德建议的替代方案。这避免了双重计算，但也避免了在不需要时甚至计算平方：

return a.Where(x => x % 2 == 0)
        .Select(x => x * x)
        .Where(square => square < 1000000)
        .ToList();

就个人而言，在我看到它在更大范围内的显着性之前，我不会担心性能差异。

（顺便说一下，我假设这只是一个例子。通常你可能会计算一次 1000000 的平方根，然后n与它进行比较，以减少几毫秒。它确实需要两次比较或一次Abs操作不过，当然。）

编辑：请注意，功能更强大的版本将完全避免使用ToList。而是返回IEnumerable<int>，并让调用者将其转换为 aList<T> 如果他们愿意。如果他们不这样做，他们就不会受到打击。如果他们只想要前 5 个值，他们可以调用Take(5). 取决于上下文，这种懒惰可能是对原始版本的巨大性能胜利。

于 2012-06-21T16:32:32.093 回答
2

只是解决你的双重计算问题：

return (from x in a
        let sq = x * x
        where x % 2 == 0 && sq < 1000000
        select sq).ToList();

也就是说，我不确定这是否会导致性能大幅提升。功能变体实际上是否比迭代变体快得多？该代码为自动优化提供了很大的潜力。

于 2012-06-21T16:31:11.573 回答
1

一些并行处理怎么样？或者解决方案是否必须是 LINQ（我认为它很慢）。

var squares = new List<int>(a.Length);

Parallel.ForEach(a, n =>
{
  if(n < 1000 && n % 2 == 0) squares.Add(n * n);             
}

Linq 版本将是：

return a.AsParallel()
  .Where(n => n < 1000 && n % 2 == 0)  
  .Select(n => n * n)
  .ToList();
于 2012-06-21T16:51:00.193 回答
0

我不认为有一个功能性解决方案可以与迭代解决方案在性能方面完全相提并论。在我的时间安排中（见下文），来自 OP 的“功能”实现似乎比迭代实现慢两倍左右。

像这样的微基准很容易出现各种问题。处理可变性问题的常用策略是重复调用正在计时的方法并计算每次调用的平均时间 - 如下所示：

// from main
Time(Functional, "Functional", a);    
Time(Linq, "Linq", a);    
Time(Iterative, "Iterative", a);
// ...

static int reps = 1000;
private static List<int> Time(Func<int[],List<int>> func, string name, int[] a)
{
    var sw = System.Diagnostics.Stopwatch.StartNew();
    List<int> ret = null;
    for(int i = 0; i < reps; ++i)
    {
        ret = func(a);
    }
    sw.Stop();
    Console.WriteLine(
        "{0} per call timings - {1} ticks, {2} ms",
        name,
        sw.ElapsedTicks/(double)reps,
        sw.ElapsedMilliseconds/(double)reps);
    return ret;
}

以下是一次会议的时间安排：

每次通话时间的功能 - 46493.541 滴答，16.945 毫秒
Linq 每次调用时间 - 46526.734 滴答声，16.958 毫秒
每次调用时间迭代 - 21971.274 滴答，8.008 毫秒

还有许多其他挑战：定时器使用的频闪效应，即时编译器如何以及何时执行其操作，垃圾收集器运行其收集，竞争算法的运行顺序，类型cpu，操作系统交换其他进程进出等。

我尝试了一些优化。我从测试中删除了平方 (num * num < 1000000) - 将其更改为 (num < 1000) - 这似乎很安全，因为输入中没有负数 - 也就是说，我取了不等式两边的平方根. 令人惊讶的是，与 OP 中的方法相比，我得到了不同的结果——我的优化输出中只有 500 个项目，而 OP 实现中的三个实现有 241,849 个项目。那么为什么会有差异呢？当平方溢出时，大部分输入都溢出了 32 位整数，所以那些额外的 241,349 项来自在平方溢出到负数或小于 100 万的数字时仍然通过我们的均匀性测试的数字。

优化（功能）时序：

每次通话时间优化 - 16849.529 滴答声，6.141 毫秒

这是按照建议更改的功能实现之一。它按预期输出通过标准的 500 个项目。它看似“更快”只是因为它输出的项目比迭代解决方案少。

我们可以通过在其实现周围添加一个检查块来使原始实现因溢出异常而崩溃。这是添加到“迭代”方法中的选中块：

private static List<int> Iterative(int[] a)
{
    checked
    {
        var squares = new List<int>(a.Length);

        // rest of method omitted for brevity...

        return squares;
    }
}
于 2012-08-25T16:27:27.913 回答