From 212a597838417f13a2371e9029066bd08cf9c2bb Mon Sep 17 00:00:00 2001 From: adash Date: Thu, 18 Jun 2009 19:14:48 +0000 Subject: [PATCH] added Quicksort for sorting array of Objects equivalent for C pointer sorting --- .../src/Benchmarks/SingleTM/Bayes/Adtree.java | 2 - .../Benchmarks/SingleTM/Bayes/IntVector.java | 13 +- .../Benchmarks/SingleTM/Bayes/Learner.java | 3 +- .../Benchmarks/SingleTM/common/BitMap.java | 4 +- .../Benchmarks/SingleTM/common/QuickSort.java | 187 +++++++++++++++--- .../Benchmarks/SingleTM/common/Vector_t.java | 1 + 6 files changed, 166 insertions(+), 44 deletions(-) diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/Adtree.java b/Robust/src/Benchmarks/SingleTM/Bayes/Adtree.java index d6c7cb3e..24be2441 100644 --- a/Robust/src/Benchmarks/SingleTM/Bayes/Adtree.java +++ b/Robust/src/Benchmarks/SingleTM/Bayes/Adtree.java @@ -221,7 +221,6 @@ public class Adtree { int numVar = dataPtr.numVar; for (int v = (index + 1); v < numVar; v++) { - //System.out.println("DEBUG: v= " +v+ " numVar= " + numVar+ " calling makeVary"); AdtreeVary varyPtr = makeVary(parentIndex, v, start, numRecord, dataPtr); boolean status; @@ -231,7 +230,6 @@ public class Adtree { } } - //System.out.println("DEBUG: End of makeNode"); return nodePtr; } diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/IntVector.java b/Robust/src/Benchmarks/SingleTM/Bayes/IntVector.java index 239dd06b..25c62465 100644 --- a/Robust/src/Benchmarks/SingleTM/Bayes/IntVector.java +++ b/Robust/src/Benchmarks/SingleTM/Bayes/IntVector.java @@ -10,10 +10,9 @@ public class IntVector { int size; int capacity; int[] elements; - QuickSort qsort; public IntVector() { - qsort = new QuickSort(); + } /* ============================================================================= @@ -119,16 +118,6 @@ public class IntVector { size = 0; } - /* ============================================================================= - * Vector_sort - * ============================================================================= - */ - public void - vector_sort () - { - qsort.sort(elements, 0, (elements.length - 1)); - } - /* ============================================================================= * Vector_copy * ============================================================================= diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/Learner.java b/Robust/src/Benchmarks/SingleTM/Bayes/Learner.java index a7104b83..e1009ca1 100644 --- a/Robust/src/Benchmarks/SingleTM/Bayes/Learner.java +++ b/Robust/src/Benchmarks/SingleTM/Bayes/Learner.java @@ -177,7 +177,6 @@ public class Learner { { Learner learnerPtr = new Learner(); - //learnerPtr = (learner_t*)malloc(sizeof(learner_t)); if (learnerPtr != null) { learnerPtr.adtreePtr = adtreePtr; learnerPtr.netPtr = Net.net_alloc(dataPtr.numVar); @@ -1533,6 +1532,7 @@ public class Learner { int numTotalParent = 0; float logLikelihood = 0.0f; + //System.out.println("DEBUG: before logLikelihood= " + logLikelihood); for (int v = 0; v < numVar; v++) { @@ -1554,6 +1554,7 @@ public class Learner { logLikelihood += localLogLikelihood; } + //System.out.println("DEBUG: after logLikelihood= " + logLikelihood); queryVectorPtr.vector_free(); parentQueryVectorPtr.vector_free(); queries = null; diff --git a/Robust/src/Benchmarks/SingleTM/common/BitMap.java b/Robust/src/Benchmarks/SingleTM/common/BitMap.java index 25cb8fe7..44708e2b 100644 --- a/Robust/src/Benchmarks/SingleTM/common/BitMap.java +++ b/Robust/src/Benchmarks/SingleTM/common/BitMap.java @@ -215,11 +215,9 @@ public class BitMap { bitmap_findClear (int startIndex) { int tmp_numBit = numBit; - int[] tmp_bits = bits; - //uint_t* bits = bitmapPtr.bits; for (int i = Math.imax(startIndex, 0); i < tmp_numBit; i++) { - int val = tmp_bits[i/NUM_BIT_PER_WORD] & (1 << (i % NUM_BIT_PER_WORD)); + int val = bits[i/NUM_BIT_PER_WORD] & (1 << (i % NUM_BIT_PER_WORD)); if(val == 0) { return i; } diff --git a/Robust/src/Benchmarks/SingleTM/common/QuickSort.java b/Robust/src/Benchmarks/SingleTM/common/QuickSort.java index 4ee8271a..3c211cd5 100644 --- a/Robust/src/Benchmarks/SingleTM/common/QuickSort.java +++ b/Robust/src/Benchmarks/SingleTM/common/QuickSort.java @@ -1,43 +1,178 @@ public class QuickSort { + public QuickSort() { - public QuickSort() { + } + /** + * Sort an array of Objects into ascending order. The sort algorithm is an optimised + * quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's + * "Engineering a Sort Function", Software-Practice and Experience, Vol. + * 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n) + * performance on many arrays that would take quadratic time with a standard + * quicksort. + * + * @param a the array to sort + */ + public void sort(Object[] a) + { + qsort(a, 0, a.length); } - public void swap (int A[], int x, int y) + public void sort(Object[] a, int fromIndex, int toIndex) { - int temp = A[x]; - A[x] = A[y]; - A[y] = temp; + qsort(a, fromIndex, toIndex); } - // Reorganizes the given list so all elements less than the first are - // before it and all greater elements are after it. - public int partition(int a[], int left, int right) + private int med3(int a, int b, int c, Object[]d) { - int i = left - 1; - int j = right; - while (true) { - while (less(a[++i], a[right])) // find item on left to swap - ; // a[right] acts as sentinel - while (less(a[right], a[--j])) // find item on right to swap - if (j == left) break; // don't go out-of-bounds - if (i >= j) break; // check if pointers cross - swap(a, i, j); // swap two elements into place + if(less(d[a], d[b])) { + if(less(d[b], d[c])) { + return b; + } else { + if(less(d[a], d[c])) + return c; + else + return a; + } + } else { + if(less(d[c], d[b])) { + return b; + } else { + if(less(d[c], d[a])) + return c; + else + return a; + } + } + } + + private void swap(int i, int j, Object[] a) + { + Object c = a[i]; + a[i] = a[j]; + a[j] = c; + } + + private void qsort(Object[] a, int start, int n) + { + // use an insertion sort on small arrays + if (n <= 7) + { + for (int i = start + 1; i < start + n; i++) + for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) + swap(j, j - 1, a); + return; + } + + int pm = n / 2; // small arrays, middle element + if (n > 7) + { + int pl = start; + int pn = start + n - 1; + + if (n > 40) + { // big arrays, pseudomedian of 9 + int s = n / 8; + pl = med3(pl, pl + s, pl + 2 * s, a); + pm = med3(pm - s, pm, pm + s, a); + pn = med3(pn - 2 * s, pn - s, pn, a); + } + pm = med3(pl, pm, pn, a); // mid-size, med of 3 + } + + int pa, pb, pc, pd, pv; + int r; + + pv = start; + swap(pv, pm, a); + pa = pb = start; + pc = pd = start + n - 1; + + while(true) + { + while (pb <= pc && (r = diff(a[pb],a[pv])) <= 0) + { + if (r == 0) + { + swap(pa, pb, a); + pa++; + } + pb++; + } + while (pc >= pb && (r = diff(a[pc],a[pv])) >= 0) + { + if (r == 0) + { + swap(pc, pd, a); + pd--; + } + pc--; + } + if (pb > pc) + break; + swap(pb, pc, a); + pb++; + pc--; } - swap(a, i, right); // swap with partition element - return i; + int pn = start + n; + int s; + s = Math.imin(pa - start, pb - pa); + vecswap(start, pb - s, s, a); + s = Math.imin(pd - pc, pn - pd - 1); + vecswap(pb, pn - s, s, a); + if ((s = pb - pa) > 1) + qsort(a, start, s); + if ((s = pd - pc) > 1) + qsort(a, pn - s, s); } - public void sort(int A[], int f, int l) + private void vecswap(int i, int j, int n, Object[] a) { - if (f >= l) return; - int pivot_index = partition(A, f, l); - sort(A, f, pivot_index); - sort(A, pivot_index+1, l); + for (; n > 0; i++, j++, n--) + swap(i, j, a); + } + + public boolean less(Object x, Object y) { + Query aQueryPtr = (Query) x; + Query bQueryPtr = (Query) y; + if(aQueryPtr.index < bQueryPtr.index) + return true; + return false; + } + + public int diff(Object x, Object y) { + Query aQueryPtr = (Query) x; + Query bQueryPtr = (Query) y; + return (aQueryPtr.index - bQueryPtr.index); } - boolean less(int x, int y) { - return(x