Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #102529

Re: _siftup and _siftdown implementation

Path csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From "Sven R. Kunze" <srkunze@mail.de>
Newsgroups comp.lang.python
Subject Re: _siftup and _siftdown implementation
Date Fri, 5 Feb 2016 17:27:39 +0100
Lines 47
Message-ID <mailman.14.1454689669.19407.python-list@python.org> (permalink)
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>
Mime-Version 1.0
Content-Type text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding 7bit
X-Trace news.uni-berlin.de +Q3fLMQZjr5zCqm+hDtKOwzjQFtI3C3H7Q0OKbWO7bAw==
Return-Path <srkunze@mail.de>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.043
X-Spam-Evidence '*H*': 0.91; '*S*': 0.00; 'here?': 0.09; 'def': 0.13; '__lt__(self,': 0.16; 'heap': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; '&lt;': 0.18; 'to:2**1': 0.21; 'subject:skip:i 10': 0.22; 'wrote': 0.23; 'import': 0.24; 'header :In-Reply-To:1': 0.24; 'header:User-Agent:1': 0.26; '100000': 0.29; 'measure': 0.29; 'random': 0.29; 'skip:_ 10': 0.32; 'class': 0.33; 'version:': 0.33; 'received:10.0': 0.34; 'best,': 0.35; 'to:addr:python-list': 0.36; 'subject:: ': 0.37; 'received:10': 0.37; 'to:addr:python.org': 0.40; 'received:de': 0.40; 'your': 0.60; 'charset:windows-1252': 0.62; 'benchmark': 0.84; 'x):': 0.84
DKIM-Signature v=1; a=rsa-sha256; c=relaxed/simple; d=mail.de; s=mail201212; t=1454689667; bh=SCl7yaUqztgqqwk6FLMFTs73qK1YWeUEnPP3/2deAr8=; h=Subject:To:References:From:Date:In-Reply-To:From; b=TF5Q3DXm/a+IR9GZUhKf6OBAtTN7/hZQUiaJ6RA2UttKa/Gu5MMuw28en9b8JGX9x Kx4RyspNy0xrMf1f5VP2PHIcY3ZIr3rn+lCrBgTvBtFAPcXdyMijFdvXNyMqReqWnD OUhQkLxLp90UbPRkBpq6AUbJgdMoy+DDgTIBJ05w=
User-Agent Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.5.1
In-Reply-To <CACs7g=C-MEHLWYZWJPiiJfxoFHE3y3UcEL2Q7kE=HLNbGQkV+g@mail.gmail.com>
X-purgate clean
X-purgate This mail is considered clean (visit http://www.eleven.de for further information)
X-purgate-type clean
X-purgate-Ad Categorized by eleven eXpurgate (R) http://www.eleven.de
X-purgate This mail is considered clean (visit http://www.eleven.de for further information)
X-purgate clean
X-purgate-size 3733
X-purgate-ID 154282::1454689667-00004575-14B8535E/0/0
X-Content-Filtered-By Mailman/MimeDel 2.1.21rc2
X-BeenThere python-list@python.org
X-Mailman-Version 2.1.21rc2
Precedence list
List-Id General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive <http://mail.python.org/pipermail/python-list/>
List-Post <mailto:python-list@python.org>
List-Help <mailto:python-list-request@python.org?subject=help>
List-Subscribe <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Xref csiph.com comp.lang.python:102529

Show key headers only | View raw

Hi srinivas,

I wrote this simple benchmark to measure comparisons:

import random

from xheapimport RemovalHeap


class X(object):
     c =0 def __init__(self, x):
         self.x = x
     def __lt__(self, other):
         X.c +=1 return self.x < other.x

n =100000 for jjin range(5):
     items = [X(i)for iin range(n)]
     random.shuffle(items)
     heap = RemovalHeap(items)

     random.shuffle(items)
     for i  in items:
         heap.remove(i)

     print(X.c)
     X.c =0


old version:
430457
430810
430657
429971
430583

your pull request version:
426414
426045
425437
425528
425522


Can we do better here?

Best,
Sven

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

_siftup and _siftdown implementation srinivas devaki <mr.eightnoteight@gmail.com> - 2016-02-05 02:20 +0530
  Re: _siftup and _siftdown implementation Steven D'Aprano <steve@pearwood.info> - 2016-02-05 11:12 +1100
    Re: _siftup and _siftdown implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-02-05 01:21 +0100
    Re: _siftup and _siftdown implementation srinivas devaki <mr.eightnoteight@gmail.com> - 2016-02-05 06:56 +0530
    Re: _siftup and _siftdown implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-02-05 15:42 +0100
    Re: _siftup and _siftdown implementation Bernardo Sulzbach <mafagafogigante@gmail.com> - 2016-02-05 12:48 -0200
    Re: _siftup and _siftdown implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-02-05 15:55 +0100
    Re: _siftup and _siftdown implementation Bernardo Sulzbach <mafagafogigante@gmail.com> - 2016-02-05 12:59 -0200
    Re: _siftup and _siftdown implementation srinivas devaki <mr.eightnoteight@gmail.com> - 2016-02-05 21:15 +0530
    Re: _siftup and _siftdown implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-02-05 17:27 +0100
    Re: _siftup and _siftdown implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-02-05 17:35 +0100
    Re: _siftup and _siftdown implementation srinivas devaki <mr.eightnoteight@gmail.com> - 2016-02-05 23:12 +0530
    Re: _siftup and _siftdown implementation srinivas devaki <mr.eightnoteight@gmail.com> - 2016-02-06 20:16 +0530

csiph-web