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

Groups > comp.lang.python > #41137 > unrolled thread

Finding the Min for positive and negative in python 3.3 list

Back to article view | Back to comp.lang.python

Contents

  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

#41137 — Finding the Min for positive and negative in python 3.3 list

[Multipart message — attachments visible in raw view] — view raw

For example:
a=[-15,-30,-10,1,3,5]

I want to find a negative and a positive minimum.

example: negative
print(min(a)) = -30
 
positive
print(min(a)) = 1

[toc] | [next] | [standalone]

#41159

On Tue, 12 Mar 2013 17:03:08 +0000, Norah Jones wrote:

> For example:
> a=[-15,-30,-10,1,3,5]
> 
> I want to find a negative and a positive minimum.
> 
> example: negative
> print(min(a)) = -30
>  
> positive
> print(min(a)) = 1

Thank you for providing examples, but they don't really cover all the 
possibilities. For example, if you had:

a = [-1, -2, -3, 100, 200, 300]

I can see that you consider -3 to be the "negative minimum". Do you 
consider the "positive minimum" to be 100, or 1?

If you expect it to be 100, then the solution is:

    min([item for item in a if item > 0])

If you expect it to be 1, then the solution is:

    min([abs(item) for item in a])

which could also be written as:

    min(map(abs, a))

A third alternative is in Python 3.3:

    min(a, key=abs)

which will return -1.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#41168

Steven D'Aprano <steve+comp.lang.python <at> pearwood.info> writes:

> 
> On Tue, 12 Mar 2013 17:03:08 +0000, Norah Jones wrote:
> 
> > For example:
> > a=[-15,-30,-10,1,3,5]
> > 
> > I want to find a negative and a positive minimum.
> > 
> > example: negative
> > print(min(a)) = -30
> >  
> > positive
> > print(min(a)) = 1
> 
> Thank you for providing examples, but they don't really cover all the 
> possibilities. For example, if you had:
> 
> a = [-1, -2, -3, 100, 200, 300]
> 
> I can see that you consider -3 to be the "negative minimum". Do you 
> consider the "positive minimum" to be 100, or 1?
> 
> If you expect it to be 100, then the solution is:
> 
>     min([item for item in a if item > 0])
> 
> If you expect it to be 1, then the solution is:
> 
>     min([abs(item) for item in a])
> 
> which could also be written as:
> 
>     min(map(abs, a))
> 
> A third alternative is in Python 3.3:
> 
>     min(a, key=abs)
> 
> which will return -1.
> 

thinking again about the question, then the min() solutions suggested so far
certainly do the job and they are easy to understand.
However, if you need to run the function repeatedly on larger lists, using min()
is suboptimal because its performance is an O(n) one.
It's faster, though less intuitive, to sort your list first, then use bisect on
it to find the zero position in it. Two manipulations running at O(log(n)).

compare these two functions:

def with_min(x):
    return (min(n for n in a if n<0), min(n for n in a if n>=0))

def with_bisect(x):
    b=sorted(x)
    return (b[0] if b[0]<0 else None, b[bisect.bisect_left(b,0)])

then either time them for small lists or try:

a=range(-10000000,10000000)
with_min(a)
with_bisect(a)

of course, the disadvantage is that you create a huge sorted list in memory and
that it's less readable.

Best,
Wolfgang

[toc] | [prev] | [next] | [standalone]

#41227

