6
\$\begingroup\$

I've tried to create optimal in terms of performance and memmory consumption. But also I've tried to make it functional and scala way. I want to get you comment on how to make it more 'scala'stic

object LifeGame extends App {
    trait Matrix extends Iterable[(Int, Int)] {
        def apply(p: (Int, Int)): Boolean
        def update(p: (Int, Int), b: Boolean): Unit
        def newInstance: Matrix;
    }

    class SparseMapMatrix extends Matrix {
        type Point = (Int, Int)

        private var data = Set[(Int, Int)]()

        def apply(p: Point): Boolean = data.contains(p)

        def update(p: Point, b: Boolean) = if (b) data += p else data -= p

        def newInstance = new SparseMapMatrix()

        def iterator = data.iterator

        override def toString() = {
            val sb = new StringBuilder()
            def best(func: (Int, Int) => Int)(p1: Point, p2: Point) = (func(p1._1, p2._1), func(p1._2, p2._2))
            val minBoundary = ((0, 0) /: iterator)(best(math.min))
            val maxBoundary = ((0, 0) /: iterator)(best(math.max))
            for (i <- minBoundary._1 to maxBoundary._1) {
                sb.append("\n")
                for (j <- minBoundary._2 to maxBoundary._2) {
                    sb.append(if (this((i, j))) "x" else " ")
                }
            }
            sb.append("\nmin=%s, max=%s" format(minBoundary, maxBoundary))
            sb.toString()
        }
    }

    object Engine {
        def apply(input: Matrix): Matrix = {
            val result = input.newInstance
            def block2D(pp: (Int, Int)): Seq[(Int, Int)] =
                for (ii <- block1D(pp._1); jj <- block1D(pp._2)) yield (ii, jj)
            val liveCells = for (p <- input.iterator.flatMap(block2D).toSet[(Int, Int)].par) yield {
                val offsets = block2D(p).filter(_ != p)
                val nn = offsets.map(p => input(p)).count(_ == true)
                case class State(l: Boolean, n: Int)
                val newValue = State(input(p), nn) match {
                    case State(true, n) if n < 2 => false
                    case State(true, 2) | State(true, 3) => true
                    case State(true, n) if n > 3 => false
                    case State(false, 3) => true
                    case State(value, _) => value
                };
                 if(newValue) Some(p) else None
            }
            liveCells.seq.foreach { _ match { case Some(p:Point) => result(p) = true; case _ => ;}}
            result
        }
    }

    def block1D(i: Int) = i - 1 to i + 1

}
\$\endgroup\$
4
\$\begingroup\$

The main-things I changed:

  • Matrix is now completely immutable
  • Code is more self-documenting (extract complex code to methods, etc.)
  • I deleted the unnecessary inheritance
  • I don't like apply-methods which are used as contains-methods -> name change
  • I deleted parentheses in side-effect free methods
  • Many syntax improvements

The code:

object LifeGame extends App {
  case class Point(x: Int = 0, y: Int = 0)

  object Matrix {
    def empty: Matrix =
      Matrix(Set.empty)
  }

  case class Matrix(private val data: Set[Point]) {

    def contains(p: Point): Boolean =
      data contains p

    def update(p: Point, b: Boolean) =
      if (b) copy(data+p) else copy(data-p)

    def iterator: Iterator[Point] =
      data.iterator

    override def toString = {
      def best(func: (Int, Int) => Int)(p1: Point, p2: Point) =
        Point(func(p1.x, p2.x), func(p1.y, p2.y))

      val minBoundary = (Point() /: iterator) { best(math.min) }
      val maxBoundary = (Point() /: iterator) { best(math.max) }

      val sb = StringBuilder.newBuilder
      for (i <- minBoundary.x to maxBoundary.x) {
        sb.append("\n")
        for (j <- minBoundary.y to maxBoundary.y) {
          sb.append(if (this contains Point(i, j)) "x" else " ")
        }
      }
      sb.append("\nmin=%s, max=%s" format (minBoundary, maxBoundary))
      sb.toString
    }
  }

  object Engine {

    def newCell: (Boolean, Int) => Boolean = {
      case (true, 0 | 1) => false
      case (true, 2 | 3) => true
      case (true, _) => false
      case (false, n) => n == 3
    }

    def apply(input: Matrix): Matrix = {
      def block1D(i: Int) =
        Seq(i-1, i, i+1)

      def block2D(p: Point) =
        for (x <- block1D(p.x); y <- block1D(p.y)) yield Point(x, y)

      def points =
        (input.iterator flatMap block2D).toSet.par

      def calcCell(p: Point) = {
        val neighbours = block2D(p) filter { p != }
        val alive = neighbours map { input contains } count { true == }

        if (newCell(input contains p, alive)) Some(p)
        else None
      }

      val cells = (points map calcCell).seq collect { case Some(p) => p }
      (Matrix.empty /: cells) { (result, p) => result(p) = true }
    }
  }
}
\$\endgroup\$
  • \$\begingroup\$ Thanks, great response. BTW why do you think def newCell: (Boolean, Int) => Boolean better than de newCell(p:(Boolean,Int)):Boolean ? And Don't you think that builder is better approach(in terms of speed) for creating immutable Matrix? \$\endgroup\$ – yura Oct 3 '11 at 10:05
  • \$\begingroup\$ A PartialFunction allows syntax sugar (you don't need to write the match-keyword). Functional programming is not the way to create really performance programs. The JVM can optimize very well so I don't think about performance unless I get problems. \$\endgroup\$ – kiritsuku Oct 3 '11 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.