Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail From: Cem Karan Newsgroups: comp.lang.python Subject: Re: Heap Implementation Date: Sun, 7 Feb 2016 20:37:00 -0500 Lines: 40 Message-ID: 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: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Xref: csiph.com comp.lang.python:102644 On Jan 30, 2016, at 5:47 PM, Sven R. Kunze wrote: > Hi again, >=20 > as the topic of the old thread actually was fully discussed, I dare to = open a new one. >=20 > I finally managed to finish my heap implementation. You can find it at = https://pypi.python.org/pypi/xheap + https://github.com/srkunze/xheap. >=20 > I described my motivations and design decisions at = http://srkunze.blogspot.com/2016/01/fast-object-oriented-heap-implementati= on.html=20 >=20 > @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. >=20 > I would really be grateful for your feedback as you have first-hand = experience with heaps. <> 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=