Functional programming

Question

I recently started using Scala to solve some Codeforces programming problems to realize functional programming skills. Thus, I was faced with one specific problem that I could not solve, observing a given execution time of 1000 ms; problem Working with a picture .

I tried various methods, starting with a direct recursive solution, using a similar approach, using streams instead of lists, and ended up trying to reduce list manipulation by working a bit with indexes. I ran out of exceptions in larger tests that I was able to fix with ScalaTailCall.. But still, although the solution solves the problem correctly, it completes too slowly within 1000 ms. In addition to this, a C ++ implementation is shown, which is ridiculously fast compared (<50ms). Now I understand that in many cases Scala will be slower compared to C ++, and I also understand that I could write a more rigorous solution in Scala, which would probably work much better. However, I am wondering if something more fundamental is lacking here, because I find it hard to believe that functional programming is much slower in this regard (and I'm quite new to functional programming).

Here is my Scala code that you can embed in a REPL, including an example that takes> 1000 ms:

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)

, ++ , 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.