Re: create tree from arrays

On 17 May 2010 16:41, David Harkness <david.h@highgearmedia.com> wrote: > Shahrzad, > > While your algorithm is correct it is very inefficient. The full array is > scanned for every element in the array. If the array contains 1,000 > elements, 1,000,000 comparisons will be performed and mktree_array() will be > called 1,000 times. This is known as order n squared: O(n^2) and is about as > slow as it gets. > > Oh, I see that you "have to use [a] recursive function." Is this is a > homework assignment? If not and you want to make it faster, you can speed up > the code by creating a new array first that maps from $a['nid'] => $a (the > array element) to create a hash table. Then loop over the array again and > use the hash table to find the parent of each element ($a) and add it to $a. > This will be much faster without being any more complex (exchange recursion > for two simple loops). > > Peace, > David > OOI, can you take a look at my first response. Is this the sort of thing you were talking about? -- ----- Richard Quadling "Standing on the shoulders of some very clever giants!" EE : http://www.experts-exchange.com/M_248814.html EE4Free : http://www.experts-exchange.com/becomeAnExpert.jsp Zend Certified Engineer : http://zend.com/zce.php?c=ZEND002498&r=213474731 ZOPA : http://uk.zopa.com/member/RQuadling