Re: Finding the Min for positive and negative in python 3.3 list
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 +, 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 n0), 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(-1000,1000) 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Finding the Min for positive and negative in python 3.3 list
Steven D'Aprano steve+comp.lang.python at pearwood.info writes: On Tue, 12 Mar 2013 17:03:08 +, 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 n0), 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(-1000,1000) 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Finding the Min for positive and negative in python 3.3 list
On 13 March 2013 10:43, Wolfgang Maier wolfgang.ma...@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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Finding the Min for positive and negative in python 3.3 list
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Finding the Min for positive and negative in python 3.3 list
On Wed, Mar 13, 2013 at 10:23 PM, Oscar Benjamin oscar.j.benja...@gmail.com wrote: On 13 March 2013 10:43, Wolfgang Maier wolfgang.ma...@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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Finding the Min for positive and negative in python 3.3 list
On Wed, Mar 13, 2013 at 10:34 PM, Wolfgang Maier wolfgang.ma...@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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Finding the Min for positive and negative in python 3.3 list
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Finding the Min for positive and negative in python 3.3 list
On Wed, 13 Mar 2013 11:23:22 +, Oscar Benjamin wrote: On 13 March 2013 10:43, Wolfgang Maier wolfgang.ma...@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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Finding the Min for positive and negative in python 3.3 list
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Finding the Min for positive and negative in python 3.3 list
On 13/03/2013 14:12, Steven D'Aprano wrote: On Wed, 13 Mar 2013 11:23:22 +, Oscar Benjamin wrote: On 13 March 2013 10:43, Wolfgang Maier wolfgang.ma...@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 -- http://mail.python.org/mailman/listinfo/python-list
Finding the Min for positive and negative in python 3.3 list
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Finding the Min for positive and negative in python 3.3 list
- Original Message - 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 -- http://mail.python.org/mailman/listinfo/python-list min(a) and min([e for e in a if e =0] Cheers, JM -- IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you. -- http://mail.python.org/mailman/listinfo/python-list
Re: Finding the Min for positive and negative in python 3.3 list
Norah Jones nh.jones01 at gmail.com 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 try this: min(a) = -30 min([n for n in a if i0]) = 1 of course, you have to figure out what you want to do with a zero value. -- http://mail.python.org/mailman/listinfo/python-list
Re: Finding the Min for positive and negative in python 3.3 list
min(a) This does not return a negative minimum on input [1] (because there is none). and min([e for e in a if e =0] This does not return a positive minimum on input [0] (because there is none). I would have said: pos_min = min(e for e in a if e 0) neg_min = min(e for e in a if e 0) And then deal with the ValueError when there is no such minimum, as appropriate. -- Devin -- http://mail.python.org/mailman/listinfo/python-list
Re: Finding the Min for positive and negative in python 3.3 list
On 3/12/2013 1:03 PM, 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 If this is homework, stop reading and do it yourself ;-) Otherwise... min(i for i in a if i 0) 1 max(i for i in a if i 0) -10 min(i for i in a if i 0) -30 You did not specify if you would include 0 in a pos min (0 is neither really positive or negative). -- Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: Finding the Min for positive and negative in python 3.3 list
Wolfgang Maier wolfgang.maier at biologie.uni-freiburg.de writes: Norah Jones nh.jones01 at gmail.com 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 try this: min(a) = -30 min([n for n in a if n0]) = 1 of course, you have to figure out what you want to do with a zero value. the i above has to be an n, of course, sorry for that typo. by the way, if you need both values and your list is really huge, an explicit for loop checking each number whether it's the current negative and positive minimum might be faster, but that would have to be tested. Also, I'm wondering whether you could somehow exploit the fact that if your list contains 0 (or 1 depending on how you want to treat zero values) you have for sure found the minimum for your positive numbers? -- http://mail.python.org/mailman/listinfo/python-list
Re: Finding the Min for positive and negative in python 3.3 list
On Tue, 12 Mar 2013 17:03:08 +, 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 -- http://mail.python.org/mailman/listinfo/python-list
