Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #82261 > unrolled thread

Nested loops is strangely slow, totally at a loss.

Back to article view | Back to comp.lang.python

Contents

  Nested loops is strangely slow, totally at a loss. Shiyao Ma <i@introo.me> - 2014-12-10 13:20 +0800
    Re: Nested loops is strangely slow, totally at a loss. Steven D'Aprano <steve@pearwood.info> - 2014-12-10 06:44 +0000
      Re: Nested loops is strangely slow, totally at a loss. Chris Angelico <rosuav@gmail.com> - 2014-12-10 17:53 +1100
        Re: Nested loops is strangely slow, totally at a loss. Steven D'Aprano <steve@pearwood.info> - 2014-12-10 07:21 +0000
      Re: Nested loops is strangely slow, totally at a loss. Terry Reedy <tjreedy@udel.edu> - 2014-12-10 02:16 -0500

#82261 — Nested loops is strangely slow, totally at a loss.

When doing nested loop, the very first iteration of the innermost loop ends ultimately slow.

Let's the code speak.

The following code is quite contrived. Actually it's derived from my 3d-dct script.
The actual difference is way more significant than this example.

In case of any evil of gmail, bpaste here: https://bpaste.net/show/edfef62edb17

# this constructs a space_len x space_len x space_len 3D coordinate
import timeit
from itertools import product
space_len = 580
space = product(xrange(space_len), xrange(space_len), xrange(space_len))


sparse_cloud = product(xrange(1), xrange(1), xrange(1))

for i, j, k in sparse_cloud:
    ts = timeit.default_timer()
    if (i, j, k) in space: pass
    te = timeit.default_timer()
    print("A, finish a loop with ", te-ts)
print("Done Test A")


sparse_cloud = product(xrange(1000), xrange(1000), xrange(1000))
for i, j, k in sparse_cloud:
    ts = timeit.default_timer()
    if (i, j, k) in space: pass
    te = timeit.default_timer()
    print("B, finish a loop with ", te-ts)
print("Done Test B")


# example output
"""
('A, finish a loop with ', 2.1457672119140625e-06)
Done Test A
('B, finish a loop with ', 8.736134052276611)
('B, finish a loop with ', 1.9073486328125e-06)
('B, finish a loop with ', 0.0)
('B, finish a loop with ', 0.0)
('B, finish a loop with ', 1.1920928955078125e-06)
('B, finish a loop with ', 9.5367431640625e-07)
('B, finish a loop with ', 9.5367431640625e-07)
...
"""

We can see that the first iteration of B ends rather slow, 8.7 seconds here.

Why? I am curious about the internals, what's happening under the hood that makes this happen?

Thanks in advance!


-- 
Shiyao Ma
http://introo.me

[toc] | [next] | [standalone]

#82264

On Wed, 10 Dec 2014 13:20:25 +0800, Shiyao Ma wrote:

> When doing nested loop, the very first iteration of the innermost loop
> ends ultimately slow.
> 
> Let's the code speak.
> 
> The following code is quite contrived. Actually it's derived from my
> 3d-dct script. The actual difference is way more significant than this
> example.
> 
> In case of any evil of gmail, bpaste here:
> https://bpaste.net/show/edfef62edb17
> 
> # this constructs a space_len x space_len x space_len 3D coordinate
> import timeit
> from itertools import product
> space_len = 580
> space = product(xrange(space_len), xrange(space_len), xrange(space_len))

space will contain 580**3 == 195112000 items, but they are lazily 
generated. Once you access an item, it is gone, never to be seen again 
(until you recreate the product iterator object).


> sparse_cloud = product(xrange(1), xrange(1), xrange(1))

This, on the other hand, only has a single item, (0,0,0). When you run 
this:


> for i, j, k in sparse_cloud:
>     ts = timeit.default_timer()
>     if (i, j, k) in space: pass
>     te = timeit.default_timer()
>     print("A, finish a loop with ", te-ts)
> print("Done Test A")

it tests:

    (0,0,0) in space


which matches the very first item of space, which takes hardly any time 
at all. But having done this, you have consumed that first value.


