From: Pascal J.B. <pj...@in...> - 2004-06-24 19:58:00
|
Elvin Peterson writes: > Hello, > I have an function (described below), which crashes > clisp for inputs greater than 1500. The limit is > substantially larger if the function is compiled. An > empty stackdump file is generated under cygwin. > > [18]> (eratosthenes 1500) > $ > > I suspect this might be a problem with large lists, > but shouldn't there be a graceful recovery and a > message rather than a crash? The problem is not with large lists, but with deep stacks. The interpreter uses more stack space than compiled functions. > (defun generate-list (n) > "Provides the list 2...n" > (labels ((generate-reversed-list (n) > "Generates the list 2...n in the reverse order" > (if (= n 2) > (cons 2 nil) > (cons n (generate-reversed-list (1- n)))))) > (reverse (generate-reversed-list n)))) Rather use an iterative version: (defun generate-numbers>=2 (n) (let ((result nil)) (dotimes (i n) (push i result)) (cddr (nreverse result)))) (defun nremove-prime-multiples (list) (do* ((prime (car list)) (prime-multiple (+ prime prime)) (next list)) ((null (cdr next)) list) (cond ((> (cadr next) prime-multiple) (incf prime-multiple prime)) ((= (cadr next) prime-multiple) (setf (cdr next) (cddr next)) (incf prime-multiple prime)) (t (setf next (cdr next)))))) (defun sieve (list-of-integer) (do* ((result (copy-seq list-of-integer)) (next (nremove-prime-multiples result) (nremove-prime-multiples (cdr next)))) ((null (cdr next)) result)));;sieve [52]> (time (sieve (generate-numbers>=2 10000))) Real time: 3.300211 sec. ;; NOT COMPILED! Run time: 3.28 sec. Space: 159984 Bytes (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 [...] 9319 9323 9337 9341 9343 9349 9371 9377 9391 9397 9403 9413 9419 9421 9431 9433 9437 9439 9461 9463 9467 9473 9479 9491 9497 9511 9521 9533 9539 9547 9551 9587 9601 9613 9619 9623 9629 9631 9643 9649 9661 9677 9679 9689 9697 9719 9721 9733 9739 9743 9749 9767 9769 9781 9787 9791 9803 9811 9817 9829 9833 9839 9851 9857 9859 9871 9883 9887 9901 9907 9923 9929 9931 9941 9949 9967 9973) [53]> (map nil (function compile) '(generate-numbers>=2 nremove-prime-multiples sieve)) NIL [54]> (time (every (function primep) (sieve (generate-numbers>=2 100000)))) Real time: 210.57819 sec. ;; NOT COMPILED! Run time: 203.1 sec. Space: 1599984 Bytes GC: 1, GC time: 0.06 sec. T Of course, it's much faster to implement the Eratostene sieve with bitmaps: [55]> (package:load-package :com.informatimago.common-lisp.primes) T [56]> (time (every (function primep) (com.informatimago.common-lisp.primes:compute-primes-to 100000))) Real time: 7.245507 sec. Run time: 7.17 sec. Space: 48284 Bytes T [67]> (time (prog1 nil (com.informatimago.common-lisp.primes:compute-primes-to 100000))) Real time: 0.695663 sec. Run time: 0.69 sec. Space: 44784 Bytes NIL -- __Pascal Bourguignon__ http://www.informatimago.com/ There is no worse tyranny than to force a man to pay for what he does not want merely because you think it would be good for him. -- Robert Heinlein |