Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #86407

Re: Bug in timsort!?

Path csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path <rosuav@gmail.com>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.004
X-Spam-Evidence '*H*': 0.99; '*S*': 0.00; ';-)': 0.03; 'alignment': 0.07; 'assuming': 0.09; 'integers': 0.09; 'objects,': 0.09; 'worse': 0.09; 'cc:addr:python-list': 0.11; '(there': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'integers,': 0.16; 'malloc': 0.16; 'ought': 0.16; 'sorting': 0.16; 'wrote:': 0.18; 'thu,': 0.19; 'feb': 0.22; 'cc:addr:python.org': 0.22; 'bytes': 0.24; "shouldn't": 0.24; 'cc:2**0': 0.24; 'sort': 0.25; 'references': 0.26; 'header:In-Reply-To:1': 0.27; 'chris': 0.29; 'am,': 0.29; 'absolute': 0.30; 'message-id:@mail.gmail.com': 0.30; 'that.': 0.31; 'object.': 0.31; 'overhead': 0.31; "they'll": 0.31; 'figure': 0.32; 'another': 0.32; 'actual': 0.34; 'could': 0.34; 'received:google.com': 0.35; 'add': 0.35; 'in.': 0.36; 'ram': 0.36; 'two': 0.37; 'list': 0.37; 'that,': 0.38; 'sure': 0.39; 'even': 0.60; "you're": 0.61; 'our': 0.64; '26,': 0.68; '2015': 0.84; 'each,': 0.84; 'to:none': 0.92
DKIM-Signature v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:cc :content-type; bh=DcWcDFviwi4pBvOgg2+R8K5vCOuc5BUMGveBGNlQrUo=; b=lQ/AxDvh9FHHJjxjsfoeSQbpvWm5vCHNGl5SrBuiUbyFksSnGiL/ttJG8/ycsUEA9t S8XV1K52VyiDEHB2JN1Jiyh63N8RKU0apxXW2tGOMvoQPO7biUkLHfdMebh0kaQmFXlN 2XkLth0PlPRMgGL2b0FKzqrvUvFCiO+mwckSkdtPypimmFG8riYtH/NwJOhQTqkmTRgW 2JhEtzVcSWWcyOyYlGNeN3E0XQUSloyi3leioIitPgt7y7IOy4x3X6+HPRbtnvDwyn/T hd0Q53uQ9Tn5P/TicddWpJqiYf3sJXU3P/E+HY5E95RxFcgaIpRKmLHsgQjEGBox/IXK x2vA==
MIME-Version 1.0
X-Received by 10.107.160.212 with SMTP id j203mr5071684ioe.43.1424877080658; Wed, 25 Feb 2015 07:11:20 -0800 (PST)
In-Reply-To <mckobh$jbh$1@ger.gmane.org>
References <1cf84559-3a63-4799-a879-ae8e513d387e@googlegroups.com> <mckke8$con$1@ger.gmane.org> <CAPTjJmrQnswnf6GWWt02kV7Akn+OAKdSEQjmwkd9d11+vO6stg@mail.gmail.com> <mckobh$jbh$1@ger.gmane.org>
Date Thu, 26 Feb 2015 02:11:20 +1100
Subject Re: Bug in timsort!?
From Chris Angelico <rosuav@gmail.com>
Cc "python-list@python.org" <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.19191.1424877089.18130.python-list@python.org> (permalink)
Lines 20
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1424877089 news.xs4all.nl 2829 [2001:888:2000:d::a6]:41878
X-Complaints-To abuse@xs4all.nl
Xref csiph.com comp.lang.python:86407

Show key headers only | View raw

On Thu, Feb 26, 2015 at 2:05 AM, Sturla Molden <sturla.molden@gmail.com> wrote:
> On 25/02/15 15:33, Chris Angelico wrote:
>
>> It's even worse than that. Unless you have a list of 2**49 references
>> to the same few objects, you're going to need to have some actual
>> content for each one. The absolute best you could do is to sort
>> integers, which would take 32 bytes each [1]; if you're sorting
>> strings, they'll be 90 bytes each, so the integers are our best bet.
>> So add another *five* powers of two to the RAM requirements.
>
>
> In that case you also need to add the PyObject_HEAD overhead for each
> object. ;-)

