Title: RE: Another programming challenge - Re: [cs-discuss] PHP+MySQL versus Lisp: Shortest Path problemi ile ilgili -
-Original Message-
From: Chris Stephenson [mailto:[EMAIL PROTECTED]]
Sent: Sat 12/17/2005 12:07 AM
To: Emre Sevinc
Cc: cs-lisp@cs.bilgi.edu.tr; cs-discuss; [EMAIL PROTECTED]; [EMAIL PROTECTED]
Subject: Another programming challenge - Re: [cs-discuss] PHP+MySQL versus Lisp: Shortest Path problemi ile ilgili -
Aldigin Kod Paul Graham'in Ansi Common Lisp kitabindan.
Maalesef kitap online degil ve elimde degil ve kutuphane'de out.
Graham'in kodun hangi sorunu çözdügünü iddia ettigini görmek isterim.
Kitap muhtemelen Sinan'da ya da Can Burak'ta ya da Haldun'da
(ya da baska bir Common Lisp sevdalisinda, kim acaba? ;-)
Bu kod bu sorunu çözmüyor, çözemez.
Istersen 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 bildigimiz assoc ise, bu kod çalisamaz.
Kod calisiyor. Tabii ben, elimde kitap olmadan giristigim
icin ne tür input bekledigini anlayamamisim basta. BM'nin
tavsiyeleri dogrultusunda kurcalayinca input'un nasil olmasi
gerektigi anlasildi.
Tekrar kodu gecmek gerekirse:
==
(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
===
bfs, anladigimiz kadari ile Breadth First Search manasinda.
Ve her elemanin komsularini yazip öyle arayacak olursak:
===
(time (shortest-path '1 '54 '(
(1 5)
(5 1 12 17)
(12 5 26 28 54)
(17 5)
(26 12)
(28 12)
(54 12
Evaluation took:
0.0 seconds of real time
0.0 seconds of user run time
0.0 seconds of system run time
0 page faults and
8,192 bytes consed.
(1 5 12 54)
Dogru sonucu yani 1 - 5 - 12 - 54 sonucunu buluyor. Windows'ta
CLISP'te ve GNU/Linux'ta SBCL ile denedim.
kodu Scheme'e çevirdim, ayni buglar mevcut. (buglu Scheme ektedir) Kodu
çalisir haline getirdim ancak hala performans açisindan büyük listeler
için berbat olmasi lazim. Performansini da çözmek de zor degil.
Yukaridaki Common Lisp kodu gördügüm kadari ile düzgün
calisiyor (biraz daha büyütüp karmasiklastirdim inputu gene
düzgün sonuc verdi)
===
CL-USER (time (shortest-path '1 '19 '((1 5)
(5 1 12 17)
(12 5 26 28 54)
(17 5)
(26 12)
(28 12)
(54 12 47)
(47 15)
(15 2)
(2 15 100 101)
(3 100)
(100 2 15 19
Evaluation took:
0.417 seconds of real time
0.054991 seconds of user run time
0.014998 seconds of system run time
46 page faults and
1,211,352 bytes consed.
(1 5 12 54 47 15 2 100 19)
CL-USER (time (shortest-path '1 '19 '((1 5)
(5 1 12 17)
(12 5 26 28 54)
(17 5)
(26 12)
(28 12)
(54 12 47)
(47 15)
(15 2)
(2 15 100 101)
(3 100)
(100 2 15 19
Evaluation took:
0.005 seconds of real time
0.005999 seconds of user run time
0.0 seconds of system run time
0 page faults and
1,224,704 bytes consed.
(1 5 12 54 47 15 2 100 19)
CL-USER (time (shortest-path '1 '19 '((1 5)
(5 1 12 17)
(12 5 26 28 54)
(17 5)
(26 12)
(28 12)
(54 12 47)
(47 15)
(15 2)
(2 15 100 101)
(3 100)
(100 19
Evaluation took:
0.005 seconds of real time
0.004999 seconds of user run time
0.0 seconds of system run time
0 page faults and
1,204,224 bytes consed.
(1 5 12 54 47 15 2 100 19)
Hafiza acisindan problemli oldugu asikar, diger yandan
cachelemenin getirdigi tekrar hesaplamalardaki hiz
farki da görülebiliyor.
Tail-recursive hale getirilirse herhalde hafiza problemi
halledilebilir, hiz konusunda ise su anda bir fikrim yok.
Bu sorun çözümü besbelli basit bir Bilgisayar Bilimleri sorunu.
Algoritmik olarak karisik degil ancak basit olmayan kisimlarini
asagida yazacagim.
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
