diff options
| author |   Raymond Hettinger <python@rcn.com> | 2014-04-10 01:18:01 -0600 |
|---|---|---|
| committer | Raymond Hettinger <python@rcn.com> | 2014-04-10 01:18:01 -0600 |
| commit | 6ed7c20ce5b01b69abbc01b9a22bdd9983db9c01 (patch) | |
| tree | 9aafcf6f9ad179f5705ec129f2aa3037a3b43cc0 /Lib | |
| parent | Closes #21172: Merged fix from 3.4. (diff) | |
| download | cpython-6ed7c20ce5b01b69abbc01b9a22bdd9983db9c01.tar.gz cpython-6ed7c20ce5b01b69abbc01b9a22bdd9983db9c01.tar.bz2 cpython-6ed7c20ce5b01b69abbc01b9a22bdd9983db9c01.zip | |
Update comment for the comparison table to use measured results rather than predicted.
Diffstat (limited to 'Lib')
| -rw-r--r-- | Lib/heapq.py | 19 |
1 files changed, 10 insertions, 9 deletions
diff --git a/Lib/heapq.py b/Lib/heapq.py index 789b17a6930..88c7019abc0 100644 --- a/Lib/heapq.py +++ b/Lib/heapq.py @@ -202,16 +202,17 @@ def _heapify_max(x): # Number of comparisons for n random inputs, keeping the k smallest values: # ----------------------------------------------------------- # Step Comparisons Action -# 1 2*k heapify the first k-inputs -# 2 n-k compare new input elements to top of heap -# 3 k*lg2(k)*(ln(n)-lg(k)) add new extreme values to the heap +# 1 1.66*k heapify the first k-inputs +# 2 n - k compare new input elements to top of heap +# 3 k*lg2(k)*(ln(n)-ln(k)) add new extreme values to the heap # 4 k*lg2(k) final sort of the k most extreme values # -# n-random inputs k-extreme values number of comparisons % more than min() -# --------------- ---------------- ------------------- ----------------- -# 10,000 100 13,634 36.3% -# 100,000 100 105,163 5.2% -# 1,000,000 100 1,006,694 0.7% +# number of comparisons +# n-random inputs k-extreme values average of 5 trials % more than min() +# --------------- ---------------- ------------------- ----------------- +# 10,000 100 14,046 40.5% +# 100,000 100 105,749 5.7% +# 1,000,000 100 1,007,751 0.8% # # Computing the number of comparisons for step 3: # ----------------------------------------------- @@ -234,7 +235,7 @@ def _heapify_max(x): # comparisons = k * log(k, 2) * (log(n,e) - log(k, e)) # # Worst-case for step 3: -# --------------------- +# ---------------------- # In the worst case, the input data is reversed sorted so that every new element # must be inserted in the heap: # comparisons = log(k, 2) * (n - k) |