-----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
"cache"lemenin 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 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
I'll be glad to see your students come up with cleve solutions in Scheme
or Common Lisp.
Now, let me tell a few things about the origin of the problem, the
real life situation.
This may help budding computer scientists understand where they
can apply their "very academic" knowledge into real life problems
(and make some money and/or reputation):
As I stated before, I've heard this problem from a PHP/MySQL
programmer.
He's running a "business" focused social network in which
members try to enlarge their business network, meet other
professionals and collaborate. Some of you may have already
heard about the website: cember.net
This site had a beautiful functionality. Whenever I clicked
on some member, let's say he/she is not in my direct connections list,
the site how I was connected to that person:
e.g. I have a list of connections: VST, CBC, Haldun
CS has some list of connections: VST, CBC
A new cember.net member arrives, let's say BM (imagine
he accepted my offer, just imagine) and now he's in
my connection list and then he sees CS and says, hmm, let me
see how I can be connected to CS, if that not-more-than-6-person
is an urban legend or not, he clicks on CS and cember.net
show (showed):
BM -> Emre -> VST -> CS
Because BM is directly connected to Emre, Emre knows VST
and of course CS knows VST directly.
This was a lovely feature. Believe me. People liked it.
Now, people and the programmer are sorry. Why? Because
the aforementioned contacts table (I've given an example
in my previous mail, you can see it below, just includes
an ID and ContactID) has grown bigger. It's now about 5 MB.
cember.net became popular, more than a few thousand members.
The machine, being a Pentium IV and having 1 GB of RAM
cannot handle that shortest path functionality anymore
when a more than tens of people click on each other to
see how they are connected.
It is implemented in MySQL, some nested selects and during
the week days, when traffic is high, it simply blows up. Boom!
cember.net programmer asked for help. People talked about SQL,
algorithms, some even said "do it in PHP" (what an advice).
Some talked about C# and .NET (believe me, they did).
The real solution to this real life problem is not a mere
and short Lisp code. You've got a GNU/Linux server, running
a PHP & MySQL & Apache based website and it needs to produce
that connections shortest path in real time. In addition
to a good performing algorithm, this is also an integration
problem:
Imagine you came up with a beautiful and high performance
Lisp code.
Now, how do you pass this input to Lisp, grab the data from
MySQL, process it, return it back to PHP and show your
members waiting for the web page?
No, don't tell me!
Go and offer cember.net to become one of their technical
consultants ;-) We're talking business here.
Understand and be aware that your Computer Science
education can give you an edge in the field of IT. Hacking
is not only about finding quick solutions, dirty kludges,
playing with some hardware and satisfying yourselves. Taking
this kind of a problem, finding the right algorithm, or finding
a better one, optimizing the implementation using your secret weapon
and then integrating it with a popular solution seamlessly is nothing
to be belittled.
This was my 2 YKRs, take it or leave it ;-)
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
_______________________________________________ cs-lisp mailing list cs-lisp@cs.bilgi.edu.tr http://church.cs.bilgi.edu.tr/lcg http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp
