Heap 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	Heap Implementation
Date	Sat, 30 Jan 2016 23:47:31 +0100
Lines	36
Message-ID	<mailman.148.1454194055.2338.python-list@python.org> (permalink)
Mime-Version	1.0
Content-Type	text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding	7bit
X-Trace	news.uni-berlin.de 5dTmJd9NExwRCTUQxfUNcAP8sUG1ttvmsCQc3S2G0vpg==
Return-Path	<srkunze@mail.de>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.057
X-Spam-Evidence	'H': 0.89; 'S': 0.00; 'url:pypi': 0.03; 'rewrite': 0.07; 'url:github': 0.09; 'thread': 0.10; 'python': 0.10; 'weird': 0.15; 'formatting.': 0.16; 'heap': 0.16; 'heapq': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'fixing': 0.22; 'header:User-Agent:1': 0.26; 'compare': 0.27; 'switch': 0.27; 'topic': 0.32; 'url:python': 0.33; 'grateful': 0.33; 'open': 0.33; 'received:10.0': 0.34; 'best,': 0.35; 'url:org': 0.36; 'tool': 0.36; 'to:addr:python-list': 0.36; 'received:10': 0.37; 'really': 0.37; 'missing': 0.37; 'feedback': 0.38; 'to:addr:python.org': 0.40; 'received:de': 0.40; 'some': 0.40; 'your': 0.60; 'skip:u 10': 0.61; 'finally': 0.70; 'incredibly': 0.76; 'removal': 0.79; 'combo': 0.84; 'sweeping': 0.84; 'url:2016': 0.84; 'worried': 0.84; 'dare': 0.91
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/simple; d=mail.de; s=mail201212; t=1454194054; bh=78YKc/DFfgeXVWovics6XcZx5DO6TcWzbSjxLetbTvY=; h=To:From:Subject:Date:From; b=aJuy80o0dGpwAS1CU6eQzPM+uN0C22M/4NrEOd/Wn8HwhUvaz0yRnVpBKV6LaViKz GQRTlvCo4VGMmwb2O6ZKHjvtBShxrNrdviEr8NiG5QPf1uOWaY2SFvsD2By/Jd7sLc VDQ1QbkYFxR0i0P7kFelkc/wF4WDYGcJJxroebno=
User-Agent	Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.5.1
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	1135
X-purgate-ID	154282::1454194054-00003BBD-2D22EA5A/0/0
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.20+
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:102324

Show key headers only | View raw

Hi again,

as the topic of the old thread actually was fully discussed, I dare to 
open a new one.

I finally managed to finish my heap implementation. You can find it at 
https://pypi.python.org/pypi/xheap + https://github.com/srkunze/xheap.

I described my motivations and design decisions at 
http://srkunze.blogspot.com/2016/01/fast-object-oriented-heap-implementation.html 


@Cem
You've been worried about a C implementation. I can assure you that I 
did not intend to rewrite the incredibly fast and well-tested heapq 
implementation. I just re-used it.

I would really be grateful for your feedback as you have first-hand 
experience with heaps.

@srinivas
You might want to have a look at the removal implementation. Do you 
think it would be wiser/faster to switch for the sweeping approach?

I plan to publish some benchmarks to compare heapq and xheap.

@all
What's the best/standardized tool in Python to perform benchmarking? 
Right now, I use a self-made combo of unittest.TestCase and time.time + 
proper formatting.

Best,
Sven


PS: fixing some weird typos and added missing part.

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

Thread

Heap Implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-01-30 23:47 +0100
  Re: Heap Implementation Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2016-01-31 12:48 +1100
    Re: Heap Implementation "Sven R. Kunze" <srkunze@mail.de> - 2016-02-01 20:32 +0100
      Re: Heap Implementation Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2016-02-02 16:38 +1100
        Re: Heap Implementation Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2016-02-02 14:53 +0000

csiph-web