1
\$\begingroup\$

Problem - Given three sorted arrays find combinations which are closest to each other.

example -

i/p - 3,8,18  7,11,16  10,15,19
o/p - (8,7,10)

i/p - 2,2,6  11,15,15  8,8,18
o/p - (6,11,8)

Kindly review this scala code and suggest improvements

import scala.math.Ordering._

object NearestMatch {

  def main(args: Array[String]) = {
    val size = args(0).toInt
    val range = args(1).toInt
    val (a,b,c) = (Array.fill(size)(scala.util.Random.nextInt(range)).sorted,
           Array.fill(size)(scala.util.Random.nextInt(range)).sorted,
           Array.fill(size)(scala.util.Random.nextInt(range)).sorted)

   println(a.mkString(","))
   println(b.mkString(","))
   println(c.mkString(","))

  var (i,j,k) = (0,0,0)
  var (pa,pb,pc) = (0,0,0)

  var curDiff = 12345 // a very large number
  while (i < a.size && j < b.size && k < c.size) {
    val min = Math.min(a(i), Math.min(b(j), c(k)))
    val max = Math.max(a(i), Math.max(b(j), c(k)))
    val newDiff = max-min

    if (curDiff > newDiff) {
      pa = i
      pb = j
      pc = k
      curDiff = newDiff
    }

    if (a(i) == min) i+=1
    else if (b(j) == min) j+=1
    else k+=1
  }
   println(a(pa), b(pb), c(pc))
  }
}
\$\endgroup\$
1
\$\begingroup\$

A few things I noticed while looking over the code:

  1. You don't need the import scala.math.Ordering._ statement. It's not buying you anything.
  2. It would be easier to read/follow the code if you used better variable names.
  3. 12345 actually isn't a very big Int. Int.MaxValue would be better.
  4. If this val size = args(0).toInt is zero then this println(a(pa), b(pb), c(pc)) will throw.
  5. According to a hint from the IntelliJ IDE, array.length is more efficient than array.size because .size "requires an additional implicit conversion to SeqLike to be made."

But the real problem is that you're using Scala, a functional language, to write imperative code with many mutable variables, making the code more verbose.

Your algorithm is efficient and limits the number of while loop iterations, so how to express it in a functional manner: recursion.

def minDif[N:Numeric](x :Seq[N] ,y :Seq[N] ,z :Seq[N]
                     ,curSet :Seq[N] ,curDiff :N) :Unit = {
  import Numeric.Implicits._
  import Ordering.Implicits._

  if (x.isEmpty || y.isEmpty || z.isEmpty)
    println(curSet.mkString(","))  //done
  else {
    val newSet  = Seq(x.head, y.head, z.head)
    val newMin  = newSet.min
    val newDiff = newSet.max - newMin
    val (nxtSet, nxtDiff) = if (curDiff > newDiff) (newSet, newDiff)
                            else                   (curSet, curDiff)
    newSet match {
      case Seq(`newMin`,_,_) => minDif(x.tail, y, z, nxtSet, nxtDiff)
      case Seq(_,`newMin`,_) => minDif(x, y.tail, z, nxtSet, nxtDiff)
      case Seq(_,_,`newMin`) => minDif(x, y, z.tail, nxtSet, nxtDiff)
    }
  }
}

// a b and c have already been populated and sorted
minDif(a, b, c, Seq(), Int.MaxValue)

The minDif() method is tail recursive so it is compiled to an equivalent while loop under the hood.

Notice that I used Seq as the collection type. This allows minDif() to accept many different types as input: Array, Stream, Vector, etc. Since there is no indexing into any collection there is little advantage in restricting it to just arrays.

Also the element type is Numeric so this will work with Int, Float, Long, etc.

\$\endgroup\$
  • \$\begingroup\$ Your solution is certainly more compact, infact it was first solution I came up with. But it turned out to be very slow for longer arrays (since it is taking all combinations in account) . For list with 1000 elements it coredumps because of exhausted heap. \$\endgroup\$ – vikrant Nov 4 '18 at 4:21
  • \$\begingroup\$ See the update. \$\endgroup\$ – jwvh Nov 5 '18 at 9:23
  • \$\begingroup\$ thanks for comment. this version works, but when I compare performance it is a but expensive. For 10000 number arrays recursive version took 1025771008 ns (nano seconds) while iterative took 9347872 ns. For 50000 numbers difference is more significant (more than two times) recursive 25612533913 ns , iterative 27517216 ns . I do think that my code look like iterative, but if it solves the problem in more efficient way then the functional version, shouldnt we stick to it? \$\endgroup\$ – vikrant Nov 5 '18 at 19:21
  • \$\begingroup\$ @vikrant; Yes, you should stick with your current code if A) efficient throughput is of paramount importance, and B) you are required code in Scala. No other language permitted. You're writing C code in Scala, which says something about Scala's flexibility, but it's not what the language was designed for. \$\endgroup\$ – jwvh Nov 6 '18 at 0:40
  • \$\begingroup\$ yes I have both (A & B) of constraints. I do see that performance is comparable for small arrays, but i need to design it for longer arrays. \$\endgroup\$ – vikrant Nov 10 '18 at 6:02

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.