[Python-checkins] python/dist/src/Objects listobject.c,2.126,2.127

2002年7月19日 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