[Python-checkins] Fixes in sorting descriptions (GH-18317)
Miss Islington (bot)
webhook-mailer at python.org
Mon Feb 3 19:30:58 EST 2020
https://github.com/python/cpython/commit/fda6593f926be274225dc4bcfdc3f96d9f40258f
commit: fda6593f926be274225dc4bcfdc3f96d9f40258f
branch: 3.7
author: Miss Islington (bot) <31488909+miss-islington at users.noreply.github.com>
committer: GitHub <noreply at github.com>
date: 2020-02-03T16:30:44-08:00
summary:
Fixes in sorting descriptions (GH-18317)
Improvements in listsort.txt and a comment in sortperf.py.
Automerge-Triggered-By: @csabella
(cherry picked from commit 24e5ad4689de9adc8e4a7d8c08fe400dcea668e6)
Co-authored-by: Stefan Pochmann <stefan.pochmann at gmail.com>
files:
M Lib/test/sortperf.py
M Objects/listsort.txt
diff --git a/Lib/test/sortperf.py b/Lib/test/sortperf.py
index 171e5cef5e29f..14a9d827ed57c 100644
--- a/Lib/test/sortperf.py
+++ b/Lib/test/sortperf.py
@@ -134,7 +134,7 @@ def tabulate(r):
L = list(range(half - 1, -1, -1))
L.extend(range(half))
# Force to float, so that the timings are comparable. This is
- # significantly faster if we leave tham as ints.
+ # significantly faster if we leave them as ints.
L = list(map(float, L))
doit(L) # !sort
print()
diff --git a/Objects/listsort.txt b/Objects/listsort.txt
index 8c877515c72e8..dc0b273d12632 100644
--- a/Objects/listsort.txt
+++ b/Objects/listsort.txt
@@ -319,13 +319,13 @@ So merging is always done on two consecutive runs at a time, and in-place,
although this may require some temp memory (more on that later).
When a run is identified, its base address and length are pushed on a stack
-in the MergeState struct. merge_collapse() is then called to see whether it
-should merge it with preceding run(s). We would like to delay merging as
-long as possible in order to exploit patterns that may come up later, but we
-like even more to do merging as soon as possible to exploit that the run just
-found is still high in the memory hierarchy. We also can't delay merging
-"too long" because it consumes memory to remember the runs that are still
-unmerged, and the stack has a fixed size.
+in the MergeState struct. merge_collapse() is then called to potentially
+merge runs on that stack. We would like to delay merging as long as possible
+in order to exploit patterns that may come up later, but we like even more to
+do merging as soon as possible to exploit that the run just found is still
+high in the memory hierarchy. We also can't delay merging "too long" because
+it consumes memory to remember the runs that are still unmerged, and the
+stack has a fixed size.
What turned out to be a good compromise maintains two invariants on the
stack entries, where A, B and C are the lengths of the three righmost not-yet
@@ -739,7 +739,7 @@ slice (leaving off both endpoints) (2**(k-1)-1)+1 through (2**k-1)-1
inclusive = 2**(k-1) through (2**k-1)-1 inclusive, which has
(2**k-1)-1 - 2**(k-1) + 1 =
2**k-1 - 2**(k-1) =
- 2*2**k-1 - 2**(k-1) =
+ 2*2**(k-1)-1 - 2**(k-1) =
(2-1)*2**(k-1) - 1 =
2**(k-1) - 1
elements.
More information about the Python-checkins
mailing list