[Python-checkins] python/dist/src/Objects listsort.txt,1.5,1.6

2002年8月10日 00:04:05 -0700

Update of /cvsroot/python/python/dist/src/Objects
In directory usw-pr-cvs1:/tmp/cvs-serv12588/python/Objects
Modified Files:
	listsort.txt 
Log Message:
Fixed new typos, added a little info about ~sort versus "hint"s.
Index: listsort.txt
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/listsort.txt,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** listsort.txt	10 Aug 2002 05:21:15 -0000	1.5
--- listsort.txt	10 Aug 2002 07:04:01 -0000	1.6
***************
*** 114,119 ****
 1.99% 1577.82% -0.06% 967.83% -24.01% 774.44%

! 524288 9205096 9453356 9408463 524468 9441930 2218577 9692015
! 9278734 524580 524633 837947 2916107 1048574
 1.88% 1693.52% -0.03% 1026.79% -23.92% 824.30%

--- 114,119 ----
 1.99% 1577.82% -0.06% 967.83% -24.01% 774.44%

! 524288 9205096 9453356 9408463 524468 9441930 2218577 9692015
! 9278734 524580 524633 837947 2916107 1048574
 1.88% 1693.52% -0.03% 1026.79% -23.92% 824.30%

***************
*** 432,436 ****
 A refinement: The MergeState struct contains the value of min_gallop that
 controls when we enter galloping mode, initialized to MIN_GALLOP.
! merge_lo() and merge_hi() adjust this higher when gallooping isn't paying
 off, and lower when it is.

--- 432,436 ----
 A refinement: The MergeState struct contains the value of min_gallop that
 controls when we enter galloping mode, initialized to MIN_GALLOP.
! merge_lo() and merge_hi() adjust this higher when galloping isn't paying
 off, and lower when it is.

***************
*** 550,554 ****
 galloping mode (if we ever leave it in the current merge, and at the
 start of the next merge). But whenever the gallop loop doesn't pay,
! min_gallop is increased by one, making it harder to transition to back
 to galloping mode (and again both within a merge and across merges). For
 random data, this all but eliminates the gallop penalty: min_gallop grows
--- 550,554 ----
 galloping mode (if we ever leave it in the current merge, and at the
 start of the next merge). But whenever the gallop loop doesn't pay,
! min_gallop is increased by one, making it harder to transition back
 to galloping mode (and again both within a merge and across merges). For
 random data, this all but eliminates the gallop penalty: min_gallop grows
***************
*** 576,579 ****
--- 576,585 ----
 it's unclear how to generalize that intuition usefully, and merging of
 wildly unbalanced runs already enjoys excellent performance.
+ 
+ ~sort is a good example of when balanced runs could benefit from a better
+ hint value: to the extent possible, this would like to use a starting
+ offset equal to the previous value of acount/bcount. Doing so saves about
+ 10% of the compares in ~sort. However, doing so is also a mixed bag,
+ hurting other cases.