[Python-checkins] cpython: Update comment for the comparison table to use measured results rather than

[raymond.hettinger]

http://hg.python.org/cpython/rev/5caae834175c
changeset:   90217:5caae834175c
user:        Raymond Hettinger <python at rcn.com>
date:        Thu Apr 10 01:18:01 2014 -0600
summary:
  Update comment for the comparison table to use measured results rather than predicted.

files:
  Lib/heapq.py |  19 ++++++++++---------
  1 files changed, 10 insertions(+), 9 deletions(-)


diff --git a/Lib/heapq.py b/Lib/heapq.py
--- a/Lib/heapq.py
+++ b/Lib/heapq.py
@@ -202,16 +202,17 @@
 # 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 @@
 #            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)

-- 
Repository URL: http://hg.python.org/cpython