You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by rw...@apache.org on 2003/12/01 20:22:41 UTC
cvs commit: jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/kata/two TestBinaryChop.java BaseBinaryChop.java
rwaldhoff 2003/12/01 11:22:41
Modified: functor/src/test/org/apache/commons/functor/example/kata/two
TestBinaryChop.java BaseBinaryChop.java
Log:
revised kata two examples
Revision Changes Path
1.5 +240 -113 jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/kata/two/TestBinaryChop.java
Index: TestBinaryChop.java
===================================================================
RCS file: /home/cvs/jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/kata/two/TestBinaryChop.java,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- TestBinaryChop.java 1 Dec 2003 16:40:11 -0000 1.4
+++ TestBinaryChop.java 1 Dec 2003 19:22:41 -0000 1.5
@@ -56,6 +56,7 @@
*/
package org.apache.commons.functor.example.kata.two;
+import java.util.Collections;
import java.util.List;
import junit.framework.Test;
@@ -67,6 +68,42 @@
import org.apache.commons.functor.generator.util.IntegerRange;
/**
+ * Examples of binary search implementations.
+ *
+ * A binary search algorithm is the same strategy used in
+ * that number guessing game, where one player picks a number
+ * between 1 and 100, and the second player tries to guess it.
+ * Each time the second player guesses a number, the first player
+ * tells whether the chosen number is higher, lower or equal to
+ * the guess.
+ *
+ * An effective strategy for this sort of game is always guess
+ * the midpoint between what you know to be the lowest and
+ * highest possible number. This will find the number in
+ * log2(N) guesses (when N = 100, this is at most 7 guesses).
+ *
+ * For example, suppose the first player (secretly) picks the
+ * number 63. The guessing goes like this:
+ *
+ * P1> I'm thinking of a number between 1 and 100.
+ * P2> Is it 50?
+ * P1> Higher.
+ * P2> 75?
+ * P1> Lower.
+ * P2> 62?
+ * P1> Higher.
+ * P2> 68?
+ * P1> Lower.
+ * P2> 65?
+ * P1> Lower.
+ * P2> 63?
+ * P1> That's it.
+ *
+ * Dave Thomas's Kata Two asks us to implement a binary search algorithm
+ * in several ways. Here we'll use this as an opportunity to
+ * consider some common approaches and explore
+ * some functor based approaches as well.
+ *
* See http://pragprog.com/pragdave/Practices/Kata/KataTwo.rdoc,v
* for more information on this Kata.
*
@@ -81,146 +118,236 @@
public static Test suite() {
return new TestSuite(TestBinaryChop.class);
}
-
- public void setUp() throws Exception {
- super.setUp();
- }
-
- public void tearDown() throws Exception {
- super.tearDown();
- }
-
+
+ /**
+ * This is Dave's test case, plus
+ * a quick check of searching a fairly large
+ * list, just to make sure the time and space
+ * requirements are reasonable.
+ */
private void chopTest(BinaryChop chopper) {
assertEquals(-1, chopper.find(3, new int[0]));
assertEquals(-1, chopper.find(3, new int[] { 1 }));
- assertEquals(0, chopper.find(1, new int[] { 1 }));
+ assertEquals(0, chopper.find(1, new int[] { 1 }));
- assertEquals(0, chopper.find(1, new int[] { 1, 3, 5 }));
- assertEquals(1, chopper.find(3, new int[] { 1, 3, 5 }));
- assertEquals(2, chopper.find(5, new int[] { 1, 3, 5 }));
+ assertEquals(0, chopper.find(1, new int[] { 1, 3, 5 }));
+ assertEquals(1, chopper.find(3, new int[] { 1, 3, 5 }));
+ assertEquals(2, chopper.find(5, new int[] { 1, 3, 5 }));
assertEquals(-1, chopper.find(0, new int[] { 1, 3, 5 }));
assertEquals(-1, chopper.find(2, new int[] { 1, 3, 5 }));
assertEquals(-1, chopper.find(4, new int[] { 1, 3, 5 }));
assertEquals(-1, chopper.find(6, new int[] { 1, 3, 5 }));
- assertEquals(0, chopper.find(1, new int[] { 1, 3, 5, 7 }));
- assertEquals(1, chopper.find(3, new int[] { 1, 3, 5, 7 }));
- assertEquals(2, chopper.find(5, new int[] { 1, 3, 5, 7 }));
- assertEquals(3, chopper.find(7, new int[] { 1, 3, 5, 7 }));
+ assertEquals(0, chopper.find(1, new int[] { 1, 3, 5, 7 }));
+ assertEquals(1, chopper.find(3, new int[] { 1, 3, 5, 7 }));
+ assertEquals(2, chopper.find(5, new int[] { 1, 3, 5, 7 }));
+ assertEquals(3, chopper.find(7, new int[] { 1, 3, 5, 7 }));
assertEquals(-1, chopper.find(0, new int[] { 1, 3, 5, 7 }));
assertEquals(-1, chopper.find(2, new int[] { 1, 3, 5, 7 }));
assertEquals(-1, chopper.find(4, new int[] { 1, 3, 5, 7 }));
assertEquals(-1, chopper.find(6, new int[] { 1, 3, 5, 7 }));
assertEquals(-1, chopper.find(8, new int[] { 1, 3, 5, 7 }));
-
- List largeList = (List)(new IntegerRange(0,100001).toCollection());
- assertEquals(-1, chopper.find(new Integer(-5),largeList));
- assertEquals(100000, chopper.find(new Integer(100000),largeList));
- assertEquals(0, chopper.find(new Integer(0),largeList));
- assertEquals(50000, chopper.find(new Integer(50000),largeList));
-
- }
+ List largeList = (List) (new IntegerRange(0, 100001).toCollection());
+ assertEquals(-1, chopper.find(new Integer(-5), largeList));
+ assertEquals(100000, chopper.find(new Integer(100000), largeList));
+ assertEquals(0, chopper.find(new Integer(0), largeList));
+ assertEquals(50000, chopper.find(new Integer(50000), largeList));
+
+ }
+
+ /**
+ * In practice, one would most likely use the
+ * binary search method already available in
+ * java.util.Collections, but that's not
+ * really the point of this exercise.
+ */
+ public void testBuiltIn() {
+ chopTest(new BaseBinaryChop() {
+ public int find(Object seeking, List list) {
+ int result = Collections.binarySearch(list,seeking);
+ //
+ // Collections.binarySearch is a bit smarter than our
+ // "find". It returns
+ // (-(insertionPoint) - 1)
+ // when the value is not found, rather than
+ // simply -1.
+ //
+ return result >= 0 ? result : -1;
+ }
+ });
+ }
+
+ /**
+ * Here's a basic iterative approach.
+ *
+ * We set the lower or upper bound to the midpoint
+ * until there's only one element between the lower
+ * and upper bound. Then the lower bound is where
+ * the element would be found if it existed in the
+ * list.
+ *
+ * We add an additional comparision at the end so
+ * that we can return -1 if the element is not yet
+ * in the list.
+ */
public void testIterative() {
- chopTest(
- new BaseBinaryChop() {
- public int find(Object seeking, List list) {
- int high = list.size();
- int low = 0;
- int cur = 0;
- while(low < high) {
- cur = (high+low)/2;
- int comp = ((Comparable)(list.get(cur))).compareTo(seeking);
- if(comp == 0) {
- return cur;
- } else if(comp < 0) {
- if(low == cur) { cur++; }
- low = cur;
- } else {
- high = cur;
- }
+ chopTest(new BaseBinaryChop() {
+ public int find(Object seeking, List list) {
+ int high = list.size();
+ int low = 0;
+ while (high - low > 1) {
+ int mid = (high + low) / 2;
+ if(greaterThan(list,mid,seeking)) {
+ high = mid;
+ } else {
+ low = mid;
}
- return -1;
}
- });
+ return list.isEmpty() ? -1 : (equals(list,low,seeking) ? low : -1);
+ }
+ });
}
+ /**
+ * A recursive version of that implementation uses
+ * method parameters to track the upper and
+ * lower bounds.
+ */
public void testRecursive() {
- chopTest(
- new BaseBinaryChop() {
- public int find(Object seeking, List list) {
- if(list.size() == 0) {
- return -1;
+ chopTest(new BaseBinaryChop() {
+ public int find(Object seeking, List list) {
+ return find(seeking, list, 0, list.size());
+ }
+
+ private int find(Object seeking, List list, int low, int high) {
+ if(high - low > 1) {
+ int mid = (high + low) / 2;
+ if(greaterThan(list,mid,seeking)) {
+ return find(seeking,list,low,mid);
} else {
- int pivot = list.size()/2;
- int offset = 0;
- int comp = ((Comparable)(list.get(pivot))).compareTo(seeking);
- if(comp == 0) {
- return pivot;
- } else if(comp < 0) {
- offset = find(seeking,list.subList(Math.max(pivot,1),list.size()));
- } else {
- offset = find(seeking,list.subList(0,pivot));
- }
- return -1 == offset ? -1 : (comp == 1) ? offset : pivot+offset;
+ return find(seeking,list,mid,high);
}
+ } else {
+ return list.isEmpty() ? -1 : (equals(list,low,seeking) ? low : -1);
}
- });
+ }
+ });
}
+ /**
+ * We can use the Algorithms.recuse method
+ * to implement that as tail recursion.
+ *
+ * Here the anonymous Function implemenation
+ * holds this itermediate state, rather than
+ * the VM's call stack.
+ *
+ * Arguably this is more like a continuation than
+ * tail recursion, since there is a bit of state
+ * to be tracked.
+ */
+ public void testTailRecursive() {
+ chopTest(new BaseBinaryChop() {
+ public int find(final Object seeking, final List list) {
+ return ((Number)Algorithms.recurse(new Function() {
+ public Object evaluate() {
+ if(high - low > 1) {
+ int mid = (high + low) / 2;
+ if(greaterThan(list,mid,seeking)) {
+ high = mid;
+ } else {
+ low = mid;
+ }
+ return this;
+ } else {
+ return list.isEmpty() ?
+ BaseBinaryChop.NEGATIVE_ONE :
+ (BaseBinaryChop.equals(list,low,seeking) ?
+ new Integer(low) :
+ BaseBinaryChop.NEGATIVE_ONE);
+ }
+ }
+ int high = list.size();
+ int low = 0;
+ })).intValue();
+ }
+ });
+ }
+
+ /**
+ * One fun functional approach is to "slice" up the
+ * list as we search, looking at smaller and
+ * smaller slices until we've found the element
+ * we're looking for.
+ *
+ * Note that while any given call to this recursive
+ * function may only be looking at a sublist, we
+ * need to return the index in the overall list.
+ * Hence we'll split out a method so that we can
+ * pass the offset in the original list as a
+ * parameter.
+ *
+ * With all of the subList creation, this approach
+ * is probably less efficient than either the iterative
+ * or the recursive implemenations above.
+ */
public void testRecursive2() {
- chopTest(
- new BaseBinaryChop() {
- public int find(Object seeking, List list) {
- return find(seeking,list,0,list.size());
- }
-
- private int find(Object seeking, List list, int low, int high) {
- if(low >= high) {
- return -1;
+ chopTest(new BaseBinaryChop() {
+ public int find(Object seeking, List list) {
+ return find(seeking,list,0);
+ }
+
+ private int find(Object seeking, List list, int offset) {
+ if(list.isEmpty()) {
+ return -1;
+ } if(list.size() == 1) {
+ return (equals(list,0,seeking) ? offset : -1);
+ } else {
+ int mid = list.size() / 2;
+ if(greaterThan(list,mid,seeking)) {
+ return find(seeking,list.subList(0,mid),offset);
} else {
- int cur = (high+low)/2;
- int comp = ((Comparable)(list.get(cur))).compareTo(seeking);
- if(comp == 0) {
- return cur;
- } else if(comp < 0) {
- if(low == cur) { cur++; }
- return find(seeking,list,cur,high);
- } else {
- return find(seeking,list,low,cur);
- }
+ return find(seeking,list.subList(mid,list.size()),offset+mid);
}
}
- });
- }
- public void testTailRecursive() {
- chopTest(
- new BaseBinaryChop() {
- public int find(final Object seeking, final List list) {
- return ((Number)Algorithms.recurse(
- new Function() {
- public Object evaluate() {
- if(low < high) {
- int mid = (high+low)/2;
- int comp = ((Comparable)(list.get(mid))).compareTo(seeking);
- if(comp == 0) {
- return new Integer(mid);
- } else if(comp < 0) {
- if(mid == low) { mid++; }
- low = mid;
- return this;
- } else {
- high = mid;
- return this;
- }
- } else {
- return new Integer(-1);
- }
+ }
+ });
+ }
+
+ /**
+ * We can do that using tail recursion as well.
+ *
+ * Again, the anonymous Function implemenation
+ * holds the "continuation" state.
+ */
+ public void testTailRecursive2() {
+ chopTest(new BaseBinaryChop() {
+ public int find(final Object seeking, final List list) {
+ return ((Number)Algorithms.recurse(new Function() {
+ public Object evaluate() {
+ if(sublist.isEmpty()) {
+ return BaseBinaryChop.NEGATIVE_ONE;
+ } if(sublist.size() == 1) {
+ return (BaseBinaryChop.equals(sublist,0,seeking) ?
+ new Integer(offset) :
+ BaseBinaryChop.NEGATIVE_ONE);
+ } else {
+ int mid = sublist.size() / 2;
+ if(greaterThan(sublist,mid,seeking)) {
+ sublist = sublist.subList(0,mid);
+ } else {
+ sublist = sublist.subList(mid,sublist.size());
+ offset += mid;
}
- int high = list.size();
- int low = 0;
- })).intValue();
- }
- });
- }
+ return this;
+ }
+ }
+ int offset = 0;
+ List sublist = list;
+ })).intValue();
+ }
+ });
+ }
+
}
1.2 +16 -2 jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/kata/two/BaseBinaryChop.java
Index: BaseBinaryChop.java
===================================================================
RCS file: /home/cvs/jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/kata/two/BaseBinaryChop.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- BaseBinaryChop.java 1 Dec 2003 07:30:24 -0000 1.1
+++ BaseBinaryChop.java 1 Dec 2003 19:22:41 -0000 1.2
@@ -79,5 +79,19 @@
return find(seeking, Arrays.asList(in));
}
+ protected static int compare(List list, int index, Object obj) {
+ return ((Comparable)list.get(index)).compareTo(obj);
+ }
+
+ protected static boolean greaterThan(List list, int index, Object obj) {
+ return compare(list,index,obj) > 0;
+ }
+
+ protected static boolean equals(List list, int index, Object obj) {
+ return compare(list,index,obj) == 0;
+ }
+
+ protected static Integer NEGATIVE_ONE = new Integer(-1);
+
public abstract int find(Object seeking, List in);
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org