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

Groups > comp.lang.python > #41178

Re: Finding the Min for positive and negative in python 3.3 list

Show all headers | View raw

Chris Angelico <rosuav <at> gmail.com> writes:

>
> > Sort cannot be O(log(n)) and it cannot be faster than a standard O(n)
> > minimum finding algorithm. No valid sorting algorithm can have even a
> > best case performance that is better than O(n). This is because it
> > takes O(n) just to verify that a list is sorted.
> 
> Or looking at it another way: Sorting a list will require, at a bare
> minimum, comparing every element against at least one other element -
> if you could reduce it below that, there would be some element whose
> position you cannot know. Finding the minimum requires precisely that
> number of comparisons: each item against the one current minimum. :)
> 
> ChrisA
> 

Shame on me! You really shouldn't post things, while working on something else
that needs all your attention. You're absolutely right with what you're saying.
I was so fixed on speeding things up with the use of bisect that I wasn't really
thinking carefully about the sorting, and I was delighted when I saw that my
solution was speeding up the range() input example.
Unfortunately, it's only speedy for this example because the input is actually
sorted from the start (so sorted just checks the list -> O(n)). When you use it
on shuffled input, performance is really poor as opposed to the simple min()
solution, so as pointed out by you the costs of sorting are higher than the gain
from using bisect.
What started this whole mess was my gut feeling that you should somehow be able
to exploit all the information you have, and that is that the second minimum
you're looking for cannot be negative, so is at least 0 (or 1 depending on how
you decide to treat 0). So I thought that under this restriction there should be
a faster way to find the minimum than with min(). It only fooled me into
thinking that bisect could be used for it though. Is it really impossible to
beat the min() solution then?

Thanks for your feedback,
Wolfgang

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

Thread

Finding the Min for positive and negative in python 3.3 list Norah Jones <nh.jones01@gmail.com> - 2013-03-12 17:03 +0000
  Re: Finding the Min for positive and negative in python 3.3 list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-03-13 01:57 +0000
    Re: Finding the Min for positive and negative in python 3.3 list Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> - 2013-03-13 10:43 +0000
      Re: Finding the Min for positive and negative in python 3.3 list 88888 Dihedral <dihedral88888@googlemail.com> - 2013-03-14 04:45 -0700
      Re: Finding the Min for positive and negative in python 3.3 list 88888 Dihedral <dihedral88888@googlemail.com> - 2013-03-14 04:45 -0700
    Re: Finding the Min for positive and negative in python 3.3 list Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-03-13 11:23 +0000
      Re: Finding the Min for positive and negative in python 3.3 list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-03-13 14:12 +0000
        Re: Finding the Min for positive and negative in python 3.3 list Mark Lawrence <breamoreboy@yahoo.co.uk> - 2013-03-13 14:37 +0000
    Re: Finding the Min for positive and negative in python 3.3 list Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> - 2013-03-13 11:34 +0000
      Re: Finding the Min for positive and negative in python 3.3 list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-03-13 14:43 +0000
    Re: Finding the Min for positive and negative in python 3.3 list Chris Angelico <rosuav@gmail.com> - 2013-03-13 22:36 +1100
    Re: Finding the Min for positive and negative in python 3.3 list Chris Angelico <rosuav@gmail.com> - 2013-03-13 22:38 +1100
    Re: Finding the Min for positive and negative in python 3.3 list Peter Otten <__peter__@web.de> - 2013-03-13 13:00 +0100
    Re: Finding the Min for positive and negative in python 3.3 list Wolfgang Maier <wolfgang.maier@biologie.uni-freiburg.de> - 2013-03-13 14:17 +0000

csiph-web