Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!selfless.tophat.at!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail Return-Path: 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; 'value,': 0.04; '-0700': 0.07; 'inserts': 0.07; 'append': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:80.91.229.12': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'received:lo.gmane.org': 0.09; 'traverse': 0.09; 'binary': 0.14; 'alist': 0.16; 'bieber': 0.16; 'declaimed': 0.16; 'email addr:ix.netcom.com': 0.16; 'email name:wlfraed': 0.16; 'from:addr:ix.netcom.com': 0.16; 'from:addr:wlfraed': 0.16; 'from:name:dennis lee bieber': 0.16; 'programmer,': 0.16; 'received:66.245': 0.16; 'received:dsl.mindspring.com': 0.16; 'received:mindspring.com': 0.16; 'received:wlfraed': 0.16; 'style,': 0.16; 'url:netcom': 0.16; 'url:wlfraed': 0.16; 'wulfraed': 0.16; 'list?': 0.16; 'subject:list': 0.19; 'insert': 0.19; 'appropriate': 0.21; 'right.': 0.22; 'fri,': 0.23; '(or': 0.24; 'code': 0.24; 'url:home': 0.25; 'lee': 0.29; 'position.': 0.29; 'instead': 0.29; 'second': 0.30; "one's": 0.30; 'sort': 0.31; 'this.': 0.31; 'community': 0.32; 'tend': 0.32; 'header:X -Complaints-To:1': 0.32; 'does': 0.33; 'to:addr:python-list': 0.33; 'list': 0.33; 'list.': 0.33; 'there': 0.35; 'using': 0.35; 'charset:us-ascii': 0.36; 'probably': 0.36; 'log': 0.36; 'similar': 0.37; 'ways': 0.37; 'another': 0.37; 'two': 0.37; 'received:org': 0.38; 'data': 0.38; 'subject:: ': 0.38; "i'd": 0.39; 'header:Mime-Version:1': 0.39; 'list,': 0.39; 'to:addr:python.org': 0.39; 'best': 0.60; 'dennis': 0.77; 'sort.': 0.91; 'subject:Best': 0.91; 'complexity': 0.93 X-Injected-Via-Gmane: http://gmane.org/ To: python-list@python.org From: Dennis Lee Bieber Subject: Re: Best way to insert sorted in a list Date: Fri, 17 Jun 2011 21:21:25 -0700 Organization: > Bestiaria Support Staff < References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Gmane-NNTP-Posting-Host: user-11faa5p.dsl.mindspring.com X-Newsreader: Forte Agent 3.3/32.846 X-No-Archive: YES X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 32 NNTP-Posting-Host: 82.94.164.166 X-Trace: 1308370907 news.xs4all.nl 49176 [::ffff:82.94.164.166]:52841 X-Complaints-To: abuse@xs4all.nl Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:7883 On Fri, 17 Jun 2011 13:53:10 -0700 (PDT), SherjilOzair declaimed the following in gmane.comp.python.general: > There are basically two ways to go about this. > One is, to append the new value, and then sort the list. > Another is to traverse the list, and insert the new value at the > appropriate position. > > The second one's complexity is O(N), while the first one's is O(N * > log N). > > Still, the second one works much better, because C code is being used > instead of pythons. > > Still, being a programmer, using the first way (a.insert(x); > a.sort()), does not feel right. > > What has the community to say about this ? What is the best (fastest) > way to insert sorted in a list ? How often do the inserts occur? How often do you need to access the list? If inserts tend to come in batches, I'd probably append all the inserts and use sort. If inserts come very sporadically, bisect (or similar binary search), split, join ( alist = alist[:splitpoint] + data + alist[splitpoint:] style, or similar) -- Wulfraed Dennis Lee Bieber AF6VN wlfraed@ix.netcom.com HTTP://wlfraed.home.netcom.com/