Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From: srinivas devaki <mr.eightnoteight@gmail.com>
Newsgroups: comp.lang.python
Subject: Re: _siftup and _siftdown implementation
Date: Sat, 6 Feb 2016 20:16:36 +0530
Lines: 68
Message-ID: <mailman.44.1454770038.2317.python-list@python.org>
References: <mailman.72.1454619005.30993.python-list@python.org> <56b3e902$0$1613$c3e8da3$5496439d@news.astraweb.com> <CACs7g=C-MEHLWYZWJPiiJfxoFHE3y3UcEL2Q7kE=HLNbGQkV+g@mail.gmail.com> <56B4CD7B.70506@mail.de> <CACs7g=CdJZOPrrdaROHsXWRO1pe0KRAHri0VrXAvH0kaGdWcrA@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
In-Reply-To: <CACs7g=CdJZOPrrdaROHsXWRO1pe0KRAHri0VrXAvH0kaGdWcrA@mail.gmail.com>
Precedence: list
Xref: csiph.com comp.lang.python:102586

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.eightnoteight@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 <srkunze@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