in reply to Re^2: Challenge: Another Infinite Lazy List
in thread Challenge: Another Infinite Lazy List
The two approaches are not the same at all. Say there are N numbers and R prime factors. The merge methods use:
N*(1/p1 + 1/p2 + ... 1/pR)*(R-1)
comparison operations to process a list of size N.
The filter method tests each number with a single gcd calculation, which is O(logN) and is independent of the total number of factors. So to produce a list of size N should be O(NlogN).
Depending on the size and quantity of factors, one or the other will be better. I would expect the filter to be better when there are many small factors, and the merge to be better when there are few factors or the factors are large.
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^4: Challenge: Another Infinite Lazy List
by Roy Johnson (Monsignor) on Mar 19, 2005 at 00:04 UTC | |
Re^4: Challenge: Another Infinite Lazy List
by tlm (Prior) on Mar 18, 2005 at 22:18 UTC | |
by tall_man (Parson) on Mar 19, 2005 at 00:38 UTC |
In Section
Seekers of Perl Wisdom