Scala functional algorithm performance

Question

I've been solving this year Code Jam task with Dijkstra. Long story short. You have to find right 3 subsets of set of chars out of X element set of chars.

I implemented my algorithm in Scala. But it didn't meet the requirements. It run for more than 10 minutes and therefore it made me lose the assignment.

class Dijkstra extends CodeJamProblem{    
  override def run(input: List[String]): String = {

    val params :: letters :: Nil = input
    val l :: x :: Nil = params.split(" ").toList.map{_.toInt}
    val inputString = (1 to x).map{_ => letters}.reduce(_ + _).toCharArray.toList

    val rests = for(
      iRests <- check(inputString, 'i);
      jRests <- check(iRests, 'j);
      kRests <- check(jRests, 'k)
      if kRests.length == 0)
      yield true

    if(rests.length > 0) "YES" else "NO"
    "NO"
  }
  @tailrec
  final def check(input: List[Char], equalTo: Symbol, lq: Quaternion = ('l, false), r: List[List[Char]] = List()) : List[List[Char]] = {
    if(input.isEmpty) r
    else {
      val rest = input.tail
      val newq = lq * Quaternion(Symbol(input.head.toString), false)
      if (newq.symbol == equalTo && !newq.negative){
        check(rest, equalTo, newq, rest :: r)
      } else {
        check(rest, equalTo, newq, r)
      }
    }
  }
  override val linesPerInput: Int = 2
}

case class Quaternion(symbol: Symbol, negative: Boolean){
  def *(that: Quaternion) = {
    val negative = this.negative ^ that.negative
    val (symbol, negate) = (this.symbol, that.symbol) match {
      case ('l, a) => (a, false)
      case (a, 'l) => (a, false)
      case (a, b) if a == b => ('l, true)

      case ('i,'j) => ('k, false)
      case ('j,'k) => ('i, false)
      case ('k,'i) => ('j, false)

      case ('j,'i) => ('k, true)
      case ('k,'j) => ('i, true)
      case ('i,'k) => ('j, true)

    }
    Quaternion(symbol, negate ^ negative)
  }
}

I thought it's just about the algorithm itself. However then I implemented the same algorithm in Erlang and it ran in less than a second.

main(String) ->
  AtomList = [{list_to_atom([X]), false} || X <- String],
  Result = [ true ||    RestI <- find_rests(AtomList, {i, false}),
                        RestJ <- find_rests(RestI, {j, false}),
                        RestK <- find_rests(RestJ, {k, false}),
                        RestK == []
              ],
  case Result of
    [true | _] -> "YES";
    _ -> "NO"
  end.

find_rests(I, S) -> find_rests(I, S, {1, false}, []).
find_rests([], _, _, Rests) -> Rests;
find_rests(Input, Symbol, LastQ, Rests) ->
  [H | Rest] = Input,
  case mulpily(LastQ, H) of
    Symbol   -> find_rests(Rest, Symbol, Symbol, [Rest | Rests]);
    Q        -> find_rests(Rest, Symbol, Q, Rests)
  end.



multiply({Sym,Sign}, {Sym2, Sign2}) ->
  {S, N} = mul(Sym, Sym2),
  {S, Sign xor Sign2 xor N}.

mul(S, 1) ->
  {S, false};
mul(1, S) ->
  {S, false};
mul(S, S) ->
  {1, true};
mul(i,j) ->
  {k, false};
mul(j,k) ->
  {i, false};
mul(k,i) ->
  {j, false};
mul(j,i) ->
  {k, true};
mul(k,j) ->
  {i, true};
mul(i,k) ->
  {j, true}.

So there is my question. What makes Scala run so much slower. My guess is it's some object copying that I can't see. But if that's the case why does scala copy immutable structures?

For people trying to understand the problem better here's the assignment https://code.google.com/codejam/contest/6224486/dashboard#s=p2

Are you sure the two implementations perform the same computation? (It would be a lot easier to compare the two if you'd chosen more similar identifiers!) — The Archetypal Paul
– The Archetypal Paul, Commented Apr 15, 2015 at 16:11
In the recursive call in check, you pass rest as the first argument, which is input.tail where input is the first parameter to this call of check. In the Erlang version you pass Rests, which is the last parameter (which would be r, in the Scala version). If the Erlang was to do the same as the scala, it would pass Rest not Rests — The Archetypal Paul
– The Archetypal Paul, Commented Apr 15, 2015 at 16:16
@Paul it's based on the exact same idea 1. Converting to string to list. 2. Getting all rests of lists that reduce to "i" 3. Getting all rests of lists for each rest of list that reduce to "j". 4. Getting lists reducing to "k" for each rest of each rest of list. 5. Displaying these results of 4 that don't have any rest (use full string for algorithm) — Krzysztof Wende
– Krzysztof Wende, Commented Apr 15, 2015 at 16:18
Yes, I know it's the same idea. My supposition is that in fact it isn't implementing the same algorithm, but determining that is made unnecessarily more difficult because the identifiers are different so you need to keep a mental map of what one identifier means in the other implementation — The Archetypal Paul
– The Archetypal Paul, Commented Apr 15, 2015 at 16:20
And as you can see from my earlier comment above, I think the two do implement something different. And (to bang on about it) it would have been obvious had you used the same identifier names — The Archetypal Paul
– The Archetypal Paul, Commented Apr 15, 2015 at 16:29

Others · Accepted Answer · 2015-07-16 03:40:42Z

In actual fact, I doubt timing is your issue here. There are multiple issues I ran into while investigating your code.

1) If you look at your main method:

override def run(input: List[String]): String = {
    val params :: letters :: Nil = input
    val l :: x :: Nil = params.split(" ").toList.map{_.toInt}
    val inputString = (1 to x).map{_ => letters}.reduce(_ + _).toCharArray.toList

    val rests = for(
      iRests <- check(inputString, 'i);
      jRests <- check(iRests, 'j);
      kRests <- check(jRests, 'k)
      if kRests.length == 0)
      yield true

    if(rests.length > 0) "YES" else "NO"
    "NO"
  }

Your last line is "NO". This means instead of returning "No" unless rests.length > 0, you are always returning "No". (You can fix this by simply deleting the last "NO")

2) I ran some test data found on the page you linked, namely "C-large-practice". It fails on the very first input with a number format exception. This is because one of the parameter numbers is "209152663278", which is larger than Int.MaxValue. To fix this is a more complicated endeavor.

2a) Firstly, I changed this line:

val l :: x :: Nil = params.split(" ").toList.map{_.toInt}

By changing the toInt to toLong.

val l :: x :: Nil = params.split(" ").toList.map{_.toLong}

2b) Also, we have to change part of the next line to handle long ranges, by changing this:

val inputString = (1 to x).map{_ => letters}.reduce(_ + _).toCharArray.toList

By adding an L after 1 to make it a long literal.

val inputString = (1L to x).map{_ => letters}.reduce(_ + _).toCharArray.toList

3) Even after these two changes, there is a slight issue. Still on our first test case, we have an error on this line:

val inputString = (1L to x).map{_ => letters}.reduce(_ + _).toCharArray.toList

Saying that it cannot map because there are More than Int.MaxValue elements. The way I whipped up to fix this was:

val inputLetters:mutable.ListBuffer[Char]=mutable.ListBuffer()
var count=0L
while(count < x){
    inputLetters++=letters.toCharArray()
    count+=1
    println("X is" + x + "count is" + count)
}
val inputString=inputLetters.toList
inputLetters.clear()

But this becomes a performance bottleneck, since it has to allocate a massive amount of memory. This might indicate where the slowdown in your program is. I'd recommend doing more testing and optimization with the datasets provided on the site you linked, if you want to improve the speed of your Scala version.

I don't have quite enough Erlang experience to debug your Erlang work, but I'd recommend testing the entire dataset provided before assuming it gives correct results at such a speed.

Collectives™ on Stack Overflow

Scala functional algorithm performance

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related