This morning I spent an hour or so working on recreating the Three Sum algorithm in Java (I know because, for the sake of motivation, I timed myself). I wanted to recreate the solution suggested in the class I'm following: go through all the possible pairs in the array and select, from the remaining values, all elements that sum to zero when added together with the pairs[1] -- using binary search.
That's the solution that takes you from O(n^3) to O(n^2 log n) -- if I'm getting the notation right. Because binary search for N elements is a log N algorithm: if you look through N elements by dividing them into halves, you can do that at worst log N times. (8 elements = 2 halves of 4 elements = 4 parts of 2 elements = 8 singletons, or 8 => 4 => 2 => 1 = 3 steps -- I guess, not including 8 itself = log 8).
Again, I had a few problems:
That's the solution that takes you from O(n^3) to O(n^2 log n) -- if I'm getting the notation right. Because binary search for N elements is a log N algorithm: if you look through N elements by dividing them into halves, you can do that at worst log N times. (8 elements = 2 halves of 4 elements = 4 parts of 2 elements = 8 singletons, or 8 => 4 => 2 => 1 = 3 steps -- I guess, not including 8 itself = log 8).
Again, I had a few problems:
- I forgot to put my midpoint value inside the loop (it was not being recalculated each time the high and low points changed).
- I had the loop running while the low was less than the high, not less than or equal to the high.
The last part screwed up my results by quite a bit. Where I was supposed to find 80 triples, for instance, I only found 40.
The hard thing about debugging algorithms in Java, for me, is that there's a lot more infrastructure to set up before you can actually run the algorithm. Java still feels clunkier than JavaScript -- just because it's less permissive. One simple example: I wanted to feed an array into a function as test data. In JavaScript you would just write:
foo([1,2,3,4,5,6])
but after a half-hearted Google search and consultation with a friend, I learned that Java wants you to write
foo(new {1,2,3,4,5,6})
-- an anonymous object, if I remember from C#. But I didn't think of that beforehand. So it's one of these languages that's just picky. And then there are different methods inside of a class that have to be called. And then there's all this data going through the methods. So I also have a lesson for today:
If you want to debug an algorithm running on a big data set, find a representative portion of the data that you understand and work with that.
Otherwise you'll just get lost.
I'll still have to think a bit more to figure out how to debug recursive functions -- because in that case, the call-stack kind of becomes your big data set. And it's hard to think about what things might be going wrong inside a very big call stack.
One more obvious moral for the day as a parting gift:
Don't run binary search on arrays that haven't been sorted.
LOL.
[1] Another thing I thought about was how you make sure you get all the unique triples that sum to zero. That's why, in the algorithm I'm following, you define each inner loop over one plus the value of the outer loop. I think a long time ago I tried to solve this problem by deleting elements from the array once the program had found mates for them -- but that couldn't have been the most efficient way to do it. So in the final version of the algorithm, look at each element in the array and find pairs for it from all the elements following it, then accept only binary search results that are later than the pair. And that raises another issue -- you can only run this version of the algorithm on a set. If there are multiple items that sum to zero with a pair, binary search won't get you the right one. That's when you would need to start thinking about deleting things from the array -- but it would screw up the rest of the book-keeping.
but after a half-hearted Google search and consultation with a friend, I learned that Java wants you to write
foo(new {1,2,3,4,5,6})
-- an anonymous object, if I remember from C#. But I didn't think of that beforehand. So it's one of these languages that's just picky. And then there are different methods inside of a class that have to be called. And then there's all this data going through the methods. So I also have a lesson for today:
If you want to debug an algorithm running on a big data set, find a representative portion of the data that you understand and work with that.
Otherwise you'll just get lost.
I'll still have to think a bit more to figure out how to debug recursive functions -- because in that case, the call-stack kind of becomes your big data set. And it's hard to think about what things might be going wrong inside a very big call stack.
One more obvious moral for the day as a parting gift:
Don't run binary search on arrays that haven't been sorted.
LOL.
[1] Another thing I thought about was how you make sure you get all the unique triples that sum to zero. That's why, in the algorithm I'm following, you define each inner loop over one plus the value of the outer loop. I think a long time ago I tried to solve this problem by deleting elements from the array once the program had found mates for them -- but that couldn't have been the most efficient way to do it. So in the final version of the algorithm, look at each element in the array and find pairs for it from all the elements following it, then accept only binary search results that are later than the pair. And that raises another issue -- you can only run this version of the algorithm on a set. If there are multiple items that sum to zero with a pair, binary search won't get you the right one. That's when you would need to start thinking about deleting things from the array -- but it would screw up the rest of the book-keeping.
"If you want to debug an algorithm running on a big data set, find a representative portion of the data that you understand and work with that."
ReplyDeleteYes that is a great lesson to learn. Always start with the most simple representation of the problem and master that before adding additional layers to it.