Edit Distance Performance Code

  def editDistance(word: String, target: String, v0: Array[Int], v1: Array[Int]) = {

    def min(a: Int, b: Int, c: Int) = Math.min(a, Math.min(b, c))

    val limit = target.size

    @tailrec
    def distanceByRow(index: Int, v0: Array[Int], v1: Array[Int]): Int = {
      if (index >= word.length) v0(target.length)
      else {
        v1(0) = index + 1
        // slow code start (note that (0 until target.length) foreach { j => has same performance)
        for (j <- 0 until limit) {
          val cost = if (word(index) == target(j)) 0 else 1
          v1(j + 1) = min(v1(j) + 1, v0(j + 1) + 1, v0(j) + cost);
        }
        // slow code end
        // fast code start
        @tailrec
        def distanceByColumn(col: Int): Unit = {
          if (col < limit) {
            val cost = if (word(index) == target(col)) 0 else 1
            v1(col + 1) = min(v1(col) + 1, v0(col + 1) + 1, v0(col) + cost);
            distanceByColumn(col + 1)
          }
        }
        distanceByColumn(0)
        // fast code end
        distanceByRow(index + 1, v1, v0)
      }
    }

    // initialize v0 as previous row of distances (starts as edit distance for empty 'word')
    for { i <- v0.indices } v0(i) = i

    // recursively process rows matching characters in word being compared to find best
    distanceByRow(0, v0, v1)
  }