Not sure about that, because the figure of 32 bytes came from
sys.getsizeof(). So assuming there's no significant malloc overhead
(there shouldn't be any alignment padding, for instance), 32 bytes
ought to be it - pack 'em all in.

ChrisA

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

Thread

Bug in timsort!? Roy Smith <roy@panix.com> - 2015-02-24 13:34 -0800
  Re: Bug in timsort!? Zachary Ware <zachary.ware+pylist@gmail.com> - 2015-02-24 15:40 -0600
  Re: Bug in timsort!? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-24 21:49 +0000
    Re: Bug in timsort!? sohcahtoa82@gmail.com - 2015-02-24 14:36 -0800
      Re: Bug in timsort!? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-25 00:38 +0000
  Re: Bug in timsort!? Grant Edwards <invalid@invalid.invalid> - 2015-02-24 22:45 +0000
    Re: Bug in timsort!? Ian Kelly <ian.g.kelly@gmail.com> - 2015-02-24 15:59 -0700
    Re: Bug in timsort!? Robert Kern <robert.kern@gmail.com> - 2015-02-25 11:34 +0000
      Re: Bug in timsort!? Grant Edwards <invalid@invalid.invalid> - 2015-02-25 15:49 +0000
  Re: Bug in timsort!? Chris Angelico <rosuav@gmail.com> - 2015-02-25 10:33 +1100
  Re: Bug in timsort!? MRAB <python@mrabarnett.plus.com> - 2015-02-24 23:38 +0000
  Re: Bug in timsort!? Skip Montanaro <skip.montanaro@gmail.com> - 2015-02-24 17:50 -0600
  Re: Bug in timsort!? Chris Angelico <rosuav@gmail.com> - 2015-02-25 11:07 +1100
    Re: Bug in timsort!? Paddy <paddy3118@gmail.com> - 2015-02-25 01:10 -0800
      Re: Bug in timsort!? Chris Angelico <rosuav@gmail.com> - 2015-02-25 21:11 +1100
  Re: Bug in timsort!? Chris Kaynor <ckaynor@zindagigames.com> - 2015-02-24 16:38 -0800
  Re: Bug in timsort!? Terry Reedy <tjreedy@udel.edu> - 2015-02-24 21:52 -0500
  Re: Bug in timsort!? Dave Angel <davea@davea.name> - 2015-02-24 21:41 -0500
  Re: Bug in timsort!? Ned Deily <nad@acm.org> - 2015-02-25 01:04 -0800
  Re: Bug in timsort!? Sturla Molden <sturla.molden@gmail.com> - 2015-02-25 14:58 +0100
    Re: Bug in timsort!? alister <alister.nospam.ware@ntlworld.com> - 2015-02-25 15:03 +0000
      Re: Bug in timsort!? Zachary Ware <zachary.ware+pylist@gmail.com> - 2015-02-25 09:23 -0600
      Re: Bug in timsort!? Terry Reedy <tjreedy@udel.edu> - 2015-02-25 16:08 -0500
    Re: Bug in timsort!? Roy Smith <roy@panix.com> - 2015-02-25 19:12 -0500
  Re: Bug in timsort!? Jonas Wielicki <jonas@wielicki.name> - 2015-02-25 15:07 +0100
  Re: Bug in timsort!? Chris Angelico <rosuav@gmail.com> - 2015-02-26 01:33 +1100
  Re: Bug in timsort!? Sturla Molden <sturla.molden@gmail.com> - 2015-02-25 16:05 +0100
  Re: Bug in timsort!? Chris Angelico <rosuav@gmail.com> - 2015-02-26 02:11 +1100
  Re: Bug in timsort!? Peter Otten <__peter__@web.de> - 2015-02-25 17:04 +0100
    Re: Bug in timsort!? Mario Figueiredo <marfig@gmail.com> - 2015-02-25 18:22 +0100
      Re: Bug in timsort!? Sturla Molden <sturla.molden@gmail.com> - 2015-02-25 19:41 +0100
      Re: Bug in timsort!? Jonas Wielicki <jonas@wielicki.name> - 2015-02-25 19:46 +0100
      Re: Bug in timsort!? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-25 20:07 +0000
  Re: Bug in timsort!? Sturla Molden <sturla.molden@gmail.com> - 2015-02-25 17:44 +0100
    Re: Bug in timsort!? Mario Figueiredo <marfig@gmail.com> - 2015-02-25 18:29 +0100
    Re: Bug in timsort!? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-02-26 10:13 +1100
      Re: Bug in timsort!? Ian Kelly <ian.g.kelly@gmail.com> - 2015-02-25 22:51 -0700
  Re: Bug in timsort!? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-25 16:50 +0000
  Re: Bug in timsort!? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-25 16:55 +0000
  Re: Bug in timsort!? Chris Kaynor <ckaynor@zindagigames.com> - 2015-02-25 08:56 -0800
  Re: Bug in timsort!? Chris Angelico <rosuav@gmail.com> - 2015-02-26 04:18 +1100
  Re: Bug in timsort!? Peter Otten <__peter__@web.de> - 2015-02-25 18:21 +0100
  Re: Bug in timsort!? Ian Kelly <ian.g.kelly@gmail.com> - 2015-02-25 12:42 -0700
  Re: Bug in timsort!? Serhiy Storchaka <storchaka@gmail.com> - 2015-02-26 09:33 +0200

csiph-web