scala - 函数式编程性能

Question

我最近开始使用 Scala 来解决一些编程挑战 Codeforces以锻炼函数式编程技能。这样做时，我遇到了一个特殊的挑战，我无法按照给定的 1000 毫秒的执行时间限制来解决； Painting Fence问题。

我尝试了各种不同的方法，从直接的递归解决方案开始，尝试使用流而不是列表的类似方法，最后尝试通过更多地使用索引来减少列表操作。我最终在较大的测试中遇到了堆栈溢出异常，我可以使用 Scala 的 TailCall 来修复这些异常。 但是，尽管该解决方案正确地解决了问题，但在 1000 毫秒内完成还是太慢了。除此之外，还有一个 C++ 实现，相比之下速度快得离谱(< 50 毫秒)。现在我确实明白，在很多情况下，Scala 会比 C++ 慢，而且我也明白，我可以在 Scala 中编写一个更具命令式风格的解决方案，它的性能可能会好得多。不过，我想知道我是否在这里遗漏了一些更基本的东西，因为我很难相信函数式编程一般来说要慢得多(而且我对函数式编程还很陌生)。

这是我的 scala 代码，您可以将其粘贴到 REPL 中，包括需要 >1000ms 的示例:

import scala.util.control.TailCalls._

def solve(l: List[(Int, Int)]): Int = {

  def go(from: Int, to: Int, prevHeight: Int): TailRec[Int] = {
    val max = to - from
    val currHeight = l.slice(from, to).minBy(_._1)._1
    val hStrokes = currHeight - prevHeight
    val splits = l.slice(from, to).filter(_._1 - currHeight == 0).map(_._2)
    val indices = from :: splits.flatMap(x => List(x, x+1)) ::: List(to)
    val subLists = indices.grouped(2).filter(xs => xs.last - xs.head > 0)

    val trampolines = subLists.map(xs => tailcall(go(xs.head, xs.last, currHeight)))
    val sumTrampolines = trampolines.foldLeft(done(hStrokes))((b, a) => b.flatMap(bVal =>
      a.map(aVal => aVal + bVal)))
    sumTrampolines.flatMap(v => done(max).map(m => Math.min(m, v)))
  }
  go(0, l.size, 0).result
}

val lst = (1 to 5000).toList.zipWithIndex
val res = solve(lst)

为了进行比较，这里有一个 C++ 示例，实现了由 Bugman 编写的相同功能(包括一些我在上面的 Scala 版本中未包含的控制台读/写操作):

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cmath>
#include <memory.h>
using namespace std;
typedef long long ll;

const int N = 1e6+6;
const int T = 1e6+6;

int a[N];
int t[T], d;

int rmq(int i, int j){
    int r = i;
    for(i+=d,j+=d; i<=j; ++i>>=1,--j>>=1){
        if(i&1) r=a[r]>a[t[i]]?t[i]:r;
        if(~j&1) r=a[r]>a[t[j]]?t[j]:r;
    }
    return r;
}

int calc(int l, int r, int h){
    if(l>r) return 0;

    int m = rmq(l,r);
    int mn = a[m];
    int res = min(r-l+1, calc(l,m-1,mn)+calc(m+1,r,mn)+mn-h);
    return res;
}

int main(){
    //freopen("input.txt","r",stdin);// freopen("output.txt","w",stdout);

    int n, m;

    scanf("%d",&n);
    for(int i=0;i<n;++i) scanf("%d",&a[i]);

    a[n] = 2e9;
    for(d=1;d<n;d<<=1);
    for(int i=0;i<n;++i) t[i+d]=i;
    for(int i=n+d;i<d+d;++i) t[i]=n;
    for(int i=d-1;i;--i) t[i]=a[t[i*2]]<a[t[i*2+1]]?t[i*2]:t[i*2+1];

    printf("%d\n",calc(0,n-1,0));

    return 0;
}

至少在我引入显式尾部调用之前，对我来说，更函数式的风格似乎比更命令式的解决方案更自然地解决问题。因此，我非常乐意了解更多关于在编写函数代码时应该注意什么，以便仍然获得可接受的性能。

Answer 1

如此严重地依赖索引可以说并不是真正惯用的函数式风格，而将索引和列表相结合会导致性能不太理想。

这是一个无索引的实现:

import scala.util.control.TailCalls._

def solve(xs: Vector[Int]): Int = {
  def go(xs: Vector[Int], previous: Int): TailRec[Int] = {
    val min = xs.min

    splitOn(xs, min).foldLeft(done(min - previous)) {
      case (acc, part) => for {
        total <- acc
        cost  <- go(part, min)
      } yield total + cost
    }.map(math.min(xs.size, _))
  }

  go(xs, 0).result
}

不过，这并不是故事的全部 - 我已将拆分部分分解为一个名为 splitOn 的方法，该方法采用序列和分隔符。因为这是一个非常简单且通用的操作，所以它是优化的良好候选者。以下是一个快速尝试:

def splitOn[A](xs: Vector[A], delim: A): Vector[Vector[A]] = {
  val builder = Vector.newBuilder[Vector[A]]
  var i = 0
  var start = 0

  while (i < xs.size) {
    if (xs(i) == delim) {
      if (i != start) {
        builder += xs.slice(start, i)
      }
      start = i + 1
    }
    i += 1
  }

  if (i != start) builder += xs.slice(start, i)

  builder.result
}

虽然此实现是命令式的，但从外部来看，该方法功能完美 - 它没有副作用等。

这通常是提高功能代码性能的好方法:我们将程序分为通用部分(在分隔符上拆分列表)和特定于问题的逻辑。因为前者非常简单，所以我们可以要求将其视为(并测试)黑匣子，同时保持我们用来解决问题的代码干净且功能齐全。

在这种情况下，性能仍然不是很好 - 这个实现大约是我机器上的两倍 - 但我认为使用 TailCalls 进行蹦床时不会有更好的结果.