Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #104137
| Path | csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail |
|---|---|
| From | "Sven R. Kunze" <srkunze@mail.de> |
| Newsgroups | comp.lang.python |
| Subject | even faster heaps |
| Date | Sun, 6 Mar 2016 14:59:48 +0100 |
| Lines | 21 |
| Message-ID | <mailman.242.1457272796.20602.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 3UxvegVrGPqmrx6pW1R0twrAQwuKqujX9dGoM/NQURcA== |
| Return-Path | <srkunze@mail.de> |
| X-Original-To | python-list@python.org |
| Delivered-To | python-list@mail.python.org |
| X-Spam-Status | OK 0.167 |
| X-Spam-Level | * |
| X-Spam-Evidence | '*H*': 0.70; '*S*': 0.03; 'pop': 0.05; '<>,': 0.07; 'url:github': 0.09; 'received:io': 0.16; 'received:psf.io': 0.16; 'all,': 0.20; 'to:2**1': 0.21; 'discovery': 0.22; 'fixing': 0.22; 'url:02': 0.22; 'bugs': 0.27; 'to:no real name:2**1': 0.27; 'compared': 0.30; 'implement': 0.32; 'up!': 0.33; 'received:10.0': 0.34; 'best,': 0.35; 'could': 0.35; 'step': 0.36; 'to:addr:python- list': 0.36; 'received:10': 0.37; 'several': 0.38; 'to:addr:python.org': 0.40; 'received:de': 0.40; 'your': 0.60; 'improved': 0.63; 'improvement.': 0.66; 'pleasant': 0.66; 'soon.': 0.73; 'removal': 0.79; 'benchmark': 0.84; 'honored': 0.84; 'sweeping': 0.84; 'url:2016': 0.84; 'yours.': 0.93 |
| DKIM-Signature | v=1; a=rsa-sha256; c=relaxed/simple; d=mail.de; s=mail201212; t=1457272789; bh=LFc9/QzmupyMLp0NfKVZhZeyodmM+H8x1VIo3NVnyVY=; h=To:From:Subject:Date:From; b=b+gfVtXmckSgGDStxc21YzVHDzyniaKvtRno/0n09O7AJcx08L1zlKY8VZRj18iWE nCQgwK7ikDXQycH52fV6JR9TU1Ass8qzer67yfQ89NQh5lI73dmQQGDgYH2y9rU3Ah i8EIJjsW2eMNBN6rxDPpMvi5vgImj1XaiRuarFPI= |
| 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 | 2223 |
| X-purgate-ID | 154282::1457272789-000009F3-E8C7CACF/0/0 |
| X-Content-Filtered-By | Mailman/MimeDel 2.1.21 |
| X-BeenThere | python-list@python.org |
| X-Mailman-Version | 2.1.21 |
| 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:104137 |
Show key headers only | View raw
Hi python-list, hi Srinivas, I managed to implement the mark&sweep approach for fast removal from heaps. This way, I got three pleasant results: 1) a substantial speed up! 2) an improved testsuite 3) discovery and fixing of several bugs @Srinivas I would be honored if you could have a look at the implementation: https://github.com/srkunze/xheap . After all, it was your idea. I only perform the sweeping step during pop and remove with the condition of yours. :) Using the original xheap benchmark <http://srkunze.blogspot.de/2016/02/the-xheap-benchmark.html>, I could see huge speedups: from 50x/25x down to 3x/2x compared to heapq. That's a massive improvement. I will publish an update soon. Best, Sven
Back to comp.lang.python | Previous | Next | Find similar | Unroll thread
even faster heaps "Sven R. Kunze" <srkunze@mail.de> - 2016-03-06 14:59 +0100
csiph-web