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-lisp mailing list
[email protected]
http://church.cs.bilgi.edu.tr/lcg
http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp
