Exo Optimisation Scala

Readme.md

Optimisation Performance Scala

Tiré d'Advent of Code 2020 : https://adventofcode.com/2020/day/15

Enoncé: Suite de Van Eck

Chacun son tour, les joueurs disent un nombre. Ils commencent par une liste prédéfinie (input). Puis les règles suivantes s'appliquent:
en considérant le nombre qui vient d'être cité, si c'est la première fois que le nombre a été cité, le joueur dit 0, sinon le joueur annonce il y a combien de tours que le nombre a été cité pour la dernière fois.

Autrement dit, après la liste initiale, chaque tour consiste en un joueur qui dit 0 si le nombre précédent était nouveau ou un âge (si le nombre précédent avait déjà été cité)

Example

Input: 0, 3, 6 Puis :

• Tour 4 : 0 (car 6 était nouveau)
• Tour 5 : 3 (car 0 avait été dit au tour 1, donc son âge était 4-1 = 3)
• Tour 6 : 3 (car 3 avait été dit au tour 2, donc son âge était 5-2 = 3)
• Tour 7 : 1 (car 3 avait été dit au tour 5, donc son âge était 6-5 = 1)
• Tour 8 : 0 (car 1 était nouveau)
• Tour 9 : 4 (car 0 avait été dit au tour 4, donc son âge était 8-4 = 4)
• Tour 10 : 0 (car 4 était nouveau)

Exercice

Le code attendu doit donner pour l'input (0, 3, 6) le 2020e élément : 436.
Or pour le calcul du 2020e élément, on met environ 180ms.
Cela pose problème si on veut calculer le 30 000 000e élément qui doit être 175594.
Comment optimiser le code ?

Indices : https://docs.scala-lang.org/overviews/collections/overview.html https://www.lihaoyi.com/post/BenchmarkingScalaCollections.html

VanEck.scala

package exo

object VanEck {

  /**
   * 2020 : 185ms
   */
  def generate(init: List[Int], n: Int): List[Int] = {

    val firstMap = init.zipWithIndex
      .map { case (x, i) => (x, List(i)) }
      .toMap

    def compute(res:(List[Int],Map[Int, List[Int]]),i: Int): (List[Int], Map[Int, List[Int]]) = {
      val (acc, map) = res
      val v = map.get(acc.last)
        .filter(_.size > 1)
        .map { case a :: b :: _ => a - b }
        .getOrElse(0)

      val newMap = map.updated(v, i:: map.getOrElse(v, Nil))
      val newAcc = acc :+ v
      (newAcc, newMap)
    }

    val (seq, finalMap) = (init.size until n).foldLeft((init,firstMap))(compute)
    seq
  }
  
}

VanEckTest.scala

package exo

import org.scalatest.flatspec.AnyFlatSpec
import org.scalatest.matchers.should.Matchers
import exo.VanEck._

class VanEckTest extends AnyFlatSpec with Matchers {

  val example = List(0,3,6)

  "Van Eck" should "find first ten items" in {
    generate0(example, 10) shouldBe List(0,3,6,0,3,3,1,0,4,0)
  }

  it should "compute 2020th element (example)" in {
    generate(example, 2020).last shouldBe 436
  }

  it should "compute 2020th element" in {
    generate0(List(18,11,9,0,5,1), 2020).last shouldBe 959
  }

  it should "compute 30e6th element" in {
    generate(example, 30_000_000).last shouldBe 175594
  }

}