Changeset 3081

Timestamp:

01/09/08 21:29:13 (11 months ago)

Author:

sean

Message:

Added some heuristics to the sort routine to address performance issues. It now matches introSort for the "median-of-3 killer" test and matches the built-in sort for the word count test, each of which were previously the respective winners in those tests. This closes #571.

Files:

• trunk/tango/core/Array.d (modified) (3 diffs)

trunk/tango/core/Array.d

@@ -2013 +2013 @@
-            }
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-            {
-                if( r <= l )
-                    return;
+
+                // HEURISTIC: Use insertion sort for sufficiently small arrays.
+                enum { MIN_LENGTH = 80 }
+                if( r - l < MIN_LENGTH )
+                    return insertionSort( l, r );
+
+                // HEURISTIC: If the recursion depth is too great, assume this
+                //            is a worst-case array and fail to heap sort.
+                if( d-- == 0 )
+                {
+                    makeHeap( buf[l .. r+1], pred );
+                    sortHeap( buf[l .. r+1], pred );
+                    return;
+                }
+
+                // HEURISTIC: Use the median-of-3 value as a pivot.  Swap this
+                //            into r so quicksort remains untouched.
+                exch( r, medianOf( l, l + (r - l) / 2, r ) );
-
-                // This implementation of quicksort improves upon the classic
@@ -2064 +2128 @@
-                    for( size_t k = l; k < p; k++, j-- )
-                        exch( k, j );
-
+, d
-                }
-                if( ++i < q )
@@ -2070 +2134 @@
-                    for( size_t k = r - 1; k >= q; k--, i++ )
-                        exch( k, i );
-
+, d
-                }
-            }
-
+            size_t maxDepth( size_t x )
+            {
+                size_t d = 0;
+
+                do
+                {
+                    ++d;
+                    x /= 2;
+                } while( x > 1 );
+                return d * 2; // same as "floor( log( x ) / log( 2 ) ) * 2"
+            }
+
-            if( buf.length > 1 )
-            {
-
+, maxDepth( buf.length )
-            }
-        }