slice notation as values?

Antoon Pardon apardon at forel.vub.ac.be
Mon Dec 12 05:03:49 EST 2005


Op 2005-12-11, Bengt Richter schreef <bokr at oz.net>:
> On 10 Dec 2005 12:07:12 -0800, "Devan L" <devlai at gmail.com> wrote:
>
>>
>>Antoon Pardon wrote:
>>> On 2005-12-10, Duncan Booth <duncan.booth at invalid.invalid> wrote:
>>[snip]
>>> >> I also think that other functions could benefit. For instance suppose
>>> >> you want to iterate over every second element in a list. Sure you
>>> >> can use an extended slice or use some kind of while. But why not
>>> >> extend enumerate to include an optional slice parameter, so you could
>>> >> do it as follows:
>>> >>
>>> >>   for el in enumerate(lst,::2)
>>> >
>>> > 'Why not'? Because it makes for a more complicated interface for something
>>> > you can already do quite easily.
>>>
>>> Do you think so? This IMO should provide (0,lst[0]), (2,lst[2]),
>>> (4,lst[4]) ...
>>>
>>> I haven't found a way to do this easily. Except for something like:
>>>
>>> start = 0:
>>> while start < len(lst):
>>>   yield start, lst[start]
>>>   start += 2
>>>
>>> But if you accept this, then there was no need for enumerate in the
>>> first place. So eager to learn something new, how do you do this
>>> quite easily?
>>
>>>>> lst = ['ham','eggs','bacon','spam','foo','bar','baz']
>>>>> list(enumerate(lst))[::2]
>>[(0, 'ham'), (2, 'bacon'), (4, 'foo'), (6, 'baz')]
>>
>>No changes to the language necessary.
>>
> Or, without creating the full list intermediately,
>
> >>> lst = ['ham','eggs','bacon','spam','foo','bar','baz']
> >>> import itertools
> >>> list(itertools.islice(enumerate(lst), 0, None, 2))
>  [(0, 'ham'), (2, 'bacon'), (4, 'foo'), (6, 'baz')]

As far as I understand use of this idiom can turn an O(n)
algorithm into an O(n^2) algorithm.

Suppose I have a list with 10 000 elements and I want 
the sum of the first 100, the sum of the second 100 ...

One way to do that would be:

for i in xrange(0,10000,100):
  sum(itertools.islice(lst, i, i+100))

But itertools.islice would each time start from the begining
of the list and iterate over i elements before giving 100
elements to sum. Which would make this implementation O(n^2)
instead of O(n).

-- 
Antoon Pardon



More information about the Python-list mailing list