Happy World Noodle

I figured I’d try this challenge.

Solution Speed depends on which sorting algorithm you use, which you’d tailor based on various factors.
Other than that, it works close to the sort speed.

This works by first sorting the array, then trimming the outer edges that are beyond the possible bounds.
In the process, it finds (or doesn’t) the summing numbers.

public static Pair containsSum(int[] list, int sum) {
	java.util.Arrays.sort(list);  // Uses quicksort.  Can choose a different algo
	int end = list.length-1;
	int start = 0;

	while(start <= end) {
                // Check that we're not already out of bounds
		if(list[start] * 2 > sum) return None;
		if(list[end] * 2 < sum) return None;

                // A little optimization.  Assumes each entry is also added to itself
		if(list[start] * 2 == sum) return new Pair(list[start], list[start]);
		if(list[end] * 2 == sum) return new Pair(list[end], list[end]);

                // Now check the current ends
		int mySum = list[start]+list[end];

		if(mySum == sum)
			return new Pair(list[start],list[end]); upper bound
		else if(mySum > sum)  // if true, the top is out of bounds, so tighten
			end–;
		else if(mySum < sum)  // if true, the bottom is out of bounds, so tighten
			start++;
	}
	return None;
}

The result returns the matching pair rather than a boolean. Here’s Pair and None:

public class Pair {
    public static final Pair None = new Pair(null,null) {

    final Object v1, v2;
    Pair(Object v1, Object v2) {this.v1 = v1; this.v2 = v2;}
      public String toString() {return "(" + v1 + "," + v2 + ")";}
    }
    public String toString() {return "None";}
};

Side Note
On a side note, I used the brute force O(n!) search to unit test. This was still pretty quick in Java. I thought I’d try a in a few different languages to see performance differences. There was a big difference.
Java

public static Pair containsSum(int[] list, int sum) {
  for(int i = list.length-1; i >= 0; i--) {
    for(int j = i; j >= 0; j--) {
      if(list[i]+list[j] == sum) return new Pair(list[i],list[j]);
    }
  }
  return None;
}

This performed far and away the fastest of all of my variations (100ms for a 10,000 entry array versus 5000ms for the closest competitor), which would be expected given the tight loops.

Scala
I did a few versions in Scala. The Scala equivalent to the Java above was really slow.

def containsSumIt(list:Seq[Int], sum:Int):Option[Pair[Int,Int]] = {
    val size = if(list == null) 0 else list.size
    var i = 0
    while(i < size) {
      var j = i
      while(j < size) {
        if(list(i)+list(j) == sum) return Some(list(i),list(j))
        j+=1
      }
      i+=1
    }
    None
}

Actually that’s a bit optimized, but the pure for-comprehension version was even slower.

The recursive counterparts were slower, which is obviously due to the fact that the JVM doesn’t have tail-recursion:

def containsSumR2(list:Seq[Int], sum:Int):Option[Pair[Int,Int]] = {
    if(list == null || list.isEmpty) return None

    def containsSumSub(list:Seq[Int], sum:Int, index:Int):Option[Pair[Int,Int]] = index match {
    case -1 => None
    case 0 => if(list(0) + list(0) == sum) Some(list(0),list(0)) else None
    case x =>
      var i = x
      while(i >= 0) if(list(x)+list(i) == sum) return Some(x,i) else i -= 1
      containsSumSub(list, sum, index-1)
    }

    containsSumSub(list, sum, list.size-1)
}

Here’s an even slower, but more functional, variation:

def containsSumR(seq:List[Int], sum:Int):Option[Pair[Int,Int]] = seq.size match {
  case 0 => None
  case _ =>
    for(i <- seq; j <- seq) if(i+j == sum) return Some(i,j)
    containsSumR(seq.tail, sum)
}

It was actually faster to loop the entire array (O(n^2)) than call List.slice(i) for each outer iteration.

To move this along, I implemented a version that parallelizes each outer-loop iteration. This sped things up a lot on my dual CPU machine:

def containsSumPar(list:Seq[Int], sum:Int):Option[Pair[Int,Int]] = {
    import java.util.concurrent._
    val size = if(list == null) 0 else list.size

    if(size == 0) return None
    if(size == 1) return if(list(0)*2 == sum) Some(list(0),list(0)) else None

    val executor = Executors.newFixedThreadPool(availableProcessors)
    val ecs = new ExecutorCompletionService[Option[Pair[Int,Int]]](executor)
    var outstanding = 0

    try {
      var futures = for(i <- List.range(0,size)) yield {
        val myList = list.slice(i)

        val c = new java.util.concurrent.Callable[Option[Pair[Int,Int]]]() {
          override def call():Option[Pair[Int,Int]] = {
            val x = myList(0)
            for(myI <- myList) if(x+myI == sum) return Some(x,myI)
            None
          }
        }
        ecs.submit(c)
        outstanding += 1

        if(i >= availableProcessors) {
          val result = ecs.take.get
          outstanding -= 1
          if(result != None) return result
        }
      }

      for(i <- 0 until outstanding) {
        val result = ecs.take.get
        if(result != None) return result
       }
      None
    }
    finally {
      executor.shutdownNow
}

I would’ve liked to have done this with Actors.

OCaml
Finally, I did an OCaml version, just to see how real tail-recursion performed (much better):

let rec range i j = if i > j then [] else i :: range (i+1) j;;

let rec hassum_sub sum v list =
  match list with
  | [] -> None
  | (x::rest) -> if v+x == sum then Some(v,x) else hassum_sub sum v rest
;;

let rec hassum list sum =
  match list with
  | [] -> None
  | (x::rest) -> match hassum_sub sum x list with
    | None -> hassum rest sum
    | y -> y
;;

This entry was posted on Monday, July 14th, 2008 at 6:47 am and is filed under programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.