libera/#commonlisp - IRC Chatlog
Search
1:42:29
ludston
beach: I like your "reverse-order" paper. It's using recursion in an interesting way. I am thinking this approach might have trouble though for O(n^2) algorithms. e.g. "(reduce (lambda (x y) (+ x y (reduce '+ some-large-list :from-end t))) some-large-list :from-end t)" as once the remaining stack space is small, nthcdr could be called a very large
1:46:28
ludston
This seems like a solvable problem except for in cases where you don't know the number of times that reduce will be recursively invoked.
1:50:24
ludston
My example of an O(n^2) algorithm is contrived, but yes there are algorithms where O(n^2) is optimal. Algorithms like O(n^m) are pretty rare though, given the run-time tends to become infinite when you have more than 10 elements.
3:06:20
beach
I don't have the paper fresh in memory, but as I recall, each invocation takes a logarithmic amount of stack space. It would appear to me then, that a quadratic algorithms would take logĀ² space.
3:34:09
beach
I added two more papers to http://metamodular.com/SICL today, namely "A modern implementation of the LOOP macro", and "Removing redundant tests by replicating control paths."