mardi 21 avril 2015

Scala functional algorithm perfomance

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?

Please help

For people trying to understand the problem better here's the assignment http://ift.tt/1J2Twoy

Aucun commentaire:

Enregistrer un commentaire