Path: csiph.com!news.swapon.de!fu-berlin.de!uni-berlin.de!not-for-mail From: "Sven R. Kunze" Newsgroups: comp.lang.python Subject: Re: _siftup and _siftdown implementation Date: Fri, 5 Feb 2016 17:35:37 +0100 Lines: 83 Message-ID: References: <56b3e902$0$1613$c3e8da3$5496439d@news.astraweb.com> <56B4CD7B.70506@mail.de> Mime-Version: 1.0 Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit X-Trace: news.uni-berlin.de qGB/7/34EMOwfdcD0yWKPQ3bOhsnZY32qAxd+Ho6N1rw== Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.014 X-Spam-Evidence: '*H*': 0.97; '*S*': 0.00; 'formatting': 0.07; 'here?': 0.09; 'list).': 0.09; 'def': 0.13; '__lt__(self,': 0.16; 'heap': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'wrote:': 0.16; '<': 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; 'skip:# 10': 0.27; '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; 'list:': 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=1454690140; bh=sQdmhJ+8Rvt6K+QuADuCiadeRUujt+g36o0BQU9f5h4=; h=Subject:To:References:From:Date:In-Reply-To:From; b=Nt1FPLIyEDkiZ6iDTkrFkbsdl2qdDVtwrjoq9VJmvjCutbi8ggMeLD6La0xCndYlV YdaQ6K2VyvtSFcsNuWUtCqk/A7RfQnZG8Wc8EZuuFYR5gj1dIrGgBbDGx7fJJScLRy 6mWxICXo198qmAa7VRi2sed23rYnIFdpJA400uzQ= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.5.1 In-Reply-To: <56B4CD7B.70506@mail.de> 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: 4856 X-purgate-ID: 154282::1454690140-00004575-219EA70B/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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Xref: csiph.com comp.lang.python:102530 again for the list: ################### import random from xheap import 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 jj in range(5): items = [X(i) for i in range(n)] random.shuffle(items) heap = RemovalHeap(items) random.shuffle(items) for i in items: heap.remove(i) print(X.c) X.c = 0 (note to myself: never copy PyCharm formatting strings to this list). On 05.02.2016 17:27, Sven R. Kunze wrote: > 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