Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail From: "Sven R. Kunze" Newsgroups: comp.lang.python Subject: Re: Heap Implementation Date: Mon, 1 Feb 2016 18:24:07 +0100 Lines: 57 Message-ID: References: <56AD3D83.2050308@mail.de> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Trace: news.uni-berlin.de or8P2bLR8ZfEBMUsAlfZ3ggOjBxQ2eq1rdCYHhmIZ+zQ== Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.009 X-Spam-Evidence: '*H*': 0.98; '*S*': 0.00; 'url:pypi': 0.03; 'rewrite': 0.07; 'cc:addr:python-list': 0.09; 'url:github': 0.09; 'thread': 0.10; 'python': 0.10; 'jan': 0.11; 'weird': 0.15; '2016': 0.16; 'brilliant': 0.16; 'formatting.': 0.16; 'heap': 0.16; 'heapq': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'wrote:': 0.16; 'memory': 0.17; 'thanks.': 0.18; 'all,': 0.20; 'cc:addr:python.org': 0.20; 'cc:2**1': 0.22; 'meant': 0.22; '31,': 0.22; 'fixing': 0.22; 'am,': 0.23; 'elements': 0.23; 'references': 0.23; 'cc:addr:gmail.com': 0.24; 'implemented': 0.24; 'header:In- Reply-To:1': 0.24; 'header:User-Agent:1': 0.26; 'compare': 0.27; 'switch': 0.27; 'post': 0.31; 'topic': 0.32; 'maybe': 0.33; 'url:python': 0.33; 'grateful': 0.33; 'items.': 0.33; 'open': 0.33; 'received:10.0': 0.34; 'running': 0.34; 'best,': 0.35; 'express': 0.35; 'instead': 0.36; 'url:org': 0.36; 'tool': 0.36; 'subject:: ': 0.37; 'received:10': 0.37; 'really': 0.37; 'missing': 0.37; 'feedback': 0.38; "didn't": 0.39; 'well.': 0.40; 'received:de': 0.40; 'some': 0.40; 'your': 0.60; 'skip:u 10': 0.61; 'periodically': 0.66; 'finally': 0.70; 'feeling': 0.72; 'incredibly': 0.76; 'removal': 0.79; 'combo': 0.84; 'sweeping': 0.84; 'url:2016': 0.84; 'worried': 0.84; 'absolutely': 0.88; 'dare': 0.91 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=mail.de; s=mail201212; t=1454347450; bh=ZCKOMPnOr/IqWRxl33fE2vBcQmB8xqwxgWvnhWheHBM=; h=Subject:To:References:Cc:From:Date:In-Reply-To:From; b=DvInllEGyLh7l3Ukc7AV8tcJva26H+CpgSenHv6prQNxW1L6ve0Mw34CglCfJzn3p NvifOTgD3Aymi/S1hwo/b7OGzn3Q84w9CRHDvrvsInbHJyvQcktyiCEVsKif5CjSdF Glt2mbawCPlbb4MsxrcqPsWa2pNo2UW6swsKnYnA= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.5.1 In-Reply-To: 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: 1971 X-purgate-ID: 154282::1454347450-000009F3-6C53B7DA/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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Xref: csiph.com comp.lang.python:102389 On 31.01.2016 05:59, srinivas devaki wrote: > @Sven > actually you are not sweeping at all, as i remember from my last post > what i meant by sweeping is periodically deleting the elements which > were marked as popped items. Exactly. Maybe I didn't express myself well. Would you prefer the sweeping approach in terms of efficiency over how I implemented xheap currently? Without running some benchmarks, I have absolutely no feeling which approach is faster/more memory efficient etc. > kudos on that __setitem__ technique, > instead of using references to the items like in HeapDict, it is > brilliant of you to simply use __setitem__ Thanks. :) > On Sun, Jan 31, 2016 at 4:17 AM, Sven R. Kunze 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. >> >> @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.