format-ing output, and a peek at performance

tag:blogger.com,1999:blog-5048733824376310579.post-15863487436132141242007-07-03T21:16:00.000-05:002007-07-03T23:04:52.443-05:00format-ing output, and a peek at performanceContinuing comments around the ongoing sudoku examples: Reader Leslie had a sensible comment, a post or two ago: `Why didn't you use a 2D array in the implementation, it seems more natural'. I admit, from the point of view of the puzzles themselves this would seem to be true. And if I was writing about an all-singing, all-dancing sudoku system, I'd probably be working in 2D. Actually, that's a lie; I'd probably start with (defclass sudoku ...) and hide these sorts of details. The interface would allow 2D subscripts though. In this case, I wasn't actually thinking of the problems the way you see them on paper, I was thinking about them as problems on a set of vertices with certain connectivity. I've renamed some variables and things to hide this, but a 1D array was natural. There's no reason we couldn't have written essentially the same code in 2D, though. The neighbors-of function would be nearly the same, now it would collect up (i,j) pairs instead of indices n. It would be less clean, because you'd have to take apart the i,j pairs all over the place to use them (or #'apply to them). Also, there isn't a nice ordering now of how to call the inner recursion. All these things could be done fairly nicely. There are some performances reasons that may push you to use a 1D representation like this, but at this stage of the game that's the last thing we want to drive the design. Still, it will come up. Before we get into all that though, Leslie's comment reminded me that it's kind of counterintuitive to look at these things as vectors though, so I'll put together a little printing function and as an added bonus it will work for 1D or 2D representations: <pre> (defun print-sudoku (array &optional (stream t)) (let ((control-string "~{~A~^ ~#[~;~;~;| ~;~;~;| ~;~;~;~%~ ~;~;~;| ~;~;~;| ~;~;~;~%~ ~;~;~;| ~;~;~;| ~;~;~;~%~ ------+-------+------~%~ ~;~;~;| ~;~;~;| ~;~;~;~%~ ~;~;~;| ~;~;~;| ~;~;~;~%~ ~;~;~;| ~;~;~;| ~;~;~;~%~ ------+-------+------~%~ ~;~;~;| ~;~;~;| ~;~;~;~%~ ~;~;~;| ~;~;~;| ~;~;~;~%~ ~;~;~;| ~;~;~;| ~;~;~;~%~ ~:;~]~}" ) (displaced (make-array 81 :element-type (array-element-type array) :displaced-to array))) (loop for x across displaced if (= x 0) collect "." into res else collect x into res finally (format stream control-string res)))) </pre> You can get tricky about format strings, and with all the repetition here I'm sure I could have done something much more compact, but I like the way spreading it out like this makes it pretty obvious what I'm doing even if you're not so used to format. It's also assuming I only feed it nice input, etc. but we won't worry about that now. Here's how it looks: <pre> BLOG> *slow* #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 9 7 0 3 0 0 0 0 0 0 1 0 0 6 0 5 0 0 0 0 4 7 0 8 0 0 2 0 0 0 0 0 2 0 0 6 0 3 1 0 0 4 0 0 0 0 0 0 8 0 0 1 6 7 0 8 7 0 0 0 0 0 0) BLOG> (print-sudoku *slow*) . . . | . . . | . . . . . . | . . . | 9 . . 9 7 . | 3 . . | . . . ------+-------+------ . 1 . | . 6 . | 5 . . . . 4 | 7 . 8 | . . 2 . . . | . . 2 | . . 6 ------+-------+------ . 3 1 | . . 4 | . . . . . . | 8 . . | 1 6 7 . 8 7 | . . . | . . . BLOG> (loop with x = (make-array `(9 9)) for n below 81 do (setf (row-major-aref x n) (aref * n)) finally (return x)) #2A((0 0 0 0 0 0 0 0 0) (0 0 0 0 0 0 9 0 0) (9 7 0 3 0 0 0 0 0) (0 1 0 0 6 0 5 0 0) (0 0 4 7 0 8 0 0 2) (0 0 0 0 0 2 0 0 6) (0 3 1 0 0 4 0 0 0) (0 0 0 8 0 0 1 6 7) (0 8 7 0 0 0 0 0 0)) BLOG> (print-sudoku *) . . . | . . . | . . . . . . | . . . | 9 . . 9 7 . | 3 . . | . . . ------+-------+------ . 1 . | . 6 . | 5 . . . . 4 | 7 . 8 | . . 2 . . . | . . 2 | . . 6 ------+-------+------ . 3 1 | . . 4 | . . . . . . | 8 . . | 1 6 7 . 8 7 | . . . | . . . </pre> So that looks a bit better. Where I'm heading with all this stuff, by the way (at least as an excuse to discuss bits an pieces) is to make a puzzle generator. Whenever I make a change in the generator, I'll want to verify it has a single unique solution. So each puzzle will get solved many, many times -- and not just looking for a first solution either. Now might be a good time for a sanity check then. I've shown that this algorithm works, but what sort of times are we looking at? You might wonder why the particular puzzle above is called *slow*. Here's why: <pre> BLOG> (time (find-first-solution *slow*)) Evaluation took: 92.649 seconds of real time 88.828224 seconds of user run time 1.617718 seconds of system run time [Run times include 5.09 seconds GC run time.] 0 calls to %EVAL 0 page faults and 7,634,328,056 bytes consed. #(1 2 3 9 4 6 7 8 5 8 4 6 2 5 7 9 3 1 9 7 5 3 8 1 6 2 4 3 1 2 4 6 9 5 7 8 5 6 4 7 1 8 3 9 2 7 9 8 5 3 2 4 1 6 2 3 1 6 7 4 8 5 9 4 5 9 8 2 3 1 6 7 6 8 7 1 9 5 2 4 3) BLOG> (print-sudoku *) 1 2 3 | 9 4 6 | 7 8 5 8 4 6 | 2 5 7 | 9 3 1 9 7 5 | 3 8 1 | 6 2 4 ------+-------+------ 3 1 2 | 4 6 9 | 5 7 8 5 6 4 | 7 1 8 | 3 9 2 7 9 8 | 5 3 2 | 4 1 6 ------+-------+------ 2 3 1 | 6 7 4 | 8 5 9 4 5 9 | 8 2 3 | 1 6 7 6 8 7 | 1 9 5 | 2 4 3 </pre> For what it's worth, that's compiled under sbcl 1.0.6 on a intel dual-core 2.16Ghz. Hmmmm. We may have a bit of a problem here. This is where a neophyte lisp user might get discouraged, thinking `what use is all this if I can't use the code for anything computationally expensive?'. Don't worry about that. Next time I'll start to describe several simple changes -- and will see a speedup of, oh, about 10,000 times.skahttp://www.blogger.com/profile/07206056709352200940noreply@blogger.com