Book Review: Collective Intelligence

Have you ever wondered how:

• Google comes up with its search results
• Amazon recommends you books/movies/music
• spam filters decide good from bad

Well, Toby Segaran not only explains these topics and more in Collective Intelligence, but he does so in a way accessible to software developers that haven't worked on machine-learning problems before. He even provides working Python code for all the algorithms.

Oh, and Collective Intelligence reads incredibly well. I could not wait to get home and get back to it -- and when I went in to work the next morning, I usually had a new idea or two of how to improve our software. I also started implementing the most important examples in Groovy to make sure I got it.

If you are a Senior Software Engineer or "better," this is a must-read. Proper application of the algorithms in this book are a great way to simplify your system and avoid getting nickel-and-dimed to death with new ways to prioritize/categorize/slice-and-dice your domain data.

Care to search for integers that sum?

I spent the better part of yesterday pondering how to efficiently search a sorted array of integers to see if a pair of integers within the array sum to given integer.

i.e., given the numbers 1, 2, 3, 5, 8, 13 -- does any pair of them add up to 8 (yes: 3+5), 13 (yes: 5+8), or 17 (no)?

There's several ways to solve this problem, but the trick is to do it in linear time (only visit each number in the array once) and linear space (don't make any copies of the numbers in the array).

After giving it the old college try, I searched for the proper algorithm and found it.

Here's the resulting Java:

public class IntsForSumJava {

 public static boolean doIntsForSumExist(int[] inputs, int target_sum) {
   int start_idx = 0;
   int end_idx = inputs.length - 1;
   boolean found_target = false;
   int iterations = 0;

   while (!found_target) {
     iterations++;
     int start = inputs[start_idx];
     int end = inputs[end_idx];
     if (end == (target_sum - start)) {
       found_target = true;
     } else if (end > (target_sum - start)) {
       end_idx--;
       if (end_idx > end_idx) {
         break;
       }
     }
   }
   System.out.println("iterations: " + iterations);
   return found_target;
 }

 public static void main(String[] args) {
   int[] inputs = {1, 2, 3, 5, 8, 13};
   int target_sum = 0;
   System.out.println("found target (" + target_sum + "): " +
       IntsForSumJava.doIntsForSumExist(inputs, target_sum));
   target_sum = 8;
   System.out.println("found target (" + target_sum + "): " +
       IntsForSumJava.doIntsForSumExist(inputs, target_sum));
   target_sum = 13;
   System.out.println("found target (" + target_sum + "): " +
       IntsForSumJava.doIntsForSumExist(inputs, target_sum));
   target_sum = 17;
   System.out.println("found target (" + target_sum + "): " +
       IntsForSumJava.doIntsForSumExist(inputs, target_sum));
 }
}

Just in case you were wondering...

Happy searching.