Wolfgang Maier於 2013年3月13日星期三UTC+8下午6時43分38秒寫道：
> Steven D'Aprano <steve+comp.lang.python <at> pearwood.info> writes:
> 
> 
> 
> > 
> 
> > On Tue, 12 Mar 2013 17:03:08 +0000, Norah Jones wrote:
> 
> > 
> 
> > > For example:
> 
> > > a=[-15,-30,-10,1,3,5]
> 
> > > 
> 
> > > I want to find a negative and a positive minimum.
> 
> > > 
> 
> > > example: negative
> 
> > > print(min(a)) = -30
> 
> > >  
> 
> > > positive
> 
> > > print(min(a)) = 1
> 
> > 
> 
> > Thank you for providing examples, but they don't really cover all the 
> 
> > possibilities. For example, if you had:
> 
> > 
> 
> > a = [-1, -2, -3, 100, 200, 300]
> 
> > 
> 
> > I can see that you consider -3 to be the "negative minimum". Do you 
> 
> > consider the "positive minimum" to be 100, or 1?
> 
> > 
> 
> > If you expect it to be 100, then the solution is:
> 
> > 
> 
> >     min([item for item in a if item > 0])
> 
> > 
> 
> > If you expect it to be 1, then the solution is:
> 
> > 
> 
> >     min([abs(item) for item in a])
> 
> > 
> 
> > which could also be written as:
> 
> > 
> 
> >     min(map(abs, a))
> 
> > 
> 
> > A third alternative is in Python 3.3:
> 
> > 
> 
> >     min(a, key=abs)
> 
> > 
> 
> > which will return -1.
> 
> > 
> 
> 
> 
> thinking again about the question, then the min() solutions suggested so far
> 
> certainly do the job and they are easy to understand.
> 
> However, if you need to run the function repeatedly on larger lists, using min()
> 
> is suboptimal because its performance is an O(n) one.
> 
> It's faster, though less intuitive, to sort your list first, then use bisect on
> 
> it to find the zero position in it. Two manipulations running at O(log(n)).
> 
> 
> 
> compare these two functions:
> 
> 
> 
> def with_min(x):
> 
>     return (min(n for n in a if n<0), min(n for n in a if n>=0))
> 
> 
> 
> def with_bisect(x):
> 
>     b=sorted(x)
> 
>     return (b[0] if b[0]<0 else None, b[bisect.bisect_left(b,0)])
> 
> 
> 
> then either time them for small lists or try:
> 
> 
> 
> a=range(-10000000,10000000)
> 
> with_min(a)
> 
> with_bisect(a)
> 
> 
> 
> of course, the disadvantage is that you create a huge sorted list in memory and
> 
> that it's less readable.
> 
> 
> 
> Best,
> 
> Wolfgang

Sorting numbers of such range M in a list of length N by radix sort 
is faster but requires more memory.

[toc] | [prev] | [next] | [standalone]

#41228

Wolfgang Maier於 2013年3月13日星期三UTC+8下午6時43分38秒寫道：
> Steven D'Aprano <steve+comp.lang.python <at> pearwood.info> writes:
> 
> 
> 
> > 
> 
> > On Tue, 12 Mar 2013 17:03:08 +0000, Norah Jones wrote:
> 
> > 
> 
> > > For example:
> 
> > > a=[-15,-30,-10,1,3,5]
> 
> > > 
> 
> > > I want to find a negative and a positive minimum.
> 
> > > 
> 
> > > example: negative
> 
> > > print(min(a)) = -30
> 
> > >  
> 
> > > positive
> 
> > > print(min(a)) = 1
> 
> > 
> 
> > Thank you for providing examples, but they don't really cover all the 
> 
> > possibilities. For example, if you had:
> 
> > 
> 
> > a = [-1, -2, -3, 100, 200, 300]
> 
> > 
> 
> > I can see that you consider -3 to be the "negative minimum". Do you 
> 
> > consider the "positive minimum" to be 100, or 1?
> 
> > 
> 
> > If you expect it to be 100, then the solution is:
> 
> > 
> 
> >     min([item for item in a if item > 0])
> 
> > 
> 
> > If you expect it to be 1, then the solution is:
> 
> > 
> 
> >     min([abs(item) for item in a])
> 
> > 
> 
> > which could also be written as:
> 
> > 
> 
> >     min(map(abs, a))
> 
> > 
> 
> > A third alternative is in Python 3.3:
> 
> > 
> 
> >     min(a, key=abs)
> 
> > 
> 
> > which will return -1.
> 
> > 
> 
> 
> 
> thinking again about the question, then the min() solutions suggested so far
> 
> certainly do the job and they are easy to understand.
> 
> However, if you need to run the function repeatedly on larger lists, using min()
> 
> is suboptimal because its performance is an O(n) one.
> 
> It's faster, though less intuitive, to sort your list first, then use bisect on
> 
> it to find the zero position in it. Two manipulations running at O(log(n)).
> 
> 
> 
> compare these two functions:
> 
> 
> 
> def with_min(x):
> 
>     return (min(n for n in a if n<0), min(n for n in a if n>=0))
> 
> 
> 
> def with_bisect(x):
> 
>     b=sorted(x)
> 
>     return (b[0] if b[0]<0 else None, b[bisect.bisect_left(b,0)])
> 
> 
> 
> then either time them for small lists or try:
> 
> 
> 
> a=range(-10000000,10000000)
> 
> with_min(a)
> 
> with_bisect(a)
> 
> 
> 
> of course, the disadvantage is that you create a huge sorted list in memory and
> 
> that it's less readable.
> 
> 
> 
> Best,
> 
> Wolfgang

