Hmm, hadn't thought about that. Good point and you're almost certainly right; I did dash them off in five minutes for this post. I'd like to benchmark the two to be sure, though.
Try building lists that are a reasonably large fraction of your gc-able space; push-rev creates 2N storage, while the [+ lst (list _)] creates about N^2/2 storage.
Right, analysis pf algorithms--forgot about that :P In all seriousness, though, good point. The time complexity should be the same for both cases: push is O(1), and rev is O(n), so push-rev is O(n); + is O(n), so push-+ is also O(n). (Warning: IANACS (in a few years, I hope), so my analysis could be woefully, laughably wrong.)
Why O(n^2) memory, though? + will reallocate the memory for the list, so that will double the memory requirements; I can't figure out where the squaring is coming from.
Then, we add an element. + creates a new list of 1 element.
Then we add an element, we discard the previous list, and + creates a list of 2 elements. We've created a total of 3 cons cells (1 discarded)
Then we add an element, we discard the previous list, and + creates a list of 3 elements. We've created a total of 6 cons cells (3 discarded).
Basically this is a summation of an arithmetic progression. Memory used isn't exactly n^2, it's a formula ((n^2 + n)/2 or some such, IIRC), basically equal to sum of i from 1 to n; since the most significant component is the n^2, it's O(n^2).
edit: even processing time complexity is not the same, either - item copy operations still take O(1) time. rev makes O(n) copy operations and + does too, but push-rev does rev only once, while pushend does + at each push.
OK, I see what you mean. I was referring to the behaviour of pushend on one element (as opposed to using it to create a list in general), which is linear; of course, using pushend to build up a list of n elements has n * O(n) = O(n^2) memory usage. If push-rev were simply
, then a sequence of those would have the same problem: n things that require O(n) memory. But if you're intelligent about it, and reverse your list, push on all the elements, and then reverse again, you come out with O(n) space usage.
(Oh, and the formula is n(n+1)/2.)
Ah well, reading about CS in one's spare time is one thing, but actual study is another. I'm off to study all this next year, so I'll hopefully have a better grasp on it soon :) Thanks for the help.
