[Python-checkins] python/dist/src/Objects listobject.c,2.126,2.127
tim_one@users.sourceforge.net
tim_one@users.sourceforge.net
Fri, 19 Jul 2002 00:05:46 -0700
Update of /cvsroot/python/python/dist/src/Objects
In directory usw-pr-cvs1:/tmp/cvs-serv15855/python/Objects
Modified Files:
listobject.c
Log Message:
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.
Index: listobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/listobject.c,v
retrieving revision 2.126
retrieving revision 2.127
diff -C2 -d -r2.126 -r2.127
*** listobject.c 19 Jul 2002 06:12:32 -0000 2.126
--- listobject.c 19 Jul 2002 07:05:44 -0000 2.127
***************
*** 1006,1046 ****
struct SamplesortStackNode stack[STACKSIZE];
! /* 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);
! }
/* ----------------------------------------------------------
--- 1006,1013 ----
struct SamplesortStackNode stack[STACKSIZE];
! assert(lo <= hi);
n = hi - lo;
! if (n < MINSIZE)
! return binarysort(lo, hi, lo, compare);
/* ----------------------------------------------------------
***************
*** 1094,1098 ****
* --------------------------------------------------------*/
for (;;) {
! /* assert lo <= hi, so n >= 0 */
n = hi - lo;
--- 1061,1065 ----
* --------------------------------------------------------*/
for (;;) {
! assert(lo <= hi);
n = hi - lo;
***************
*** 1104,1109 ****
if (n < MINPARTITIONSIZE || extra == 0) {
if (n >= MINSIZE) {
! /* assert extra == 0
! This is rare, since the average size
of a final block is only about
ln(original n). */
--- 1071,1076 ----
if (n < MINPARTITIONSIZE || extra == 0) {
if (n >= MINSIZE) {
! assert(extra == 0);
! /* This is rare, since the average size
of a final block is only about
ln(original n). */
***************
*** 1185,1189 ****
l = lo + 1;
r = hi - 1;
! /* assert lo < l < r < hi (small n weeded out above) */
do {
--- 1152,1156 ----
l = lo + 1;
r = hi - 1;
! assert(lo < l && l < r && r < hi);
do {
***************
*** 1209,1215 ****
} while (l < r);
! /* assert lo < r <= l < hi
! assert r == l or r+1 == l
! everything to the left of l is < pivot, and
everything to the right of r is >= pivot */
--- 1176,1181 ----
} while (l < r);
! assert(lo < r && r <= l && l < hi);
! /* everything to the left of l is < pivot, and
everything to the right of r is >= pivot */
***************
*** 1220,1230 ****
--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.
! */
*lo = *r;
*r = pivot;
--- 1186,1195 ----
--r;
}
! 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;
***************
*** 1251,1261 ****
}
! /* assert lo <= r < l <= hi
! Partitions are [lo, r) and [l, hi) */
!
! /* push 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 */
if (r - lo <= hi - l) {
/* second is bigger */
--- 1216,1225 ----
}
! 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);
if (r - lo <= hi - l) {
/* second is bigger */
***************
*** 1284,1289 ****
}
- #undef IFLT
-
static PyTypeObject immutable_list_type;
--- 1248,1251 ----
***************
*** 1291,1296 ****
listsort(PyListObject *self, PyObject *args)
{
! int err;
PyObject *compare = NULL;
PyTypeObject *savetype;
--- 1253,1259 ----
listsort(PyListObject *self, PyObject *args)
{
! int k;
PyObject *compare = NULL;
+ PyObject **hi, **p;
PyTypeObject *savetype;
***************
*** 1299,1313 ****
return NULL;
}
savetype = self->ob_type;
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)
return NULL;
- Py_INCREF(Py_None);
- return Py_None;
}
int
--- 1262,1321 ----
return NULL;
}
+
savetype = self->ob_type;
+ if (self->ob_size < 2) {
+ k = 0;
+ goto done;
+ }
+
self->ob_type = &immutable_list_type;
! 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;
}
+
+ #undef IFLT
int