Scala Codility GenomicRangeQuery performance

Question

I solved Codility's GenomicRangeQuery challenge in Scala. We are given a long DNA sequence (up to 100000 bases), where A, C, G, T are assigned values 1, 2, 3, 4, respectively. There are up to 50000 queries of the form (p_i, q_i), for each of which we should return the smallest value in the DNA string between positions p_i and q_i (inclusive, and zero-based).

I came up with the following solutions, both of which got 100% correctness but 0% performance. I'd like to know what can I do to improve the performance of these functions.

Answer #1

def solution(s: String, p: Array[Int], q: Array[Int]): Array[Int] = {
  for (i <- p.indices.toArray) yield {
    val gen = s.substring(p(i), q(i) + 1)
    gen match {
      case _ if gen.contains('A') => 1
      case _ if gen.contains('C') => 2
      case _ if gen.contains('G') => 3
      case _ if gen.contains('T') => 4
    }
  }
}

Answer #2

def solution(s: String, p: Array[Int], q: Array[Int]): Array[Int] = {
  val weights = 
    for (c <- s.toCharArray) yield c match {
      case 'A' => 1
      case 'C' => 2
      case 'G' => 3
      case 'T' => 4
    }

  for (i <- p.indices.toArray) yield weights.slilce(p(i), q(i) + 1).min
}

Answer 1

The basic task here is to search for the minimum value in the current subset, but there is a known floor value so it would be nice if we could terminate the search early if the floor value is encountered. Unfortunately the Standard Library doesn't have such an animal so we'll have to roll our own.

def solution(s: String, p: Array[Int], q: Array[Int]): Array[Int] = {

  val arr = s.toArray.map {   // String to Array of weighted values
    case 'A' => 1
    case 'C' => 2
    case 'G' => 3
    case 'T' => 4
  }

  def subMin(start: Int, end: Int, min: Int = 4): Int =
    if (start > end) min                                          // search done
    else if (arr(start) == 1 || arr(end) == 1) 1                  // early end
    else subMin(start+1, end-1, arr(start) min arr(end) min min)  // tail recurse

  p.indices.map(x => subMin(p(x), q(x))).toArray
}

With this I got 100% correctness and 66% performance.

So a different, and perhaps larger, performance issue is that once a subset has been evaluated it would be really nice if we never have to revisit it again, just recall the previous evaluation when needed.

That's the basic idea behind a segment tree. Essentially, your data becomes the leaves of a binary tree and each node contains the result of the associative operation on all the leaf values underneath it.

I won't paste the 40 lines of segment tree code here (worthy of independent study), but with that in place...

def solution(s: String, p: Array[Int], q: Array[Int]): Array[Int] = {

  val arr = s.toArray.map {   // String to Array of weighted values
    case 'A' => 1
    case 'C' => 2
    case 'G' => 3
    case 'T' => 4
  }

  val st = SegmentTree(arr, Math.min)  // build the segment tree

  p.indices.map(x => st(p(x), q(x))).toArray
}

... this got 100% correctness and 100% performance.