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

Groups > comp.lang.python > #7883

Re: Best way to insert sorted in a list

Show key headers only | View raw

On Fri, 17 Jun 2011 13:53:10 -0700 (PDT), SherjilOzair
<sherjilozair@gmail.com> 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/

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

Thread

Best way to insert sorted in a list SherjilOzair <sherjilozair@gmail.com> - 2011-06-17 13:53 -0700
  Re: Best way to insert sorted in a list Shashank Singh <shashank.sunny.singh@gmail.com> - 2011-06-18 02:32 +0530
  Re: Best way to insert sorted in a list Ethan Furman <ethan@stoneleaf.us> - 2011-06-17 14:31 -0700
  Re: Best way to insert sorted in a list Ian Kelly <ian.g.kelly@gmail.com> - 2011-06-17 15:23 -0600
  Re: Best way to insert sorted in a list Chris Torek <nospam@torek.net> - 2011-06-17 21:48 +0000
    Re: Best way to insert sorted in a list Ethan Furman <ethan@stoneleaf.us> - 2011-06-17 15:24 -0700
    Re: Best way to insert sorted in a list Ian Kelly <ian.g.kelly@gmail.com> - 2011-06-17 17:33 -0600
      Re: Best way to insert sorted in a list Chris Torek <nospam@torek.net> - 2011-06-18 00:46 +0000
  Re: Best way to insert sorted in a list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-06-18 02:27 +0000
  Re: Best way to insert sorted in a list Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2011-06-17 21:21 -0700
  Re: Best way to insert sorted in a list Vito De Tullio <vito.detullio@gmail.com> - 2011-06-19 16:21 +0200

csiph-web