Prev: CL to generate native docs
Next: ATTENTION: RETAIL FANZ OUT HERE : )/ CHECK THIS OUT : )
From: Pascal J. Bourguignon on 31 Jan 2010 22:10
Joshua Taylor <tayloj(a)cs.rpi.edu> writes:
> John Thingstad wrote:
>> (defun set- (list1 list2)
>> (loop for element in list2 do
>> (setf list1 (remove element list1)))
>> list1)
>
> Why not SET-DIFFERENCE [1]?

NIH syndrome?

--
__Pascal Bourguignon__
From: Nicolas Neuss on 5 Feb 2010 04:25
Helmut Eller <eller.helmut(a)gmail.com> writes:

> * John Thingstad [2010-01-30 02:18+0100] writes:
>
>> Been learning unix system administration lately so I haven't had much
>> time to program. (Unless you call basic scripting programming.) Today I
>> took some time off so I made a rough prototype of a sudoku. To make this
>> elegant and general would require some more work but still a fun
>> diversion.
>
> I once translated Peter Norvig's Python code
> http://norvig.com/sudoku.html to Lisp. While the Lisp version runs a
> bit faster,

Hmm. How much is a a bit faster for you? If I interpret Norvig
correctly, his Python code needs more than 10 seconds while I observe
only 0.5 seconds (using SBCL) with your version.

> I have to admit that the Python version is shorter and easier to read.

I have not really tried hard to improve on your code, but one could gain
several lines (and IMO also some clarity) by using some general purpose
utility functions (probably most of them in Alexandria), e.g. Grahams
AIF and SINGLE? (your SINGELTON?), and the LRET which I have proposed at
some point (a LET returning its last argument).

E.g., your DFSEARCH function would then look like

(defun dfsearch (board)
(and board
(aif (most-constrained-square board)
(some (lambda (d) (dfsearch (assign (copy-seq board) it d)))
(svref board it))
board)))

After such changes, I think that the CL code would be about as short
(and as nice, although that is subjective, of course) as the Python code
and would run (even without any optimization effort!) much faster. And
that is the prime advantage of CL in my eyes.

Nicolas

