Emre
Aldığın Kod Paul Graham'ın "Ansi Common Lisp" kitabından.
Maalesef kitap online değil ve elimde değil ve kutuphane'de "out".
Graham'ın kodun hangi sorunu çözdüğünü iddia ettiğini görmek isterim.
Bu kod bu sorunu çözmüyor, çözemez.
İstersen bunu deneyin!
Try this!
(shortest-path '1 '26 '((1 5)
(5 1)
(5 12)
(5 17)
(12 26)
(12 28)
(12 54)))
daha da kötü bir sonuç!
assoc bildiğimiz assoc ise, bu kod çalışamaz.
kodu Scheme'e çevirdim, aynı buglar mevcut. (buglu Scheme ektedir) Kodu
çalışır haline getirdim ancak hala performans açısından büyük listeler
için berbat olması lazım. Performansını da çözmek de zor değil.
Bu sorun çözümü besbelli basit bir Bilgisayar Bilimleri sorunu.
So a programming challenge for any student in any year. Solve either
part of Emre's problem
(a) find and correct the bugs in Paul Graham's code. Emre has
demonstrated one, my example above demonstrates another.
(b) produce a version of Graham's code that demonstrates the expected
O(e+v) performance
To help you, I have translated Paul Graham's code from ANSI LISP into
Scheme. (The code only works on a very small subset of the possible
inputs, which is also true of the original).
The first student(s) producing clearly independent solutions to either
of these two problems will get extra marks if they are currently taking
any course from me, and if they are not taking a course from me, then
they can bank the extra marks for a time when they do take a course from
me.
Deadline 0900 Wednesday 21 December
Sorry, Emre, if you are in a hurry, come and see me!
cs
Emre Sevinç wrote:
Bir programci (MySQL ve PHP) $u tür bir sey sormus:
Asagidaki gibi bir tablo olsun:
ID ContactID
1 5
5 12
5 17
12 26
12 28
12 54
Amac, IDsi verilmis iki kullanici arasindaki minimum yolu bulmak.
Söz gelimi, 1 ile 54 arasindaki min yol:
1-5-12-54
Kendisi bunu MySQL'de yaptigini ama tablo büyüdükce zorlandigini söylemis
Ben de merak ettim, acaba Lisp (ya da Scheme) ile yapilsaydi nasil
olurdu diye. Internet'te
bakinirken Graham'in bir uygulamasini gördüm:
(defun shortest-path (start end net)
(bfs end (list (list start)) net))
(defun bfs (end queue net)
(if (null queue)
nil
(let ((path (car queue)))
(let ((node (car path)))
(if (eql node end)
(reverse path)
(bfs end
(append (cdr queue)
(new-paths path node net))
net))))))
(defun new-paths (path node net)
(mapcar #'(lambda (n)
(cons n path))
(cdr (assoc node net))))
Ancak bekledigim sekilde sonuc vermedi:
CL-USER> (shortest-path '1 '26 '((1 5)
(5 12)
(5 17)
(12 26)
(12 28)
(12 54)))
(1 5 12 26)
Ama:
CL-USER> (shortest-path '1 '54 '((1 5)
(5 12)
(5 17)
(12 26)
(12 28)
(12 54)))
NIL
Yani 1 ile 54 arasindaki yolu bulamadi. Sebebine dair bir aciklama
yapabilecek
olan var mi?
Asil derdim bir tür benchmark yapacak bir Lisp kodu ile kisa bir test
yapmak
mesela o MySQL programcisindan 10.000 satirlik verisini alip, bunu Lisp'e
verip birkac kere calistirip bir bakmak Lisp ne kadar sürüyor diye
(tabii daha
optimize ve düzgün calisan shortest-path Lisp kodu bulmak/gelistirmek
mümkün,
onunla kiyaslamak daha iyi olur).
Belki ben bir seyler bulana/gelistirene dek benden önce birileri bir
seyler önerir.
Emre S.
_______________________________________________
cs-discuss mailing list
[EMAIL PROTECTED]
http://cs.bilgi.edu.tr/mailman/listinfo/cs-discuss
(define assoc-null
(lambda (q alist)
(let ((answer (assoc q alist)))
(cond
((not answer) null)
(else answer)))))
(define cdr-null
(lambda (x)
(cond
((null? x) null)
(else (cdr x)))))
(define shortest-path
(lambda (start end net)
(bfs end (list (list start)) net)))
(define bfs
(lambda (end queue net)
(if (null? queue)
null
(let ((path (car queue)))
(let ((node (car path)))
(if (eq? node end)
(reverse path)
(bfs end
(append (cdr queue)
(new-paths path node net))
net)))))))
(define new-paths
(lambda (path node net)
(map (lambda (n)
(cons n path))
(cdr-null (assoc-null node net)))))
_______________________________________________
cs-lisp mailing list
[email protected]
http://church.cs.bilgi.edu.tr/lcg
http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp
