As the comments in the heapq module says, in most of the cases (probability 0.837 [from knuth vol3]) the the new inserted element whose initial location is end of the array, which means that it will be larger than the `pos` children. So the old version and new version code is same in these cases because in old version the comparison is taking place at line 129, in the new version comparison is taking place inside _siftdown. SO the total number of comparisons are not decreased by those cases the other type case is the swapped element is smaller than `pos` parents, in this case the old version does a comparison and then goto _sifdown but in the new version _siftdown will be executed and then it comes to _siftup, here in 50% of the cases(len(heap last level) == len(heap) // 2) the pos doesn't have a child, so no comparison.
================================================================================================ `pos` | probability | `old version comparisons` | `new version comparisions` ================================================================================================ last level | 0.5 | 1 | 0 last - 1 level | 0.25 | 1 | 1 lower levels | 0.25 | 1 | >=1 ================================================================================================ as the new version doesn't do a comparison if it is in the last level, the optimization is occurring in that place. Which makes the reason behind the heapq module's choice of _siftup code is not at all related to this cause. PS: please copy the table to some text editor, for better visualization. On Fri, Feb 5, 2016 at 11:12 PM, srinivas devaki <mr.eightnotei...@gmail.com> wrote: > wow, that's great. > you read a comment in the code, and you test it, to only find that it > is indeed true, > sounds ok, but feels great. :) > > Just experimenting a bit, I swaped the lines _siftdown and _siftup and > something > strange happened the number of comparisions in both the versions remained > same. > I'm attaching the files. > > do you have any idea why this happened? > > On Fri, Feb 5, 2016 at 9:57 PM, Sven R. Kunze <srku...@mail.de> wrote: >> >> Can we do better here? >> > I don't know, I have to read TAOP knuth article. > > -- > Regards > Srinivas Devaki > Junior (3rd yr) student at Indian School of Mines,(IIT Dhanbad) > Computer Science and Engineering Department > ph: +91 9491 383 249 > telegram_id: @eightnoteight -- Regards Srinivas Devaki Junior (3rd yr) student at Indian School of Mines,(IIT Dhanbad) Computer Science and Engineering Department ph: +91 9491 383 249 telegram_id: @eightnoteight -- https://mail.python.org/mailman/listinfo/python-list