I am a programmer and architect (the kind that writes code) with a focus on testing and open source; I maintain the PHPUnit_Selenium project. I believe programming is one of the hardest and most beautiful jobs in the world. Giorgio is a DZone MVB and is not an employee of DZone and has posted 636 posts at DZone. You can read more from them at their website. View Full User Profile

Karate Chop

09.16.2013
| 2774 views |
  • submit to reddit

During one of our internal training events, we explored the Karate Chop kata (number #2 in the list of Dave Thomas). I went on in exercising myself after that, and here's a little recap of the experience.

A quick recap of the problem: implement binary search, a classic algorithm, over a sorted array (or your preferred random-access linear data structure, depending on your programming language.) You should compare different programming styles and paradigms if you can, with the goal of stimulating your creativity to find 5 different ways to implement the algorithm.

I don't want to spoil the kata for you, so I'll avoid code samples; however this article is full of implementation considerations so do not read it if you still want to try the kata without being primed by my direction.

#1: iterative

The iterative version of the algorithm is probably the easiest to implement and the one to start with. I think I was taught it during high school and it resurfaced while I was facing the acceptance tests prepared by Dave Thomas.

Basically, every iteration performs the following steps:

  • look for a pivot element in the middle of the current search space, which can be the array or a part of it.
  • Compare it with the searched element, and return its position in case of a success.
  • Move the search space to the left or to the right of the pivot, depending on the element being greater or less than the pivot itself.

There are some termination conditions that need to be tuned, to avoid accessing elements in positions outside of the array.

#2: recursive

Actually, tail recursive; having just implemented the iterative version, I found myself for the first time in where the tail recursive version of the algorithm seemed easier than the other recursive possibilities.

Basically, the entry point delegated to a recursive function whose signature was:

loop_recursive(element, list, min, max);

and that delegated to itself if going on with another search step, after redefining min and max to focus on a single section of the array.

I guess we can't wipe our brain RAM after the end of a kata; previous knowledge seeps in the new executions. This makes it less effortful to solve the problem, but it's part of the game as you get to experiment with more constraints.

#3: concurrent

A comment on the kata page suggested trying to write a concurrent version of the algorithm, based on threads. This was actually a very bad idea, but the process of understanding why was interesting.

To get a benefit from concurrent threads working on the same problem, you need some parallelizable process inside the algorithm. For example, summing the element of an array or mapping any function over it is an highly paralleliable operation as you can perform many different operations that have no dependency on each other.

The binary search algorithm is composed of O(log(n)) steps, where each one depends on the result of the previous one. For this reason it is not prone to become much more efficient, since spawning new threads would be either a waste if they go into the wrong direction; or there will lots of wait conditions for threads to wait on the previous ones to finish and synchronize with their result.

Parallel version of the algorithm indeed exists, and they achieve a speed up of a constant multiplier by dividing the original array linearly into sections, and performing search on each of the sections. This is an improvement, but hardly a breakthrough from a theoretical standpoint as the algorithm is still asymptotically O(log(n)) (big O notation does not even begin to describe an algorithm performance fully, but I just want to note it's not that clever idea like a B-tree).

Conclusions

I still have to experiment two other ways to implement binary search to have a comparison.

One thing I may find useful in the future to avoid derailment is to write in big letters the goal of a kata next to the keyboard. When we first tackled the problem in our book club, we drifted to experimenting with TDD-as-you-mean-it due to a fault of mine. There are times when you want to experiment with one technique, while there are others where your focus is elsewhere.

In fact, this problem is simple to describe, but difficult enough that you should keep a single constraint (e.g. iterative or recursive version) while solving it, leaving other experimentations for the second time you try a particular style. I started with a plain recursive solution implemented one-test-at-a-time, and find out big problems with the returned indexes while making the first half of the test pass... Problems that made me delete the code and start again. After all, starting again a kata is the only free action while exercising.

Published at DZone with permission of Giorgio Sironi, author and DZone MVB.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Tags: