diff options
author | Tim Peters <tim.peters@gmail.com> | 2002-07-19 07:05:44 (GMT) |
---|---|---|
committer | Tim Peters <tim.peters@gmail.com> | 2002-07-19 07:05:44 (GMT) |
commit | 330f9e9581a5d97a0560f10182ae882b07eb3c66 (patch) | |
tree | 91f26b00dd4376e7734673e561b82443dd11442e /Objects/listobject.c | |
parent | 8235ea1c3a5c57c9279668b5bff3d5f021ceb2d5 (diff) | |
download | cpython-330f9e9581a5d97a0560f10182ae882b07eb3c66.zip cpython-330f9e9581a5d97a0560f10182ae882b07eb3c66.tar.gz cpython-330f9e9581a5d97a0560f10182ae882b07eb3c66.tar.bz2 |
More sort cleanup: Moved the special cases from samplesortslice into
listsort. If the former calls itself recursively, they're a waste of
time, since it's called on a random permutation of a random subset of
elements. OTOH, for exactly the same reason, they're an immeasurably
small waste of time (the odds of finding exploitable order in a random
permutation are ~= 0, so the special-case loops looking for order give
up quickly). The point is more for conceptual clarity.
Also changed some "assert comments" into real asserts; when this code
was first written, Python.h didn't supply assert.h.
Diffstat (limited to 'Objects/listobject.c')
-rw-r--r-- | Objects/listobject.c | 138 |
1 files changed, 73 insertions, 65 deletions
diff --git a/Objects/listobject.c b/Objects/listobject.c index bc79cd1..7d3d48f 100644 --- a/Objects/listobject.c +++ b/Objects/listobject.c @@ -1005,43 +1005,10 @@ samplesortslice(PyObject **lo, PyObject **hi, PyObject *compare) int n, extra, top, extraOnRight; struct SamplesortStackNode stack[STACKSIZE]; - /* assert lo <= hi */ + assert(lo <= hi); n = hi - lo; - - /* ---------------------------------------------------------- - * Special cases - * --------------------------------------------------------*/ - if (n < 2) - return 0; - - /* Set r to the largest value such that [lo,r) is sorted. - This catches the already-sorted case, the all-the-same - case, and the appended-a-few-elements-to-a-sorted-list case. - If the array is unsorted, we're very likely to get out of - the loop fast, so the test is cheap if it doesn't pay off. - */ - /* assert lo < hi */ - for (r = lo+1; r < hi; ++r) { - IFLT(*r, *(r-1)) - break; - } - /* [lo,r) is sorted, [r,hi) unknown. Get out cheap if there are - few unknowns, or few elements in total. */ - if (hi - r <= MAXMERGE || n < MINSIZE) - return binarysort(lo, hi, r, compare); - - /* Check for the array already being reverse-sorted. Typical - benchmark-driven silliness <wink>. */ - /* assert lo < hi */ - for (r = lo+1; r < hi; ++r) { - IFLT(*(r-1), *r) - break; - } - if (hi - r <= MAXMERGE) { - /* Reverse the reversed prefix, then insert the tail */ - reverse_slice(lo, r); - return binarysort(lo, hi, r, compare); - } + if (n < MINSIZE) + return binarysort(lo, hi, lo, compare); /* ---------------------------------------------------------- * Normal case setup: a large array without obvious pattern. @@ -1093,7 +1060,7 @@ samplesortslice(PyObject **lo, PyObject **hi, PyObject *compare) * Partition [lo, hi), and repeat until out of work. * --------------------------------------------------------*/ for (;;) { - /* assert lo <= hi, so n >= 0 */ + assert(lo <= hi); n = hi - lo; /* We may not want, or may not be able, to partition: @@ -1103,8 +1070,8 @@ samplesortslice(PyObject **lo, PyObject **hi, PyObject *compare) */ if (n < MINPARTITIONSIZE || extra == 0) { if (n >= MINSIZE) { - /* assert extra == 0 - This is rare, since the average size + assert(extra == 0); + /* This is rare, since the average size of a final block is only about ln(original n). */ if (samplesortslice(lo, hi, compare) < 0) @@ -1184,7 +1151,7 @@ samplesortslice(PyObject **lo, PyObject **hi, PyObject *compare) duplicates later. */ l = lo + 1; r = hi - 1; - /* assert lo < l < r < hi (small n weeded out above) */ + assert(lo < l && l < r && r < hi); do { /* slide l right, looking for key >= pivot */ @@ -1208,9 +1175,8 @@ samplesortslice(PyObject **lo, PyObject **hi, PyObject *compare) } while (l < r); - /* assert lo < r <= l < hi - assert r == l or r+1 == l - everything to the left of l is < pivot, and + assert(lo < r && r <= l && l < hi); + /* everything to the left of l is < pivot, and everything to the right of r is >= pivot */ if (l == r) { @@ -1219,13 +1185,12 @@ samplesortslice(PyObject **lo, PyObject **hi, PyObject *compare) else --r; } - /* assert lo <= r and r+1 == l and l <= hi - assert r == lo or a[r] < pivot - assert a[lo] is pivot - assert l == hi or a[l] >= pivot - Swap the pivot into "the middle", so we can henceforth - ignore it. - */ + assert(lo <= r && r+1 == l && l <= hi); + /* assert r == lo or a[r] < pivot */ + assert(*lo == pivot); + /* assert l == hi or a[l] >= pivot */ + /* Swap the pivot into "the middle", so we can henceforth + ignore it. */ *lo = *r; *r = pivot; @@ -1250,13 +1215,12 @@ samplesortslice(PyObject **lo, PyObject **hi, PyObject *compare) ++l; } - /* assert lo <= r < l <= hi - Partitions are [lo, r) and [l, hi) */ - - /* push fattest first; remember we still have extra PPs + assert(lo <= r && r < l && l <= hi); + /* Partitions are [lo, r) and [l, hi) + :ush fattest first; remember we still have extra PPs to the left of the left chunk and to the right of the right chunk! */ - /* assert top < STACKSIZE */ + assert(top < STACKSIZE); if (r - lo <= hi - l) { /* second is bigger */ stack[top].lo = l; @@ -1283,33 +1247,77 @@ samplesortslice(PyObject **lo, PyObject **hi, PyObject *compare) return -1; } -#undef IFLT - static PyTypeObject immutable_list_type; static PyObject * listsort(PyListObject *self, PyObject *args) { - int err; + int k; PyObject *compare = NULL; + PyObject **hi, **p; PyTypeObject *savetype; if (args != NULL) { if (!PyArg_ParseTuple(args, "|O:sort", &compare)) return NULL; } + savetype = self->ob_type; + if (self->ob_size < 2) { + k = 0; + goto done; + } + self->ob_type = &immutable_list_type; - err = samplesortslice(self->ob_item, - self->ob_item + self->ob_size, - compare); - self->ob_type = savetype; - if (err < 0) + hi = self->ob_item + self->ob_size; + + /* Set p to the largest value such that [lo, p) is sorted. + This catches the already-sorted case, the all-the-same + case, and the appended-a-few-elements-to-a-sorted-list case. + If the array is unsorted, we're very likely to get out of + the loop fast, so the test is cheap if it doesn't pay off. + */ + for (p = self->ob_item + 1; p < hi; ++p) { + IFLT(*p, *(p-1)) + break; + } + /* [lo, p) is sorted, [p, hi) unknown. Get out cheap if there are + few unknowns, or few elements in total. */ + if (hi - p <= MAXMERGE || self->ob_size < MINSIZE) { + k = binarysort(self->ob_item, hi, p, compare); + goto done; + } + + /* Check for the array already being reverse-sorted, or that with + a few elements tacked on to the end. */ + for (p = self->ob_item + 1; p < hi; ++p) { + IFLT(*(p-1), *p) + break; + } + /* [lo, p) is reverse-sorted, [p, hi) unknown. */ + if (hi - p <= MAXMERGE) { + /* Reverse the reversed prefix, then insert the tail */ + reverse_slice(self->ob_item, p); + k = binarysort(self->ob_item, hi, p, compare); + goto done; + } + + /* A large array without obvious pattern. */ + k = samplesortslice(self->ob_item, hi, compare); + +done: /* The IFLT macro requires a label named "fail". */; +fail: + self->ob_type = savetype; + if (k >= 0) { + Py_INCREF(Py_None); + return Py_None; + } + else return NULL; - Py_INCREF(Py_None); - return Py_None; } +#undef IFLT + int PyList_Sort(PyObject *v) { |