[gambit-list] strange mutation problem (bug?) (Re: "Number of arguments exceeds implementation)

Bill Richter richter at math.northwestern.edu
Tue Oct 3 22:19:48 EDT 2006


   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...



More information about the Gambit-list mailing list