Re: Linear Time Tree Traversal Generator

On Thu, Sep 22, 2016 at 3:32 AM, Ian Kelly wrote: > On Tue, Sep 20, 2016 at 11:03 AM, Rob Gaddi > wrote: >> The only thing that's O(N log N) in that is the number of actual yield >> calls. If you're doing pretty much anything with those

Re: Linear Time Tree Traversal Generator

On Thu, Sep 22, 2016 at 3:15 AM, Random832 wrote: > Or you can give up on recursion. Recursive tree traversal is generally > associated with passing in a callback in rather than implementing an > iterable-like interface that can be used with a caller's for-loop > anyway. >

Re: Linear Time Tree Traversal Generator

On Tue, Sep 20, 2016 at 11:03 AM, Rob Gaddi wrote: > The only thing that's O(N log N) in that is the number of actual yield > calls. If you're doing pretty much anything with those values as > they're being iterated over then they'll dominate the timing, and

Re: Linear Time Tree Traversal Generator

On Wed, Sep 21, 2016, at 10:39, ROGER GRAYDON CHRISTMAN wrote: > Which only highlights my disappointment that my tree > traversal itself was O(n log n), unless I gave up on yield. Or you can give up on recursion. Recursive tree traversal is generally associated with passing in a callback in

Re: Linear Time Tree Traversal Generator

On Thu, Sep 22, 2016 at 12:39 AM, ROGER GRAYDON CHRISTMAN wrote: > Which only highlights my disappointment that my tree > traversal itself was O(n log n), unless I gave up on yield. > As a teacher I'm stuck with either > a) a data structure that can only get its maximal speed >

Re: Linear Time Tree Traversal Generator

Since I was asked how I got different running times for my two code fragments, I'll try to apply them to a very simple tree: 4 2 6 1 3 5 7 >def __iter__(node): > for x in iter(node._left): > yield x > yield node._value > for x in

Re: Linear Time Tree Traversal Generator

the generator is supposed to avoid. > > Now, I did see that itertools has a chain method for concatenating > iterators, so it would be nice to concatenate the results from the > recursive calls without the for loops, but I have no idea how to > squeeze the 'yield node._value' in bet

Re: Linear Time Tree Traversal Generator

On Tue, Sep 20, 2016, at 23:34, Steve D'Aprano wrote: > One of us is badly missing something. The problem is the number of times next is called. Here, it'll be more clear if we wrap the iterator in the original example to print each time next is called. class WrappedIterator(): def

Re: Linear Time Tree Traversal Generator

On Wed, 21 Sep 2016 12:47 pm, Chris Angelico wrote: > On Wed, Sep 21, 2016 at 12:34 PM, Steve D'Aprano > wrote: >> "since values from the leaves of the tree have to be yielded >> multiple times to the top of the tree" >> >> Each leaf is yielded once, and I

Re: Linear Time Tree Traversal Generator

On Wed, 21 Sep 2016 02:46 am, ROGER GRAYDON CHRISTMAN wrote: > I am trying to find a better (i.e. more efficient) way to implement a > generator that traverses a tree. > > The current model of the code (which is also used by a textbook I am > teaching from does this) > >def __iter__(node):

Re: Linear Time Tree Traversal Generator

On Wed, 21 Sep 2016 12:44 pm, Random832 wrote: > On Tue, Sep 20, 2016, at 22:34, Steve D'Aprano wrote: >> I'm afraid I don't understand this. This is a standard binary tree >> inorder traversal. Each node is visited once, and there are N nodes, >> so I make that out to be O(N) not O(N log N). I'm

Re: Linear Time Tree Traversal Generator

On Wed, Sep 21, 2016 at 12:34 PM, Steve D'Aprano wrote: > "since values from the leaves of the tree have to be yielded > multiple times to the top of the tree" > > Each leaf is yielded once, and I don't understand what you mean by yielding > to the top of the

Re: Linear Time Tree Traversal Generator

On Tue, Sep 20, 2016, at 22:34, Steve D'Aprano wrote: > I'm afraid I don't understand this. This is a standard binary tree > inorder traversal. Each node is visited once, and there are N nodes, > so I make that out to be O(N) not O(N log N). I'm afraid I can't parse > your final clause: > >

Re: Linear Time Tree Traversal Generator

On Wed, 21 Sep 2016 02:46 am, ROGER GRAYDON CHRISTMAN wrote: > I am trying to find a better (i.e. more efficient) way to implement a > generator that traverses a tree. > > The current model of the code (which is also used by a textbook I am > teaching from does this) > >def __iter__(node):

Re: Linear Time Tree Traversal Generator

On Tue, Sep 20, 2016 at 9:46 AM, ROGER GRAYDON CHRISTMAN d...@psu.edu> wrote: >I am trying to find a

Re: Linear Time Tree Traversal Generator

(self): return chain(self._left, [self._value], self._right) i. e. you wrap the value in an iterable. But I don't see how this could help in terms of big O. > Is there hope for a linear-time tree-traversal generator, or will > I have just have to settle for an n-log-n ge

Re: Linear Time Tree Traversal Generator

On Tue, Sep 20, 2016 at 9:46 AM, ROGER GRAYDON CHRISTMAN wrote: > I am trying to find a better (i.e. more efficient) way to implement a > generator > that traverses a tree. > > The current model of the code (which is also used by a textbook I am > teaching > from does this) > >

Re: Linear Time Tree Traversal Generator

I did see that itertools has a chain method for concatenating > iterators, so it would be nice to concatenate the results from the > recursive calls without the for loops, but I have no idea how to > squeeze the 'yield node._value' in between them. > > Is there hope for a linear-tim

Re: Linear Time Tree Traversal Generator

On Wed, Sep 21, 2016 at 2:46 AM, ROGER GRAYDON CHRISTMAN wrote: > The current model of the code (which is also used by a textbook I am teaching > from does this) > >def __iter__(node): > for x in iter(node._left): > yield x > yield node._value >

Linear Time Tree Traversal Generator

squeeze the 'yield node._value' in between them. Is there hope for a linear-time tree-traversal generator, or will I have just have to settle for an n-log-n generator or a linear time behavior with linear extra space? Roger Christman instructor Pennsylvania State University -- https://mail.pyth