Finding the Min for positive and negative in python 3.3 list

[Norah Jones]

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

 

[Steven D'Aprano]

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.

 

[Wolfgang Maier]

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

 

[Oscar Benjamin]

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

 

[Wolfgang Maier]

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

 

[Chris Angelico]

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

 

[Peter Otten]

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

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.

 

[Steven D'Aprano]

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.

 

[Wolfgang Maier]

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

 

[Mark Lawrence]

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

 

[Steven D'Aprano]

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.

 

[88888 Dihedral]

Wolfgang Maieræ–¼ 2013å¹´3月13日星期三UTC+8下åˆ6時43分38秒寫é“：

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

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.

 

[88888 Dihedral]

Wolfgang Maieræ–¼ 2013å¹´3月13日星期三UTC+8下åˆ6時43分38秒寫é“：

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

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.