>>>>> "VY" == Volkan YAZICI <[EMAIL PROTECTED]> writes:
[...]
VY> Sizin algoritmanın Lisp/Scheme ile yazımına ya da kendisine
VY> getireceğiniz öneriler nelerdir?
Setleri ne ile kodladiginiza bagli biraz da bu. Mesela sayiyla
yaparsaniz (hafizadan tasarruf):
(defun set-converter (num set) ;yavas!
(loop for i from 0 below (length set)
for bits = num then (ash bits -1)
when (oddp bits) collect (nth i set)))
deneyelim
CL-USER> (set-converter 3 '(1 2 3 4 5))
(1 2)
CL-USER> (set-converter 7 '(1 2 3 4 5))
(1 2 3)
CL-USER> (set-converter 8 '(1 2 3 4 5))
(4)
CL-USER> (set-converter 11 '(1 2 3 4 5))
(1 2 4)
O zaman butun kombinasyonlar icin sayi saymaniz kafi:
(defun combinations-num (set)
(loop for i from 0 below (ash 1 (length set))
collect i))
CL-USER> (let ((set '(1 2 3 4)))
(dolist (encoded-subset (combinations-num set))
(print (set-converter encoded-subset set))))
NIL
(1)
(2)
(1 2)
(3)
(1 3)
(2 3)
(1 2 3)
(4)
(1 4)
(2 4)
(1 2 4)
(3 4)
(1 3 4)
(2 3 4)
(1 2 3 4)
NIL
CL-USER>
Tabii hizli olsun istiyorsaniz mesela soyle birsey de deneyebilirsiniz:
(defun make-set-converter (set)
(let* ((set-size (length set))
(set-array (make-array set-size :initial-contents set)))
(compile nil
`(lambda (num)
(declare
(optimize (speed 3) (debug 0) (safety 0)))
(loop for i fixnum from 0 below ,set-size
for bits of-type (unsigned-byte ,set-size) = num then (ash
bits -1)
when (oddp bits) collect (svref ,set-array i))))))
CL-USER> (defvar set100 (loop for i from 1 to 100 collect i))
SET100
CL-USER> set100
(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100)
CL-USER> (defvar hizli-conv)
HIZLI-CONV
CL-USER> (setf hizli-conv (make-set-converter set100))
;;temizlik
#<FUNCTION {B256BCD}>
CL-USER> (format t "~b~%" 31337357)
1110111100010101110001110
CL-USER> (set-converter 31337357 set100)
(1 3 4 8 9 10 12 14 18 19 20 21 23 24 25)
CL-USER> (funcall hizli-conv 31337357)
(1 3 4 8 9 10 12 14 18 19 20 21 23 24 25)
CL-USER> (time (dotimes (i 10000) (set-converter 31337357 set100)))
Evaluation took:
0.043 seconds of real time
0.044003 seconds of user run time
0.0 seconds of system run time
0 page faults and
1,277,952 bytes consed.
NIL
CL-USER> (time (dotimes (i 10000) (funcall hizli-conv 31337357)))
Evaluation took:
0.033 seconds of real time
0.032002 seconds of user run time
0.0 seconds of system run time
0 page faults and
1,277,952 bytes consed.
NIL
Boyle uzar gider. (Cok ciddiye almayin hata yapmis olabilirim).
BM
_______________________________________________
cs-lisp mailing list
[email protected]
http://church.cs.bilgi.edu.tr/lcg
http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp
