Re: Lucky numbers in Python
Op Thursday 30 Apr 2015 04:55 CEST schreef Ian Kelly: On Wed, Apr 29, 2015 at 6:01 PM, Cecil Westerhof ce...@decebal.nl wrote: Op Thursday 30 Apr 2015 00:38 CEST schreef Ian Kelly: In that case you can definitely omit the middle term of the slice, which will be both more concise and clearer in intent, though probably not significantly faster. It is certainly nit faster. It is even significantly slower. With the middle term lucky_numbers(int(1e6)) takes 0.13 seconds. Without it takes 14.3 seconds. Hundred times as long. That would be rather surprising, since it's the same operation being performed, so I did my own timing and came up with 0.25 seconds (best of 3) with the middle term and 0.22 seconds without. I suspect that you tested it as del sieve[skip_count - 1 : skip_count] (which would delete only one item) rather than del sieve[skip_count - 1 :: skip_count]. Yeah, that is how I interpreted omitting the middle term. But it seemed to give the right results. With your amendment it runs slightly faster. With 1E7 it is 8.0 and 7.7. So almost 4% faster. -- Cecil Westerhof Senior Software Engineer LinkedIn: http://www.linkedin.com/in/cecilwesterhof -- https://mail.python.org/mailman/listinfo/python-list
Re: Lucky numbers in Python
Because I want the code to work with Python 3 also, the code is now: def lucky_numbers(n): Lucky numbers from 1 up-to n http://en.wikipedia.org/wiki/Lucky_number if n 3: return [1] sieve = list(range(1, n + 1, 2)) sieve_index = 1 while True: sieve_len = len(sieve) if (sieve_index + 1) sieve_len: break skip_count = sieve[sieve_index] if sieve_len skip_count: break del sieve[skip_count - 1 : : skip_count] sieve_index += 1 return sieve It looks like the list in: sieve = list(range(1, n + 1, 2)) does not have much influence in Python 2. So I was thinking of leaving the code like it is. Or is it better to check and do the list only with Python 3? -- Cecil Westerhof Senior Software Engineer LinkedIn: http://www.linkedin.com/in/cecilwesterhof -- https://mail.python.org/mailman/listinfo/python-list
Re: Lucky numbers in Python
On 04/30/2015 02:55 PM, Cecil Westerhof wrote: Because I want the code to work with Python 3 also, the code is now: def lucky_numbers(n): Lucky numbers from 1 up-to n http://en.wikipedia.org/wiki/Lucky_number if n 3: return [1] sieve = list(range(1, n + 1, 2)) sieve_index = 1 while True: sieve_len = len(sieve) if (sieve_index + 1) sieve_len: break skip_count = sieve[sieve_index] if sieve_len skip_count: break del sieve[skip_count - 1 : : skip_count] sieve_index += 1 return sieve It looks like the list in: sieve = list(range(1, n + 1, 2)) does not have much influence in Python 2. So I was thinking of leaving the code like it is. Or is it better to check and do the list only with Python 3? I'd do something like this at top of the module: try: range = xrange except NameError as ex: pass then use range as it is defined in Python3. if that makes you nervous, then define irange = xrange, and if it gets a NameError exception, irange = range -- DaveA -- https://mail.python.org/mailman/listinfo/python-list
Re: Lucky numbers in Python
On Wed, Apr 29, 2015 at 12:24 PM, Cecil Westerhof ce...@decebal.nl wrote: I was wondering if there is a way to do this: for del_index in range((sieve_len // skip_count) * skip_count - 1, skip_count - 2, -skip_count): del sieve[del_index] in a more efficient way. You can delete using slices. del sieve[(sieve_len // skip_count) * skip_count - 1 : skip_count - 2 : -skip_count] Now you no longer need to do the iteration in reverse, which makes the slicing simpler: del sieve[skip_count - 1 : (sieve_len // skip_count) * skip_count : skip_count] And although it's not clear to me what this is supposed to be doing, you probably no longer need the middle term if the intention is to continue deleting all the way to the end of the list (if it is then I think you have a bug in the existing implementation, since the last item in the list can never be deleted). del sieve[skip_count - 1 :: skip_count] -- https://mail.python.org/mailman/listinfo/python-list
Re: Lucky numbers in Python
Op Wednesday 29 Apr 2015 21:57 CEST schreef Ian Kelly: On Wed, Apr 29, 2015 at 12:24 PM, Cecil Westerhof ce...@decebal.nl wrote: I was wondering if there is a way to do this: for del_index in range((sieve_len // skip_count) * skip_count - 1, skip_count - 2, -skip_count): del sieve[del_index] in a more efficient way. You can delete using slices. del sieve[(sieve_len // skip_count) * skip_count - 1 : skip_count - 2 : -skip_count] Now you no longer need to do the iteration in reverse, which makes the slicing simpler: del sieve[skip_count - 1 : (sieve_len // skip_count) * skip_count : skip_count] I expected that it could be done more efficiently, but did not expect such a big difference: more as hundred times. The old situation took 20 seconds for 100. The new takes 0.17. The code is know (I added a missing check): def lucky_numbers(n): if n 3: return [1] sieve = range(1, n + 1, 2) sieve_index = 1 while True: sieve_len = len(sieve) if (sieve_index + 1) sieve_len: break skip_count = sieve[sieve_index] if sieve_len skip_count: break del sieve[skip_count - 1 : (sieve_len // skip_count) * skip_count : skip_count] sieve_index += 1 return sieve And although it's not clear to me what this is supposed to be doing, you probably no longer need the middle term if the intention is to continue deleting all the way to the end of the list (if it is then I think you have a bug in the existing implementation, since the last item in the list can never be deleted). What do you mean by this? Executing: lucky_numbers(5) gives: [1, 3] So the last element (5) is deleted. -- Cecil Westerhof Senior Software Engineer LinkedIn: http://www.linkedin.com/in/cecilwesterhof -- https://mail.python.org/mailman/listinfo/python-list
Re: Lucky numbers in Python
On Wed, Apr 29, 2015 at 3:45 PM, Cecil Westerhof ce...@decebal.nl wrote: Op Wednesday 29 Apr 2015 21:57 CEST schreef Ian Kelly: And although it's not clear to me what this is supposed to be doing, you probably no longer need the middle term if the intention is to continue deleting all the way to the end of the list (if it is then I think you have a bug in the existing implementation, since the last item in the list can never be deleted). What do you mean by this? Executing: lucky_numbers(5) gives: [1, 3] So the last element (5) is deleted. Off by one error on my part. This is why negative skip values on ranges and slices are not recommended: they're confusing. :-) In that case you can definitely omit the middle term of the slice, which will be both more concise and clearer in intent, though probably not significantly faster. -- https://mail.python.org/mailman/listinfo/python-list
Re: Lucky numbers in Python
On Wed, Apr 29, 2015 at 2:45 PM, Cecil Westerhof ce...@decebal.nl wrote: I was wondering if there is a way to do this: for del_index in range((sieve_len // skip_count) * skip_count - 1, skip_count - 2, -skip_count): del sieve[del_index] in a more efficient way. You can delete using slices. del sieve[(sieve_len // skip_count) * skip_count - 1 : skip_count - 2 : -skip_count] Now you no longer need to do the iteration in reverse, which makes the slicing simpler: del sieve[skip_count - 1 : (sieve_len // skip_count) * skip_count : skip_count] I expected that it could be done more efficiently, but did not expect such a big difference: more as hundred times. The old situation took 20 seconds for 100. The new takes 0.17. Its not too surprising, as deleting the non-end element of a list is a O(n) operation - it must copy all elements in the list into a new list each time. This means that your algorithm is roughly O(n*n*log(n)) performance - n for each list delete, which is wrapped in a for loop of n iterations, which is wrapped in a while loop which will run log(n) times (I think that while loop will run log(n) times, but have not actually tested the math). Deleting a slice should take n time as well, however it is now done only once rather than once per item to be removed, which should reduce the overall algorithm to O(n*log(n)) time - aka, a HUGE difference with any moderate to large input. Chris -- https://mail.python.org/mailman/listinfo/python-list
Re: Lucky numbers in Python
On Thu, 30 Apr 2015 05:57 am, Ian Kelly wrote: On Wed, Apr 29, 2015 at 12:24 PM, Cecil Westerhof ce...@decebal.nl wrote: I was wondering if there is a way to do this: for del_index in range((sieve_len // skip_count) * skip_count - 1, skip_count - 2, -skip_count): del sieve[del_index] in a more efficient way. You can delete using slices. del sieve[(sieve_len // skip_count) * skip_count - 1 : skip_count - 2 : -skip_count] Now you no longer need to do the iteration in reverse, which makes the slicing simpler: del sieve[skip_count - 1 : (sieve_len // skip_count) * skip_count : skip_count] True, but *probably* at the expense of speed. When you delete items from a list, the remaining items have to be moved, which takes time, especially for very large lists. Most of the time, rather than deleting items, it is faster to set them to a placeholder (for example None) and then copy the ones which aren't None in a separate loop: def erat(n): Return a list of primes up to and including n. This is a fixed-size version of the Sieve of Eratosthenes, using an adaptation of the traditional algorithm. erat(30) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] if n 2: return [] # Generate a fixed array of integers. arr = list(range(n+1)) # A list is faster than an array. # Cross out 0 and 1 since they aren't prime. arr[0] = arr[1] = None i = 2 while i*i = n: # Cross out all the multiples of i starting from i**2. for p in range(i*i, n+1, i): arr[p] = None # Advance to the next number not crossed off. i += 1 while i = n and arr[i] is None: i += 1 # Copy the items which aren't None. return list(filter(None, arr)) The above is written for Python 3. In Python 2, you can safely drop the two calls to list() since both range and filter already return lists. Another alternative is to use slice assignment of the slices that you don't delete, rather than deleting directly: del alist[5:55] is similar to: alist[:] = alist[:4] + alist[55:] # Note the [:] on the left. Which is faster will probably depend on the specifics of the list. But of course for small lists, none of this matters and you should just use whatever is easiest and most natural to read. -- Steven -- https://mail.python.org/mailman/listinfo/python-list
Re: Lucky numbers in Python
Op Thursday 30 Apr 2015 00:38 CEST schreef Ian Kelly: On Wed, Apr 29, 2015 at 3:45 PM, Cecil Westerhof ce...@decebal.nl wrote: Op Wednesday 29 Apr 2015 21:57 CEST schreef Ian Kelly: And although it's not clear to me what this is supposed to be doing, you probably no longer need the middle term if the intention is to continue deleting all the way to the end of the list (if it is then I think you have a bug in the existing implementation, since the last item in the list can never be deleted). What do you mean by this? Executing: lucky_numbers(5) gives: [1, 3] So the last element (5) is deleted. Off by one error on my part. This is why negative skip values on ranges and slices are not recommended: they're confusing. :-) In that case you can definitely omit the middle term of the slice, which will be both more concise and clearer in intent, though probably not significantly faster. It is certainly nit faster. It is even significantly slower. With the middle term lucky_numbers(int(1e6)) takes 0.13 seconds. Without it takes 14.3 seconds. Hundred times as long. -- Cecil Westerhof Senior Software Engineer LinkedIn: http://www.linkedin.com/in/cecilwesterhof -- https://mail.python.org/mailman/listinfo/python-list
Re: Lucky numbers in Python
On Wed, Apr 29, 2015 at 6:01 PM, Cecil Westerhof ce...@decebal.nl wrote: Op Thursday 30 Apr 2015 00:38 CEST schreef Ian Kelly: In that case you can definitely omit the middle term of the slice, which will be both more concise and clearer in intent, though probably not significantly faster. It is certainly nit faster. It is even significantly slower. With the middle term lucky_numbers(int(1e6)) takes 0.13 seconds. Without it takes 14.3 seconds. Hundred times as long. That would be rather surprising, since it's the same operation being performed, so I did my own timing and came up with 0.25 seconds (best of 3) with the middle term and 0.22 seconds without. I suspect that you tested it as del sieve[skip_count - 1 : skip_count] (which would delete only one item) rather than del sieve[skip_count - 1 :: skip_count]. -- https://mail.python.org/mailman/listinfo/python-list
Re: Lucky numbers in Python
On Wed, Apr 29, 2015 at 6:11 PM, Steven D'Aprano steve+comp.lang.pyt...@pearwood.info wrote: On Thu, 30 Apr 2015 05:57 am, Ian Kelly wrote: On Wed, Apr 29, 2015 at 12:24 PM, Cecil Westerhof ce...@decebal.nl wrote: I was wondering if there is a way to do this: for del_index in range((sieve_len // skip_count) * skip_count - 1, skip_count - 2, -skip_count): del sieve[del_index] in a more efficient way. You can delete using slices. del sieve[(sieve_len // skip_count) * skip_count - 1 : skip_count - 2 : -skip_count] Now you no longer need to do the iteration in reverse, which makes the slicing simpler: del sieve[skip_count - 1 : (sieve_len // skip_count) * skip_count : skip_count] True, but *probably* at the expense of speed. When you delete items from a list, the remaining items have to be moved, which takes time, especially for very large lists. Most of the time, rather than deleting items, it is faster to set them to a placeholder (for example None) and then copy the ones which aren't None in a separate loop: You're correct, but I think this would be difficult to apply to the OP's algorithm since the list indexing depends on the items from previous iterations having been removed. -- https://mail.python.org/mailman/listinfo/python-list
