Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #68492
| Path | csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail |
|---|---|
| Return-Path | <joshua.landau.ws@gmail.com> |
| X-Original-To | python-list@python.org |
| Delivered-To | python-list@mail.python.org |
| X-Spam-Status | OK 0.000 |
| X-Spam-Evidence | '*H*': 1.00; '*S*': 0.00; 'feedback.': 0.04; 'anyway.': 0.05; 'argument': 0.05; 'cache': 0.07; 'pypy': 0.07; 'assuming': 0.09; 'below).': 0.09; 'executed': 0.09; 'inclusion': 0.09; 'keys,': 0.09; 'part,': 0.09; 'python': 0.11; 'suggest': 0.14; 'random': 0.14; '"create': 0.16; '*grins*': 0.16; '__lt__': 0.16; 'accesses': 0.16; 'both,': 0.16; 'dwarfed': 0.16; 'index.': 0.16; 'jumping': 0.16; 'keys.': 0.16; 'once.': 0.16; 'optimised': 0.16; 'ported': 0.16; 'sorting': 0.16; 'stutzbach': 0.16; 'subtraction': 0.16; 'unfair': 0.16; 'so.': 0.16; 'sender:addr:gmail.com': 0.17; 'fix': 0.17; 'wrote:': 0.18; 'module': 0.19; 'slightly': 0.19; 'error': 0.23; 'issue,': 0.24; 'fine': 0.24; 'sort': 0.25; '(see': 0.26; 'compare': 0.26; 'daniel': 0.26; 'header:In-Reply-To:1': 0.27; "doesn't": 0.30; 'message-id:@mail.gmail.com': 0.30; "i'm": 0.30; 'gives': 0.31; 'that.': 0.31; 'bad.': 0.31; 'overhead': 0.31; 'though.': 0.31; 'this.': 0.32; 'probably': 0.32; 'limitation': 0.33; 'to:name :python-list': 0.33; 'sense': 0.34; 'there,': 0.34; "i'd": 0.34; 'could': 0.34; 'agree': 0.35; 'classes': 0.35; 'something': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'really': 0.36; 'doing': 0.36; 'method': 0.36; 'thanks': 0.36; 'similar': 0.36; 'should': 0.36; 'turn': 0.37; 'list': 0.37; 'list.': 0.37; 'step': 0.37; 'to:addr:python-list': 0.38; 'little': 0.38; 'expect': 0.39; 'to:addr:python.org': 0.39; 'how': 0.40; 'march': 0.61; "you're": 0.61; 'first': 0.61; "you'll": 0.62; 'making': 0.63; 'kind': 0.63; 'skip:n 10': 0.64; 'pick': 0.64; 'more': 0.64; 'love': 0.65; 'worth': 0.66; 'improvement.': 0.68; 'risk': 0.72; 'further,': 0.74; 'obvious': 0.74; ':).': 0.84; 'benchmark': 0.84 |
| DKIM-Signature | v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:content-type; bh=Sirt9Z9oWrDybOX3ThJVU55uYVsUdzyBnsja/7YgViQ=; b=Hzx5jHFperb0mBAuvJZS2qpCeJDl9z6LkggE3RlMvLe+fyvwo6+A47kPNn1LpO+PYu IOAqJPQTY7PIg92mqLukQVabF9W2ye9yZe1AWZvKxYdwh091TNaYR2J+ZZhboZ84AlU2 rmrqQDPDxUMqT5XQpWd2ktEvG1lMzgP73v8oQmxEN4wNoUQnihlMqJJJd5WAa8uFTZID XfaCZxJ/Of04Bb0POzKkRVDj0HpSBsNLNMuFNhEpWR+KCDb/OOESd7cmCT6EJvLwoTL9 dR5DWDYydBny4fpYD8Acx/0Kr9RTvbmgOgD32wc7cuBqp3h05go4srec7SINqpQ38SL4 7pTg== |
| X-Received | by 10.152.225.70 with SMTP id ri6mr20312925lac.26.1395128842734; Tue, 18 Mar 2014 00:47:22 -0700 (PDT) |
| MIME-Version | 1.0 |
| Sender | joshua.landau.ws@gmail.com |
| In-Reply-To | <CAMMy=OveYrvz+SZkbk9WvdrmsQMEx3_HVWSkcatbZC4A5jzD8Q@mail.gmail.com> |
| References | <lennh4$kpm$1@cabale.usenet-fr.net> <CAPTjJmomgZSFj7TanBn8_qXP4ULhCm85abJ5=2PcikXJkrH6GQ@mail.gmail.com> <CAN1F8qU8AJ+Z-Rb4+wGsYWd_bS5aOA3bsjd5NjF46MUvnecSeQ@mail.gmail.com> <mailman.7473.1393598638.18130.python-list@python.org> <XnsA2E95FA1E1EB6duncanbooth@127.0.0.1> <bnvctpF5vanU1@mid.individual.net> <mailman.7920.1394252278.18130.python-list@python.org> <87eh2d3x8h.fsf_-_@elektro.pacujo.net> <CAGGBd_qU3Zp3A4pymnDQfWynWZwFVrdHJpG=U0WZTap4HiymdA@mail.gmail.com> <lffv32$mqo$1@ger.gmane.org> <CAN1F8qU=2K6ysbpnu-JoUtfWfTToRsOaRek0dSQzjPx_sYzPKQ@mail.gmail.com> <CAMMy=OsYUzULRTRHwytiTszd44f3anz43=2DtGALHR3nBGe8JQ@mail.gmail.com> <CAN1F8qUqVnhjxXEUnub36GEwK_DD+ukKK2GwA5wYku0s=wpdgA@mail.gmail.com> <CAMMy=OveYrvz+SZkbk9WvdrmsQMEx3_HVWSkcatbZC4A5jzD8Q@mail.gmail.com> |
| From | Joshua Landau <joshua@landau.ws> |
| Date | Tue, 18 Mar 2014 07:46:42 +0000 |
| X-Google-Sender-Auth | qCv3fu4wLqEW-u4uH85hGy4WbRM |
| Subject | Re: Balanced trees |
| To | python-list <python-list@python.org> |
| Content-Type | text/plain; charset=UTF-8 |
| X-BeenThere | python-list@python.org |
| X-Mailman-Version | 2.1.15 |
| 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> |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.8245.1395128850.18130.python-list@python.org> (permalink) |
| Lines | 67 |
| NNTP-Posting-Host | 2001:888:2000:d::a6 |
| X-Trace | 1395128850 news.xs4all.nl 2933 [2001:888:2000:d::a6]:49809 |
| X-Complaints-To | abuse@xs4all.nl |
| Xref | csiph.com comp.lang.python:68492 |
Show key headers only | View raw
On 18 March 2014 01:01, Daniel Stutzbach <stutzbach@google.com> wrote:
> I would love to have include macro-benchmarks. I keep waiting for the PyPy
> benchmark suite to get ported to Python 3...
*grins*
>> "Delete a slice" is fudged from its inclusion of multiplication, which
>> is far faster on blists. I admit that it's not obvious how to fix
>> this.
>
> I could move the initialization into the timed part, similar to what I did
> for sort (see below). That has downsides too, of course, but it might be an
> improvement.
You could try making a baseline and subtracting it:
timer("del x[len(x)//4:3*len(x)//4]; x *= 2") - timer("x * 2")
Not ideal, but closer, assuming that the multiplication isn't much
larger than the deletion. Error would be summed.
>> "Sort *" are really unfair because they put initialisation in the
>> timed part
>
> That's a limitation of timeit. The setup step is only executed once. If I
> put the initialization there, every sort after the first one would be
> sorting a pre-sorted list. If you compare the "Create form an iterator" and
> "Sort a random list", you'll see that the initialization cost is dwarfed by
> the sorting cost for n > 15 or so.
This argument is slightly less convincing without the overhead of the
keys. It might be worth doing a subtraction and adding some error-bars
as I suggest above. Nevertheless, I do agree for n > some small n,
which is all that matters anyway.
>> and all have keys.
>
> If you use classes with __lt__ methods instead of keys, the cost is
> dominated by the calls to __lt__. You're right that I should include both,
> though.
This argument doesn't make sense to me. The only time this happens is
when you have a non-primitive and your transformation gives a
primitive which has optimised comparisons. This typically only happens
when the key is a getitem or getattr, in which case it's just
meaningless overhead. I see little reason to care about the key's cost
in those cases.
> That's definitely a cache issue, which is always a risk with
> micro-benchmarks.
>
> I agree it's more interesting to pick items randomly instead of always
> querying the same index. The overhead of choice() is kind of a problem,
> though. Since I'm only plotting up to 10**5, I'd expect these to look more
> or less flat.
You could try jumping around to avoid the cache without using random
numbers. Something like "idx = (idx + LARGE_PRIME) % n" might have less
overhead. Further, the subtraction method would probably work fine for
that.
Also, I don't think the cache is all bad. Chances are a lot of list
accesses have a lot of data locality.
> Thanks for all of the feedback.
Thanks in turn for the module :).
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Re: Tuples and immutability Duncan Booth <duncan.booth@invalid.invalid> - 2014-03-07 09:33 +0000
Re: Tuples and immutability Ben Finney <ben+python@benfinney.id.au> - 2014-03-07 22:04 +1100
Re: Tuples and immutability Chris Angelico <rosuav@gmail.com> - 2014-03-07 22:11 +1100
Re: Tuples and immutability Peter Otten <__peter__@web.de> - 2014-03-07 12:38 +0100
Re: Tuples and immutability Chris Angelico <rosuav@gmail.com> - 2014-03-07 22:45 +1100
Re: Tuples and immutability Alister <alister.ware@ntlworld.com> - 2014-03-07 11:51 +0000
Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-07 11:23 -0700
Re: Tuples and immutability Roy Smith <roy@panix.com> - 2014-03-07 08:37 -0500
Re: Tuples and immutability Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-03-08 15:17 +1300
Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-07 21:17 -0700
Balanced trees (was: Re: Tuples and immutability) Marko Rauhamaa <marko@pacujo.net> - 2014-03-08 10:34 +0200
Re: Balanced trees (was: Re: Tuples and immutability) Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-08 04:03 -0700
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-08 13:26 +0200
Re: Balanced trees (was: Re: Tuples and immutability) Dan Stromberg <drsalists@gmail.com> - 2014-03-08 11:58 -0800
Re: Balanced trees Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-03-08 20:37 +0000
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-08 23:21 +0200
Re: Balanced trees Roy Smith <roy@panix.com> - 2014-03-08 17:22 -0500
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-09 11:17 +0200
Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-08 17:31 -0800
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-09 11:27 +0200
Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-09 14:20 -0700
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-09 23:32 +0200
Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-09 14:37 -0700
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-09 23:43 +0200
Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-09 15:08 -0700
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-10 00:24 +0200
Re: Balanced trees Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-09 18:04 -0600
Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-10 03:24 +0000
Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-10 03:24 +0000
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-10 08:16 +0200
Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-10 08:53 +0000
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-10 11:41 +0200
Re: Balanced trees Ned Batchelder <ned@nedbatchelder.com> - 2014-03-10 06:57 -0400
Re: Balanced trees Rustom Mody <rustompmody@gmail.com> - 2014-03-10 09:01 -0700
Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-11 02:02 +0000
Re: Balanced trees Roy Smith <roy@panix.com> - 2014-03-10 22:20 -0400
Re: Balanced trees Chris Angelico <rosuav@gmail.com> - 2014-03-11 13:29 +1100
Re: Balanced trees Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-03-10 09:51 +0000
Re: Balanced trees Roy Smith <roy@panix.com> - 2014-03-10 09:59 -0400
Re: Balanced trees Chris Angelico <rosuav@gmail.com> - 2014-03-11 03:20 +1100
Re: Balanced trees Chris Angelico <rosuav@gmail.com> - 2014-03-11 03:24 +1100
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-10 19:08 +0200
Re: Balanced trees Chris Angelico <rosuav@gmail.com> - 2014-03-11 04:17 +1100
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-10 19:34 +0200
Re: Balanced trees Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-13 12:40 -0600
Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-13 23:57 +0000
Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-13 20:12 -0700
Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-14 05:02 +0000
Re: Balanced trees Roy Smith <roy@panix.com> - 2014-03-10 19:24 -0400
Re: Balanced trees Chris Angelico <rosuav@gmail.com> - 2014-03-11 10:27 +1100
Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-11 01:26 +0000
Re: Balanced trees Chris Angelico <rosuav@gmail.com> - 2014-03-11 12:45 +1100
Re: Balanced trees Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-10 21:38 -0600
Re: Balanced trees Chris Angelico <rosuav@gmail.com> - 2014-03-11 15:28 +1100
Re: Balanced trees "Rhodri James" <rhodri@wildebst.org.uk> - 2014-03-12 00:57 +0000
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-11 12:12 +0200
Re: Balanced trees alex23 <wuwei23@gmail.com> - 2014-03-12 10:13 +1000
Re: Balanced trees Alister <alister.ware@ntlworld.com> - 2014-03-11 09:25 +0000
Re: Balanced trees Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2014-03-12 10:08 +0100
Re: Balanced trees Tim Chase <python.list@tim.thechases.com> - 2014-03-10 11:33 -0500
Re: Balanced trees Chris Angelico <rosuav@gmail.com> - 2014-03-11 03:39 +1100
Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-10 18:05 -0700
Re: Balanced trees Roy Smith <roy@panix.com> - 2014-03-10 22:13 -0400
Re: Balanced trees Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2014-03-10 19:57 -0400
Re: Balanced trees Joshua Landau <joshua@landau.ws> - 2014-03-15 01:13 +0000
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-18 00:05 +0200
Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-18 12:26 -0700
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-18 22:55 +0200
Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-18 14:45 -0700
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-19 00:03 +0200
Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-18 15:21 -0700
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-19 01:11 +0200
Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-19 01:15 +0000
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-19 10:49 +0200
Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-19 13:42 +0000
Re: Balanced trees Marko Rauhamaa <marko@pacujo.net> - 2014-03-19 15:54 +0200
Re: Balanced trees Roy Smith <roy@panix.com> - 2014-03-19 10:06 -0400
Re: Balanced trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-19 01:15 +0000
Re: Balanced trees Ethan Furman <ethan@stoneleaf.us> - 2014-03-19 08:15 -0700
Re: Balanced trees "Rhodri James" <rhodri@wildebst.org.uk> - 2014-03-20 02:16 +0000
Re: Balanced trees Dan Stromberg <drsalists@gmail.com> - 2014-03-19 19:34 -0700
Re: Balanced trees Chris Kaynor <ckaynor@zindagigames.com> - 2014-03-18 18:02 -0700
Re: Balanced trees Daniel Stutzbach <stutzbach@google.com> - 2014-03-18 13:18 -0700
blist in standard library (was Re: Balanced trees) Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-03-15 12:31 +0000
Re: Balanced trees Daniel Stutzbach <stutzbach@google.com> - 2014-03-17 14:16 -0700
Re: Balanced trees Joshua Landau <joshua@landau.ws> - 2014-03-18 00:08 +0000
Re: Balanced trees Daniel Stutzbach <stutzbach@google.com> - 2014-03-17 18:01 -0700
Re: Balanced trees Joshua Landau <joshua@landau.ws> - 2014-03-18 07:46 +0000
Re: Tuples and immutability Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-03-09 13:40 +1300
Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-08 19:39 -0700
Re: Tuples and immutability Marko Rauhamaa <marko@pacujo.net> - 2014-03-09 11:35 +0200
Re: Tuples and immutability Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-03-10 11:03 +1300
Re: Tuples and immutability Terry Reedy <tjreedy@udel.edu> - 2014-03-09 19:00 -0400
Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-09 17:42 -0600
Re: Tuples and immutability Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-10 02:37 +0000
Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-10 02:35 -0600
Re: Tuples and immutability Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-10 09:13 +0000
Re: Tuples and immutability Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-03-11 18:15 +1300
Re: Tuples and immutability Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-03-11 18:03 +1300
Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-11 04:39 -0600
Re: Tuples and immutability Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-11 16:46 +0000
Re: Tuples and immutability Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-03-12 10:23 +1300
Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-11 17:06 -0600
Re: Tuples and immutability Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-12 23:20 +0000
Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-12 19:35 -0600
Re: Tuples and immutability Terry Reedy <tjreedy@udel.edu> - 2014-03-12 22:09 -0400
Re: Tuples and immutability Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-03-09 13:45 +1300
Re: Tuples and immutability Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-08 19:55 -0700
csiph-web