> sparse_cloud = product(xrange(1000), xrange(1000), xrange(1000)) for i,
> j, k in sparse_cloud:
>     ts = timeit.default_timer()
>     if (i, j, k) in space: pass
>     te = timeit.default_timer()
>     print("B, finish a loop with ", te-ts)
> print("Done Test B")

Now you create a new sparse_cloud iterator, and iterate over it. The 
first loop gets

    i, j, k = 0, 0, 0

and then tried to check:

    (0,0,0) in space

*but* that item from has already been consumed. So it now runs through 
the rest of the iterator:

    (0,0,0) == (0,0,1)  # False
    (0,0,0) == (0,0,2)  # False
    (0,0,0) == (0,0,3)  # False
    ...
    (0,0,0) == (0,0,579)  # False
    (0,0,0) == (0,1,0)  # False
    (0,0,0) == (0,1,1)  # False
    ...
    (0,0,0) == (579,579,579)  # False

which takes a long time.

Now the next loop gets the values:

    i, j, k = 0, 0, 1

and then tried to check:

    (0,0,1) in space

but space is now exhausted, and it returns False immediately. And so on 
for the rest of the sparse_cloud iterator.




It would be nice if product iterators behaved like xrange() objects and 
could perform "in" tests without exhausting the iterator, but they don't. 
That's sad.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#82266

On Wed, Dec 10, 2014 at 5:44 PM, Steven D'Aprano <steve@pearwood.info> wrote:
> It would be nice if product iterators behaved like xrange() objects and
> could perform "in" tests without exhausting the iterator, but they don't.
> That's sad.

It'd be very difficult to do that in the general sense. But it should
be possible to have a multi-dimensional range object that behaves the
way Py3's range object does, including membership tests and stuff.
(Might already exist, for all I know.) That would do what the OP
wants, I think.

ChrisA

[toc] | [prev] | [next] | [standalone]

#82269

On Wed, 10 Dec 2014 17:53:05 +1100, Chris Angelico wrote:

> On Wed, Dec 10, 2014 at 5:44 PM, Steven D'Aprano <steve@pearwood.info>
> wrote:
>> It would be nice if product iterators behaved like xrange() objects and
>> could perform "in" tests without exhausting the iterator, but they
>> don't. That's sad.
> 
> It'd be very difficult to do that in the general sense. But it should be
> possible to have a multi-dimensional range object that behaves the way
> Py3's range object does, including membership tests and stuff. (Might
> already exist, for all I know.) That would do what the OP wants, I
> think.

Oh yes. If the product object has n-ordinates, then you could implement 
it something vaguely like this:

def contains(product_obj, item):
    if not isinstance(item, tuple):
        return False
    if len(item) != number_of_ordinates:
        return False
    for i, x in enumerate(item):
        if x not in ordinate[i]:
            return False
    return True


but note that this too might exhaust the product iterator, if it is 
constructed from iterators! But for the case whether it is constructed 
from xrange objects, lists, tuples, etc. it would work fine.

Strings are another funny case: consider what happens here:

("bc", "x", "1") in product("abcd", "wxyz", "1234")

It should return False, but since string containment tests operate on 
substrings not just single characters, it will wrongly return True.


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#82268

On 12/10/2014 1:53 AM, Chris Angelico wrote:
> On Wed, Dec 10, 2014 at 5:44 PM, Steven D'Aprano <steve@pearwood.info> wrote:
>> It would be nice if product iterators behaved like xrange() objects and
>> could perform "in" tests without exhausting the iterator, but they don't.
>> That's sad.
>
> It'd be very difficult to do that in the general sense. But it should
> be possible to have a multi-dimensional range object that behaves the
> way Py3's range object does, including membership tests and stuff.
> (Might already exist, for all I know.) That would do what the OP
> wants, I think.

Itertools are general tools for building specialized objects. 
itertools.product provides the iter method.

class ReitProd():  # untested
     def __init__(self, reiterable, n):
         self.reit = reiterable  # must support 'in'
         self.n = n
     def __iter__(self):
         return itertools.product(self.reit, repeat=self.n)
     def __contains__(self, seq):
	if len(seq) != self.n:
             return False
         for i, item in enumerate(it):
             if item not in self.reit:
                 return False
         return True

-- 
Terry Jan Reedy

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web