Re: Heap Implementation

Path	csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From	Cem Karan <cfkaran2@gmail.com>
Newsgroups	comp.lang.python
Subject	Re: Heap Implementation
Date	Sun, 7 Feb 2016 20:37:00 -0500
Lines	40
Message-ID	<mailman.84.1454895431.2317.python-list@python.org> (permalink)
References	<56AD3D83.2050308@mail.de>
Mime-Version	1.0 (Mac OS X Mail 6.6 \(1510\))
Content-Type	text/plain; charset=us-ascii
Content-Transfer-Encoding	quoted-printable
X-Trace	news.uni-berlin.de 03MdWw96bXbAR6geEt8zFwNmnmOJMC34rWkXmgmwnPjA==
Return-Path	<cfkaran2@gmail.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.012
X-Spam-Evidence	'H': 0.98; 'S': 0.00; 'url:pypi': 0.03; 'lately': 0.07; 'rewrite': 0.07; 'cc:addr:python-list': 0.09; 'called.': 0.09; 'it;': 0.09; 'url:github': 0.09; 'thread': 0.10; 'jan': 0.11; 'pushed': 0.13; 'heap': 0.16; 'heapq': 0.16; 'received:192.168.1.4': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'wrote:': 0.16; 'result,': 0.18; 'library': 0.20; 'cc:addr:python.org': 0.20; 'cc:2**1': 0.22; 'thanks,': 0.24; 'cc:addr:gmail.com': 0.24; 'header:In-Reply- To:1': 0.24; 'handling': 0.27; 'looks': 0.29; 'directly,': 0.29; 'queue': 0.29; 'push': 0.30; 'topic': 0.32; 'useful': 0.33; 'url:python': 0.33; 'grateful': 0.33; 'open': 0.33; "i'll": 0.33; 'message-id:@gmail.com': 0.34; 'handle': 0.34; 'received:google.com': 0.35; 'could': 0.35; 'quite': 0.35; 'item': 0.35; 'but': 0.36; 'there': 0.36; 'url:org': 0.36; 'received:209.85': 0.36; '(and': 0.36; 'pm,': 0.36; 'subject:: ': 0.37; 'really': 0.37; 'being': 0.37; 'charset:us-ascii': 0.37; 'busy': 0.38; 'received:209': 0.38; 'feedback': 0.38; 'received:192': 0.39; 'well.': 0.40; 'some': 0.40; 'future': 0.60; 'your': 0.60; 'header:Message-Id:1': 0.61; '30,': 0.63; 'more': 0.63; 'times': 0.63; 'finally': 0.70; 'incredibly': 0.76; 'client- side': 0.84; 'url:2016': 0.84; 'worried': 0.84; 'dare': 0.91; 'good,': 0.93
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=content-type:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=PdBdGNc1u+JDVIwSmlQIro00kc7ojsiSkiUIt/ApyUM=; b=xVVD7xgovkuJ+t1HyEg7EiawOmgf4SdXlib9sdQ3Nj5ODF5FMNMbV1Qib1F5/5N8Nu rsCsKbsn9Uv6+pu6nWHy/nHU3EjKBw/bTMXh3TgLpO2qKubwNrZ1NjPus03XHx3R8FkF NipgRWrZrzfWHSAvLWsWX5o3z9WWVwR5fMapgVtvG8qLCMUOeOc4Krm5zIX8mIe5NfvK i9v8yXlnknS1MIG7QwV4nM28yPOQjBZbC6TSLIjsH/2VsfzdL2bZSS28nZn3KSvJpu6i ujL+1o7Iu3yilpjJDUY4HHn9D9+5B+udJ1GObz3fYsobdu/+YZrO6Pi0dA7JQ3gfxmFJ M0lw==
X-Google-DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:content-type:mime-version:subject:from :in-reply-to:date:cc:content-transfer-encoding:message-id:references :to; bh=PdBdGNc1u+JDVIwSmlQIro00kc7ojsiSkiUIt/ApyUM=; b=fcT8iOd3LXlhJM40iII5clhdntm8os7p6dQHABmZEDInwQNpfVuClZ4bgmQ6iEEcre PtOzVj9Eb72uaYCRrmVL9yamIf0ZkDqaUnX/IP9RqcgwXy7pPiXe4SbBKd0L1xIlkSmz DHcCSWMo21GwXWNx2mNTuD6nK0iPp9lHDpIaZ94kKeq3zbJt523vKMqYxR75jdd51Emt qqDeuzcspTMOR/V2bs4cEMcBfKe3JI6R/ppqDGAuzZHGS7X93KFAbhl2OlqQZEMacdas Sv28wyPjxqEn6nWQaPBral1DPp273huDzAKSRGGySrZoed1DV/nv5PHqFyor820LB3ql IiKg==
X-Gm-Message-State	AG10YOQ4bMKZsY1mweqVga5GluZ7xJAeRAQB6d3VwJhkVUPmb7vm7l095jCL2VQGBp1rHQ==
X-Received	by 10.140.202.212 with SMTP id x203mr26850273qha.19.1454895422699; Sun, 07 Feb 2016 17:37:02 -0800 (PST)
In-Reply-To	<56AD3D83.2050308@mail.de>
X-Mailer	Apple Mail (2.1510)
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:102644

Show key headers only | View raw

On Jan 30, 2016, at 5:47 PM, Sven R. Kunze <srkunze@mail.de> wrote:

> 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.

<<SNIP>>

My apologies for not writing sooner, but work has been quite busy lately (and likely will be for some time to come).

I read your approach, and it looks pretty good, but there may be one issue with it; how do you handle the same item being pushed into the heap more than once?  In my simple simulator, I'll push the same object into my event queue multiple times in a row.  The priority is the moment in the future when the object will be called.  As a result, items don't have unique priorities.  I know that there are methods of handling this from the client-side (tuples with unique counters come to mind), but if your library can handle it directly, then that could be useful to others as well.

Thanks,
Cem Karan

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

Thread

Re: Heap Implementation Cem Karan <cfkaran2@gmail.com> - 2016-02-07 20:37 -0500

csiph-web