Sorting numbers of such range M in a list of length N by radix sort 
is faster but requires more memory.

[toc] | [prev] | [next] | [standalone]

#41171

On 13 March 2013 10:43, Wolfgang Maier
<wolfgang.maier@biologie.uni-freiburg.de> wrote:
>
> thinking again about the question, then the min() solutions suggested so far
> certainly do the job and they are easy to understand.
> However, if you need to run the function repeatedly on larger lists, using min()
> is suboptimal because its performance is an O(n) one.
> It's faster, though less intuitive, to sort your list first, then use bisect on
> it to find the zero position in it. Two manipulations running at O(log(n)).

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.


Oscar

[toc] | [prev] | [next] | [standalone]

#41177

On Wed, 13 Mar 2013 11:23:22 +0000, Oscar Benjamin wrote:

> On 13 March 2013 10:43, Wolfgang Maier
> <wolfgang.maier@biologie.uni-freiburg.de> wrote:
>>
>> thinking again about the question, then the min() solutions suggested
>> so far certainly do the job and they are easy to understand. However,
>> if you need to run the function repeatedly on larger lists, using min()
>> is suboptimal because its performance is an O(n) one. It's faster,
>> though less intuitive, to sort your list first, then use bisect on it
>> to find the zero position in it. Two manipulations running at
>> O(log(n)).
> 
> 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.

That's almost true. It applies to comparison sorts, that is, the kind of 
sort algorithm where you have to compare the elements being sorted to 
know where they go. But it doesn't necessarily apply to non-comparison 
sorts. For example, Bead sort could in principle operate in O(sqrt(n)) 
time, or even O(1), although in practice it is O(n).

Another example is Bitonic sort, which is O(log(n)**2).

In practical terms though, you are right. There is no practical, general 
purpose sorting algorithm that can beat O(n) for arbitrary lists of data.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#41179

On 13/03/2013 14:12, Steven D'Aprano wrote:
> On Wed, 13 Mar 2013 11:23:22 +0000, Oscar Benjamin wrote:
>
>> On 13 March 2013 10:43, Wolfgang Maier
>> <wolfgang.maier@biologie.uni-freiburg.de> wrote:
>>>
>>> thinking again about the question, then the min() solutions suggested
>>> so far certainly do the job and they are easy to understand. However,
>>> if you need to run the function repeatedly on larger lists, using min()
>>> is suboptimal because its performance is an O(n) one. It's faster,
>>> though less intuitive, to sort your list first, then use bisect on it
>>> to find the zero position in it. Two manipulations running at
>>> O(log(n)).
>>
>> 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.
>
> That's almost true. It applies to comparison sorts, that is, the kind of
> sort algorithm where you have to compare the elements being sorted to
> know where they go. But it doesn't necessarily apply to non-comparison
> sorts. For example, Bead sort could in principle operate in O(sqrt(n))
> time, or even O(1), although in practice it is O(n).
>
> Another example is Bitonic sort, which is O(log(n)**2).
>
> In practical terms though, you are right. There is no practical, general
> purpose sorting algorithm that can beat O(n) for arbitrary lists of data.
>

For the newbies hanging around there's Python's own Timsort which 
apparantly has worst case performance O(n log n), best case O(n) and 
average case O(n log n).  Please don't shoot the messenger :)



-- 
Cheers.

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#41172

Oscar Benjamin <oscar.j.benjamin <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.
> 
> Oscar
> 