> (defpackage :sudo
> (:use :cl))
> (in-package :sudo)
>
> (defun square (row col) (+ (* row 9) col))
> (defun row (square) (floor square 9))
> (defun col (square) (mod square 9))
> (defun boxstart (coord) (- coord (mod coord 3)))
>
> (defun rect (row height col width)
> (loop for r from row repeat height
> append (loop for c from col repeat width
> collect (square r c))))
>
> (defparameter *squares* (rect 0 9 0 9))
>
> (defparameter *units*
> (map 'vector
> (lambda (s)
> (list (rect (row s) 1 0 9)
> (rect 0 9 (col s) 1)
> (rect (boxstart (row s)) 3 (boxstart (col s)) 3)))
> *squares*))
>
> (defparameter *peers*
> (map 'vector
> (lambda (s) (remove s (reduce #'union (aref *units* s))))
> *squares*))
>
> (defvar *digits* (loop for i from 1 to 9 collect i))
>
> (defun dfsearch (board)
> (cond ((not board) nil)
> ((let* ((s (most-constrained-square board)))
> (cond ((not s) board)
> ((some (lambda (d) (dfsearch (assign (copy-seq board) s d)))
> (svref board s))))))))
>
> (defun most-constrained-square (board)
> (let ((min 10)
> (sq nil))
> (loop for vs across board for i from 0 do
> (let ((len (length vs)))
> (cond ((= len 2) (return i))
> ((< 1 len min) (setq min len sq i))))
> finally (return sq))))
>
> (defun assign (board s d)
> (catch 'inconsistent
> (loop for d2 in (aref board s)
> unless (= d d2) do (eliminate board s d2))
> board))
>
> (defun eliminate (board s d)
> (unless (member d (aref board s))
> (return-from eliminate board))
> (let ((set (setf (aref board s) (remove d (aref board s)))))
> (when (null set)
> (throw 'inconsistent nil))
> (when (singelton? set)
> (loop for s2 in (aref *peers* s) do
> (eliminate board s2 (car set))))
> (dolist (u (aref *units* s))
> (let ((dplaces (loop for ss in u
> if (member d (aref board ss)) collect ss)))
> (when (null dplaces)
> (throw 'inconsistent nil))
> (when (singelton? dplaces)
> (or (assign board (car dplaces) d) (throw 'inconsistent nil)))))
> board))
>
> (defun parse-grid (ggrid)
> (let ((grid (loop for c across ggrid
> if (find c "0.-123456789") collect c))
> (board (coerce (loop for s in *squares* collect *digits*) 'vector)))
> (loop for d in grid for s in *squares* do
> (unless (find d "0.-")
> (unless (assign board s (- (char-code d) (char-code #\0)))
> (return-from parse-grid nil))))
> board))
>
> (defun singelton? (set) (and set (null (cdr set))))
>
> ;; (dfsearch (parse-grid "4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......"))
>
> (defun test-top95 (filename)
> (with-open-file (s filename)
> (loop for line = (read-line s nil) for i from 0
> while line do
> (format t "line: ~d~%" i)
> (force-output)
> (dfsearch (parse-grid line)))))
>
> ;; (time (test-top95 "top95.txt"))
>
>
> Helmut
From: Helmut Eller on 5 Feb 2010 07:29
* Nicolas Neuss [2010-02-05 10:25+0100] writes:

>> I once translated Peter Norvig's Python code
>> http://norvig.com/sudoku.html to Lisp. While the Lisp version runs a
>> bit faster,
>
> Hmm. How much is a a bit faster for you?

A constant factor. I used slightly different data-structures,
eg. vectors where Norvig used dicts.

> If I interpret Norvig
> correctly, his Python code needs more than 10 seconds while I observe
> only 0.5 seconds (using SBCL) with your version.

On my machine, Python needs 7 seconds, CMUCL 1.2, and CLISP 3. Seems to
be in the same ballpark.

>> I have to admit that the Python version is shorter and easier to read.
>
> I have not really tried hard to improve on your code, but one could gain
> several lines (and IMO also some clarity) by using some general purpose
> utility functions (probably most of them in Alexandria), e.g. Grahams
> AIF and SINGLE? (your SINGELTON?), and the LRET which I have proposed at
> some point (a LET returning its last argument).
>
> E.g., your DFSEARCH function would then look like
>
> (defun dfsearch (board)
> (and board
> (aif (most-constrained-square board)
> (some (lambda (d) (dfsearch (assign (copy-seq board) it d)))
> (svref board it))
> board)))

Well, that's 6 lines; exactly as many as my version.

> After such changes, I think that the CL code would be about as short
> (and as nice, although that is subjective, of course) as the Python code
> and would run (even without any optimization effort!) much faster. And
> that is the prime advantage of CL in my eyes.

Possibly, but I think that CL's current speed advantage will melt away
when Python switches to JIT compilers.

Helmut
From: Raffael Cavallaro on 5 Feb 2010 09:38
On 2010-02-05 07:29:23 -0500, Helmut Eller said:

> Possibly, but I think that CL's current speed advantage will melt away
> when Python switches to JIT compilers.

Speed advantages are typically implementation issues, not issues with
the language design per se.

The real advantage of common lisp over python is that when you want a
piece of novel syntax or a new control structure, in python you have to
wait and hope that guido deigns to include it in some future version of
python. In common lisp you just write it yourself and get on with what
you're doing. True, you do have the source, so you could fork python,
but this is an extreme solution to what should be a trivial problem; an
extreme solution that is necessitated by the lack of syntactic
abstraction in the python language.

--
Raffael Cavallaro

From: Pillsy on 5 Feb 2010 10:28
On Feb 5, 7:29 am, Helmut Eller <eller.hel...(a)gmail.com> wrote:

> * Nicolas Neuss [2010-02-05 10:25+0100] writes:

> >> I once translated Peter Norvig's Python code
> >>http://norvig.com/sudoku.htmlto Lisp.  While the Lisp version runs a
> >> bit faster,

> > Hmm.  How much is a a bit faster for you?  

> A constant factor.  I used slightly different data-structures,
> eg. vectors where Norvig used dicts.

Well, since the algorithm is essentially the same, I'd be surprised by
anything *but* a constant factor. On my machine, the constant factor
in question, for Python 2.5.1 vs. SBCL 1.0.34, was around 10 (4.65 s
for Python, 0.475 s for SBCL). That's pretty significant, considering
no extra work was involved. Even if I forced SBCL to recompile
"sudo.lisp" before running it, I the speed-up was between a factor of
7 and 8 (0.622 s).

What really surprised and impressed me, though, was the fact that I
got almost a factor of 2 improvement from CLISP, which completed in
2.67 s (2.74 s with a recompilation of "sudo.lisp"), since CLISP
doesn't compile to native code any more than Python does. CLISP is
fast, folks.

The real advantage for the Python code, IMO, comes from its use of
list comprehensions. That's one hell of a nice language feature there,
and one that stock CL doesn't have.

OTOH, I'm not sure why you think the Python code is shorter, since
it's 85 lines (without comments or whitespace) compared to 77 for your
Lisp code.

Cheers,
Pillsy
[...]
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: CL to generate native docs
Next: ATTENTION: RETAIL FANZ OUT HERE : )/ CHECK THIS OUT : )