Next time, try to prove your tenacity by tracking down the problem yourself, please :)
I didn't mean to hog the credit, Christian, and you did most of the work. Let's go back to our earlier correspondence::
I'm coding up a Sudoku technique that involves chains going from one of the 81 cells to another one, beginning & ending on different numbers. There's thousands, maybe tens of thousands of such chains. OK. There are rules to glue two chains together, and make new ones, which then go on this large list of chains. Etc. What's a good speed implementation for this?
Well, I don't know Sudoku and don't have the time to learn about it. So I can't follow what programming technique you're using and what you might be missing. It's only a guess when I suspect that you're building too much data at once in memory, and might profit from lazy evaluation (streams). I did suggest that to you in a different occasion once. You seem to think mathematically, so my guess is that you're programming in a rather descriptive way and do not care nor think about how memory is being used during processing; using lazy evaluation in the right places makes memory being used only on demand, without changing the program much.
Christian, I'm not having memory problems for my Sudoku program. I've never noticed that I was taking up more than 2% of the 2GB memory. My programs run for a long time in spite of the lack of memory problems. I'm trying to raise a general problem that has nothing to do with Sudoku, other than this: there are 81 cells with 9 possible values, and (* 9 81) = 729.
Now let's consider a relation on this set of 729 element, R subset 729 x 729 R happens to be symmetric, i.e. if (x, y) in R, then (y, x) in R also, but that's probably not important. Suppose we have a way of generating R from a smaller subset. So we start with R_1 subset 729 x 729 and we'll build R as the union of some R_n, for n = 1, 2, 3... We have a way of constructing R_{n+1} from R_n and R_1 like this. We're given a predicate Glue? : 729 x 729 -> Boolean and the rule is: If (x, y) in R_1, and (a, b) in R_n, then (x, b) in R_{n+1} iff (Glue? b x) => #t Let me write this recursion rule in Scheme, even using an undefined function, although of course this would be terribly slow code:
(define (R n) (if (= n 1) R_1 (bi-filter-map (lambda (a-b x-y) (let ([a (first a-b)] [b (second a-b)] [x (first x-y)] [y (second x-y)]) (and (Glue? b x) (list a y)))) R_1 (R (sub1 n)))))
OK. Then there's a rule saying when any element (x, y) in R_n does any good, given by a predicate
Eliminate? : R_n x 729 -> Boolean
If an elimination takes place, we quit, otherwise we build R_{n+1}. But I think the slow part is building R_{n+1}, because R_1 is a list of a few thousand pairs, and R can be over 50,000 pairs. n could be large, possibly as large as 81, but for my long-running programs, n doesn't seem to get above 7 or so. I would imagine good schemers had some tricks to do this much faster than my code.
Christian, back to your suggestion of using streams to reduce memory consumption on my other program, I can't imagine how this might work. What happened there is that I was building a large list, onto which I would `merge' smaller lists. The merging was destructive: if an element in the smaller list occurred in the large list, both elements disappear. This merge-smaller-lists-on process would continue until the large list was empty, or else somehow it was shown that the large list couldn't become empty. This business went a lot faster when I switched to trees, but I think the extra memory usage eventually did me in.
I can't see how streams would help. I don't think I'm just thinking mathematically. I think I need the entire large list, and that's why it's hogging so much memory. If I just needed a procedure to calculate elements of of the large list, and then calculate elements as they were needed, that would help minimize memory consumption...