|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Jason Proctor <jproctor@persons.marlboro.edu>:
> It was very clever not actually telling us how you did it,
> so we wouldn't be influenced by your algorithm.
It wasn't clever; it was vanity. I didn't want anyone else to see how
crappy my algorithm was.
> It's not obvious how you generated your list of nodes to compare.
Those are just examples. When I said
> > The common ancestor of D and G is B;
I meant that if the function is given D and G as arguments, it should
return B.
> Assuming the latter, is this youngest common ancestor function the sort of
> thing you want to optimize for (thus 18 lines being "too long") or is it
> just an incidental feature? Or somewhere in between?
I want the code to be simple; I want the algorithm to be efficient in
space and time.
> My first thought was if, in addition to the parent() method, there were an
> ancestors() method that returns a complete list. To optimize speed (at
> the expense of memory, of course), carry the list around with the node.
> If that's not an option, generate it each time. Step through $list1 until
> you find an element in $list2, or return undef.
If the ancestor lists have sizes M and N, that takes O(MN) time. It
seems to me that it should be possible to do it faster.
> If finding parents is expensive (another tree search?),
Finding parents is cheap.
> Either way, I don't think you're looking at much less than 15-20 "lines".
> You could apply some obfuscation to make it take less vertical space, but
> you're not likely to make it much less computationally complex.
I wonder what reasons you have for saying so.
-
**Majordomo list services provided by PANIX <URL:http://www.panix.com>**
**To Unsubscribe, send "unsubscribe phl" to majordomo@lists.pm.org**
|
|