harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From telli...@apache.org
Subject svn commit: r419207 - /incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/Arrays.java
Date Wed, 05 Jul 2006 10:44:26 GMT
Author: tellison
Date: Wed Jul  5 03:44:24 2006
New Revision: 419207

URL: http://svn.apache.org/viewvc?rev=419207&view=rev
Log:
Apply patch HARMONY-636 (performance enhancement for Arrays.sort(Object[]...))

Modified:
    incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/Arrays.java

Modified: incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/Arrays.java
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/Arrays.java?rev=419207&r1=419206&r2=419207&view=diff
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/Arrays.java
(original)
+++ incubator/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/Arrays.java
Wed Jul  5 03:44:24 2006
@@ -25,6 +25,9 @@
  */
 public class Arrays {
 
+     /* Specifies when to switch to insertion sort */
+     private static final int SIMPLE_LENGTH = 7;
+
     private static class ArrayList<E> extends AbstractList<E> implements
             List<E>, Serializable, RandomAccess {
 
@@ -2146,39 +2149,478 @@
         sort(start, end, array);
     }
 
-    @SuppressWarnings("unchecked")
-    private static void sort(int start, int end, Object[] array) {
-        int middle = (start + end) / 2;
-        if (start + 1 < middle) {
-            sort(start, middle, array);
-        }
-        if (middle + 1 < end) {
-            sort(middle, end, array);
-        }
-        if (start + 1 >= end) {
-            return; // this case can only happen when this method is called by
-        }
-        // the user
-        if (((Comparable<Object>) array[middle - 1]).compareTo(array[middle]) <=
0) {
+    private static void sort(int fromIndex, int toIndex, Object[] array) {
+        int length = toIndex - fromIndex;
+        if (length <= 0) {
             return;
         }
-        if (start + 2 == end) {
-            Object temp = array[start];
-            array[start] = array[middle];
-            array[middle] = temp;
-            return;
-        }
-        int i1 = start, i2 = middle, i3 = 0;
-        Object[] merge = new Object[end - start];
-        while (i1 < middle && i2 < end) {
-            merge[i3++] = ((Comparable<Object>) array[i1]).compareTo(array[i2]) <=
0 ? array[i1++]
-                    : array[i2++];
-        }
-        if (i1 < middle) {
-            System.arraycopy(array, i1, merge, i3, middle - i1);
-        }
-        System.arraycopy(merge, 0, array, start, i2 - start);
-    }
+        if (array instanceof String[]) {
+            stableStringSort((String[]) array, fromIndex, toIndex);
+        } else {
+            Object[] out = new Object[toIndex];
+            System.arraycopy(array, fromIndex, out, fromIndex, length);
+            mergeSort(out, array, fromIndex, toIndex);
+        }
+    }
+
+    /**
+      * Swaps the elements at the specified positions in the specified array.
+      *
+      * @param a -
+      *            the index of one element to be swapped.
+      * @param b -
+      *            the index of the other element to be swapped.
+      * @param arr -
+      *            the array in which to swap elements.
+      */
+     private static void swap(int a, int b, Object[] arr) {
+         Object tmp = arr[a];
+         arr[a] = arr[b];
+         arr[b] = tmp;
+     }
+
+     /**
+      * Sorts the specified range of the specified array of objects. The range to
+      * be sorted extends from index fromIndex, inclusive, to index toIndex,
+      * exclusive. (If fromIndex==toIndex, the range to be sorted is empty.) This
+      * sort is guaranteed to be stable: equal elements will not be reordered as
+      * a result of the sort.
+      *
+      * The sorting algorithm is a mergesort with exponential search (in which
+      * the merge is performed by exponential search). This algorithm offers
+      * guaranteed n*log(n) performance and in average case faster then any
+      * mergesort in which the merge is performed by linear search.
+      *
+      * @param in -
+      *            the array for sorting.
+      * @param out -
+      *            the result, sorted array.
+      * @param fromIndex -
+      *            the index of the first element (inclusive) to be sorted.
+      * @param toIndex -
+      *            the index of the last element (exclusive) to be sorted.
+      */
+     private static void mergeSort(Object[] in, Object[] out, int fromIndex,
+             int toIndex) {
+         int len = toIndex - fromIndex;
+         //use insertion sort for small arrays
+         if (len <= SIMPLE_LENGTH) {
+             for (int i = fromIndex + 1; i < toIndex; i++) {
+                 Comparable current = (Comparable) out[i];
+                 Object prev = out[i - 1];
+                 if (current.compareTo(prev) < 0) {
+                     int j = i;
+                     do {
+                        out[j--] = prev;
+                     } while (j > fromIndex
+                             && current.compareTo(prev = out[j - 1]) < 0);
+                     out[j] = current;
+                 }
+             }
+             return;
+         }
+         int med = (toIndex + fromIndex) >> 1;
+         mergeSort(out, in, fromIndex, med);
+         mergeSort(out, in, med, toIndex);
+
+         // merging
+
+         //if arrays are already sorted - no merge
+         if (((Comparable) in[med]).compareTo(in[med - 1]) >= 0) {
+             System.arraycopy(in, fromIndex, out, fromIndex, len);
+             return;
+         }
+         int r = med, i = fromIndex;
+
+         // use merging with exponential search
+         do {
+             Comparable fromVal = (Comparable) in[fromIndex];
+             Comparable rVal = (Comparable) in[r];
+             if (fromVal.compareTo(rVal) <= 0) {
+                 int l_1 = find(in,rVal,-1,fromIndex+1,med-1);
+                 int toCopy = l_1 - fromIndex + 1;
+                 System.arraycopy(in, fromIndex, out, i, toCopy);
+                 i += toCopy;
+                 out[i++] = rVal;
+                 r++;
+                 fromIndex = l_1+1;
+             } else {
+                 int r_1 = find(in,fromVal,0,r+1,toIndex-1);
+                 int toCopy = r_1 - r + 1;
+                 System.arraycopy(in, r, out, i, toCopy);
+                 i += toCopy;
+                 out[i++] = fromVal;
+                 fromIndex++;
+                 r = r_1+1;
+             }
+         } while ((toIndex - r) > 0 && (med - fromIndex) > 0);
+
+        // copy rest of array
+         if ((toIndex - r) <= 0) {
+             System.arraycopy(in, fromIndex, out, i, med - fromIndex);
+         } else {
+             System.arraycopy(in, r, out, i, toIndex - r);
+         }
+     }
+
+     /**
+      * Sorts the specified range of the specified array of objects. The range to
+      * be sorted extends from index fromIndex, inclusive, to index toIndex,
+      * exclusive. (If fromIndex==toIndex, the range to be sorted is empty.) This
+      * sort is guaranteed to be stable: equal elements will not be reordered as
+      * a result of the sort.
+      *
+      * The sorting algorithm is a mergesort with exponential search (in which
+      * the merge is performed by exponential search). This algorithm offers
+      * guaranteed n*log(n) performance and in average case faster then any
+      * mergesort in which the merge is performed by linear search.
+      *
+      * @param in -
+      *            the array for sorting.
+      * @param out -
+      *            the result, sorted array.
+      * @param fromIndex -
+      *            the index of the first element (inclusive) to be sorted.
+      * @param toIndex -
+      *            the index of the last element (exclusive) to be sorted.
+      * @param c -
+      *            the comparator to determine the order of the array.
+      */
+     private static void mergeSort(Object[] in, Object[] out, int fromIndex,
+             int toIndex, Comparator c) {
+         int len = toIndex - fromIndex;
+         //use insertion sort for small arrays
+         if (len <= SIMPLE_LENGTH) {
+             for (int i = fromIndex + 1; i < toIndex; i++) {
+                 Object current = out[i];
+                 Object prev = out[i - 1];
+                 if (c.compare(prev, current) > 0) {
+                     int j = i;
+                     do {
+                        out[j--] = prev;
+                     } while (j > fromIndex
+                             && (c.compare(prev = out[j - 1], current) > 0));
+                     out[j] = current;
+                 }
+             }
+             return;
+         }
+         int med = (toIndex + fromIndex) >> 1;
+         mergeSort(out, in, fromIndex, med,c);
+         mergeSort(out, in, med, toIndex,c);
+
+         // merging
+
+         //if arrays are already sorted - no merge
+         if (c.compare(in[med],in[med - 1]) >= 0) {
+             System.arraycopy(in, fromIndex, out, fromIndex, len);
+             return;
+         }
+         int r = med, i = fromIndex;
+
+         // use merging with exponential search
+         do {
+             Object fromVal =  in[fromIndex];
+             Object rVal =  in[r];
+             if (c.compare(fromVal,rVal) <= 0) {
+                 int l_1 = find(in,rVal,-1,fromIndex+1,med-1,c);
+                 int toCopy = l_1 - fromIndex + 1;
+                 System.arraycopy(in, fromIndex, out, i, toCopy);
+                 i += toCopy;
+                 out[i++] = rVal;
+                 r++;
+                 fromIndex = l_1+1;
+             } else {
+                 int r_1 = find(in,fromVal,0,r+1,toIndex-1,c);
+                 int toCopy = r_1 - r + 1;
+                 System.arraycopy(in, r, out, i, toCopy);
+                 i += toCopy;
+                 out[i++] = fromVal;
+                 fromIndex++;
+                 r = r_1+1;
+             }
+         } while ((toIndex - r) > 0 && (med - fromIndex) > 0);
+
+        // copy rest of array
+         if ((toIndex - r) <= 0) {
+             System.arraycopy(in, fromIndex, out, i, med - fromIndex);
+         } else {
+             System.arraycopy(in, r, out, i, toIndex - r);
+         }
+     }
+
+     /**
+      * Finds the place of specified range of specified sorted array, where the
+      * element should be inserted for getting sorted array. Uses expionential
+      * search algorithm.
+      *
+      * @param arr - the array with already sorted range
+      *
+      * @param val - object to be inserted
+      *
+      * @param l - the index of the first element (inclusive)
+      *
+      * @param r - the index of the last element (inclusive)
+      *
+      * @param bnd - possible values 0,-1. "-1" - val is located at index more
+      * then elements equals to val. "0" - val is located at index less then
+      * elements equals to val.
+      *
+      */
+     private static int find(Object[] arr, Comparable val, int bnd, int l, int r){
+         int m = l ;
+         int d = 1;
+         while (m <= r) {
+             if (val.compareTo(arr[m]) > bnd) {
+                l=m+1;
+             } else {
+                r=m-1;
+                break;
+             }
+             m+=d;
+             d<<=1;
+         }
+         while (l <= r) {
+             m = (l + r) >> 1;
+             if (val.compareTo(arr[m]) > bnd) {
+                  l = m+1;
+             } else {
+                  r = m-1;
+             }
+         }
+         return l-1;
+     }
+
+     /**
+      * Finds the place of specified range of specified sorted array, where the
+      * element should be inserted for getting sorted array. Uses expionential
+      * search algorithm.
+      *
+      * @param arr - the array with already sorted range
+      *
+      * @param val - object to be inserted
+      *
+      * @param l - the index of the first element (inclusive)
+      *
+      * @param r - the index of the last element (inclusive)
+      *
+      * @param bnd - possible values 0,-1. "-1" - val is located at index more
+      * then elements equals to val. "0" - val is located at index less then
+      * elements equals to val.
+      *
+      * @param c -
+      *            the comparator to determine the order of the array.
+      */
+     private static int find(Object[] arr, Object val, int bnd, int l,
+             int r, Comparator c){
+         int m = l ;
+         int d = 1;
+         while (m <= r) {
+             if (c.compare(val,arr[m]) > bnd) {
+                l=m+1;
+             } else {
+                r=m-1;
+                break;
+             }
+             m+=d;
+             d<<=1;
+         }
+         while (l <= r) {
+             m = (l + r) >> 1;
+             if (c.compare(val,arr[m]) > bnd) {
+                  l = m+1;
+             } else {
+                  r = m-1;
+             }
+         }
+         return l-1;
+     }
+
+     /*
+      * returns the median index.
+      */
+     private static int medChar(int a, int b, int c, String[] arr, int id) {
+         int ac = charAt(arr[a], id);
+         int bc = charAt(arr[b], id);
+         int cc = charAt(arr[c], id);
+         return ac < bc ? (bc < cc ? b : (ac < cc ? c : a))
+                 : (bc < cc ? (ac < cc ? a : c) : b);
+
+     }
+
+     /*
+      * Returns the char value at the specified index of string or -1 if the
+      * index more than the length of this string.
+      */
+    private static int charAt(String str, int i) {
+         if (i >= str.length()) {
+             return -1;
+         }
+         return str.charAt(i);
+     }
+
+     /**
+      * Copies object from one array to another array with reverse of objects
+      * order. Source and destination arrays may be the same.
+      *
+      * @param src -
+      *            the source array.
+      * @param from -
+      *            starting position in the source array.
+      * @param dst -
+      *            the destination array.
+      * @param to -
+      *            starting position in the destination array.
+      * @param len -
+      *            the number of array elements to be copied.
+      */
+    private static void copySwap(Object[] src, int from, Object[] dst, int to,
+             int len) {
+         if (src == dst && from + len > to) {
+             int new_to = to + len - 1;
+             for (; from < to; from++, new_to--, len--) {
+                 dst[new_to] = src[from];
+             }
+             for (; len > 1; from++, new_to--, len -= 2) {
+                 swap(from, new_to, dst);
+             }
+
+         } else {
+             to = to + len - 1;
+             for (; len > 0; from++, to--, len--) {
+                 dst[to] = src[from];
+             }
+         }
+     }
+
+     /**
+      * Sorts the specified range of the specified array of String.
+      *
+      * @param arr -
+      *            the array to be sorted
+      * @param fromIndex -
+      *            the index of the first element (inclusive) to be sorted.
+      * @param toIndex -
+      *            the index of the last element (exclusive) to be sorted.
+      */
+     private static void stableStringSort(String[] arr, int fromIndex,
+             int toIndex) {
+         stableStringSort(arr, arr, new String[toIndex], fromIndex, toIndex, 0);
+     }
+
+     /**
+      * Sorts the specified range of the specified array of String. Use stable
+      * ternary quick sort algorithm.
+      *
+      * @param arr -
+      *            the array to be sorted
+      * @param src -
+      *            auxilary array
+      * @param dst -
+      *            auxilary array
+      * @param fromIndex -
+      *            the index of the first element (inclusive) to be sorted.
+      * @param toIndex -
+      *            the index of the last element (exclusive) to be sorted.
+      * @param chId -
+      *            index of char for current sorting
+      */
+     private static void stableStringSort(String[] arr, String[] src,
+             String[] dst, int fromIndex, int toIndex, int chId) {
+         int length = toIndex - fromIndex;
+         //use insertion sort fro small arrays
+         if (length < SIMPLE_LENGTH) {
+             if (src == arr) {
+                 for (int i = fromIndex + 1; i < toIndex; i++) {
+                     String current = arr[i];
+                     String prev = arr[i - 1];
+                     if (current.compareTo(prev) < 0) {
+                         int j = i;
+                         do {
+                             arr[j--] = prev;
+                         } while (j > fromIndex
+                                 && current.compareTo(prev = arr[j - 1]) < 0);
+                         arr[j] = current;
+                     }
+                 }
+             } else {
+                 int end = toIndex - 1;
+                 dst[fromIndex] = src[end--];
+                 for (int i = fromIndex + 1; i < toIndex; i++, end--) {
+                     String current = (String) src[end];
+                     String prev;
+                     int j = i;
+                     while (j > fromIndex && current.compareTo(prev = dst[j -
1]) < 0) {
+                         dst[j--] = prev;
+                     }
+                     dst[j] = current;
+                 }
+             }
+             return;
+         }
+         // aproximate median
+         int s;
+         int mid = fromIndex + length / 2;
+         int lo = fromIndex;
+         int hi = toIndex - 1;
+         if (length > 40) {
+             s = length / 8;
+             lo = medChar(lo, lo + s, lo + s * 2, src, chId);
+             mid = medChar(mid - s, mid, mid + s, src, chId);
+             hi = medChar(hi, hi - s, hi - s * 2, src, chId);
+         }
+         mid = medChar(lo, mid, hi, src, chId);
+         //  median finded
+         // create 4 pointers <a (in star of src) ,
+         //                      =b(in start of dst), >c (in end of dst)
+         // i - current element;
+         int midVal = charAt(src[mid], chId);
+         int a, b, c;
+         a = b = fromIndex;
+         c = toIndex - 1;
+         int cmp;
+
+         for (int i = fromIndex; i < toIndex; i++) {
+             String el = src[i];
+             cmp = charAt(el, chId) - midVal;
+             if (cmp < 0) {
+                 src[a] = el;
+                 a++;
+             } else if (cmp > 0) {
+                 dst[c] = el;
+                 c--;
+             } else {
+                 dst[b] = el;
+                 b++;
+             }
+         }
+
+         s = b - fromIndex;
+         if (s > 0) {
+             if (arr == src) {
+                 System.arraycopy(dst, fromIndex, arr, a, s);
+             } else {
+                 copySwap(dst, fromIndex, arr, a, s);
+             }
+
+             if (b >= toIndex && midVal == -1) {
+                 return;
+             }
+             stableStringSort(arr, arr, arr == dst ? src : dst, a, a + s,
+                     chId + 1);
+         }
+
+         s = a - fromIndex;
+         if (s > 0) {
+             stableStringSort(arr, src, dst, fromIndex, a, chId);
+         }
+
+         c++;
+         s = toIndex - c;
+         if (s > 0) {
+             stableStringSort(arr, dst, src, c, toIndex, chId);
+         }
+     }
 
     /**
      * Sorts the specified range in the array using the specified Comparator.
@@ -2213,40 +2655,13 @@
     private static <T> void sort(int start, int end, T[] array,
             Comparator<? super T> comparator) {
         if (comparator == null) {
-            sort(start, end, array);
-            return;
-        }
-
-        int middle = (start + end) / 2;
-        if (start + 1 < middle) {
-            sort(start, middle, array, comparator);
-        }
-        if (middle + 1 < end) {
-            sort(middle, end, array, comparator);
-        }
-        if (start + 1 >= end) {
-            return; // this case can only happen when this method is called by
-        }
-        // the user
-        if (comparator.compare(array[middle - 1], array[middle]) <= 0) {
-            return;
-        }
-        if (start + 2 == end) {
-            T temp = array[start];
-            array[start] = array[middle];
-            array[middle] = temp;
-            return;
-        }
-        int i1 = start, i2 = middle, i3 = 0;
-        Object[] merge = new Object[end - start];
-        while (i1 < middle && i2 < end) {
-            merge[i3++] = comparator.compare(array[i1], array[i2]) <= 0 ? array[i1++]
-                    : array[i2++];
-        }
-        if (i1 < middle) {
-            System.arraycopy(array, i1, merge, i3, middle - i1);
+           sort(start, end, array);
+        } else {
+           int length = end - start;
+           Object[] out = new Object[end];
+           System.arraycopy(array, start, out, start, length);
+           mergeSort(out, array, start, end, comparator);
         }
-        System.arraycopy(merge, 0, array, start, i2 - start);
     }
 
     /**



Mime
View raw message