Lucky numbers in Python

[Steven D'Aprano]

On Thu, 30 Apr 2015 05:57 am, Ian Kelly wrote:

> On Wed, Apr 29, 2015 at 12:24 PM, Cecil Westerhof <Cecil at 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