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

[tim_one@users.sourceforge.net]

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.