Oops, you're right of course.
Wrote this in a hurry before and got confused a bit.
So, the two min()s take O(n) each, the sort takes O(n),
but the bisect takes O(log n),
which means that sorting and bisecting together should still be faster
than 2xmin(), although it's a bit less striking than what I wrote first.
Thanks for the correction,
Wolfgang

[toc] | [prev] | [next] | [standalone]

#41180

On Wed, 13 Mar 2013 11:34:08 +0000, Wolfgang Maier wrote:

> Oscar Benjamin <oscar.j.benjamin <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.
>> 
>> Oscar
>> 
>> 
> Oops, you're right of course.
> Wrote this in a hurry before and got confused a bit. So, the two min()s
> take O(n) each, the sort takes O(n), but the bisect takes O(log n),
> which means that sorting and bisecting together should still be faster
> than 2xmin(), although it's a bit less striking than what I wrote first.

Not quite. In general, Big Oh values add by taking the *largest* term.

Calling min() twice is O(n) + O(n) or 2*O(n), which is just O(n) since 
Big Oh analysis ignores any multiplicative constant.

Sorting in general is O(n*log n), not O(n). If you have arbitrary, 
unsorted data, then sorting it first and then bisecting is O(n*log n) + 
O(log n), which is just O(n*log n), which is slower than O(n).

Since Big Oh doesn't tell you the actual physical cost of operations, or 
how long they take, beware of relying too much on Big Oh analysis without 
doing actual physical timings.

And in practice, min() is such a straight-forward, simple operation that 
it is hard to imagine anything beating it under normal circumstances. 
Unless you have truly vast amounts of data, the simplest solution is 
usually the best.


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#41173

On Wed, Mar 13, 2013 at 10:23 PM, Oscar Benjamin
<oscar.j.benjamin@gmail.com> wrote:
> On 13 March 2013 10:43, Wolfgang Maier
> <wolfgang.maier@biologie.uni-freiburg.de> wrote:
>>
>> thinking again about the question, then the min() solutions suggested so far
>> certainly do the job and they are easy to understand.
>> However, if you need to run the function repeatedly on larger lists, using min()
>> is suboptimal because its performance is an O(n) one.
>> It's faster, though less intuitive, to sort your list first, then use bisect on
>> it to find the zero position in it. Two manipulations running at O(log(n)).
>
> 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

[toc] | [prev] | [next] | [standalone]

#41174

On Wed, Mar 13, 2013 at 10:34 PM, Wolfgang Maier
<wolfgang.maier@biologie.uni-freiburg.de> wrote:
> Oscar Benjamin <oscar.j.benjamin <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.
>>
>> Oscar
>>
>
> Oops, you're right of course.
> Wrote this in a hurry before and got confused a bit.
> So, the two min()s take O(n) each, the sort takes O(n),
> but the bisect takes O(log n),
> which means that sorting and bisecting together should still be faster
> than 2xmin(), although it's a bit less striking than what I wrote first.
> Thanks for the correction,
> Wolfgang

Your sort is usually going to be O(n log n), not O(log n).

ChrisA

[toc] | [prev] | [next] | [standalone]

#41175

Wolfgang Maier wrote:

> Oscar Benjamin <oscar.j.benjamin <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.
>> 
>> Oscar
>> 
> 
> Oops, you're right of course.
> Wrote this in a hurry before and got confused a bit.
> So, the two min()s take O(n) each, the sort takes O(n),

O(n*log(n)) according to

<http://wiki.python.org/moin/TimeComplexity>

> but the bisect takes O(log n),
> which means that sorting and bisecting together should still be faster
> than 2xmin(), although it's a bit less striking than what I wrote first.

That's not how big-O math works. 2*O(n) is still O(n).

2*O(n) == O(n)

As n grows an O(log(n)) approach will eventually be faster than O(n), but 
that's asymptotical behaviour and allows for an arbitrary constant factor. 
For a given n you cannot decide if the O(n) or the O(log(n)) algorithm is 
faster unless you know these constant factors. 

Put another way: Iterating twice over the list doubles an unknown constant 
factor.

[toc] | [prev] | [next] | [standalone]

#41178

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web