Re: [cs-lisp] Re: Türkçe Fonksiyon İsimler i (Was: Re: Aquamacs-CM'de calismadi; LispWorks Personal'de calisti)

[Chris Stephenson]

TARIK ÖZKANLI wrote:
 Her dilde lisp kodu yazılabilmeli.
 Yazılamıyorsa yazılabilmesini sağlamak iyi bir çalışma olurdu bence.

Scheme (en az DrSCheme versiyonu) her unicode character kabul eder.

-- 
Chris Stephenson

İstanbul Bilgi Üniversitesi
Bilgisayar Bilimleri Bölüm Başkanı

___
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

Programming challenge: Re: [cs-lisp] Re: PHP+MySQL versus Lisp: Shortest Path problemi ile ilgili

[Chris Stephenson]

1.
OK we misunderstood the input format - it is neighbour lists, not pairs 
of contacts, Emre's example test data misled us.


2.
My challenge to my students still stands (modified in the light of our 
new information).

a) Modify the Graham code to work on pairs of contacts
b) Find the -algorithmic- inefficiency in Graham's code and correct it. 
My example (misunderstood) test data gives a clue to the algorithmic 
inefficiency.
c) Solve the implementation inefficiencies in Graham's code to get down 
to a solution that is O(e+v) or, at the very worst, O( (e+v) log (e+v))


I once again attach the scheme version of the Graham code.

3.
Technicalities:-
There are two inefficiencies in Graham's code

(a) the algorithmic inefficiency that is the subject of challenge 2(b).

(b) the use of inherently time inefficient LISP structures - this is 
important, but -much- less important than (a). LISP/Scheme, of course, 
offers alternative, more efficient, structures, or you can easily and 
cheaply build your own.


4.
Cember's problem:
a) I repeat that this is a problem whose solution is LINEAR in the total 
size of its input. It is therefore easily soluble, in Cember's practical 
situation, without blowing up the server, even for tens of thousands of 
subscribers. You can make that hundreds of thousands of subscribers, 
given the likely e/v ratio (quite low) and the likely pattern of 
contacts. O(e+v) is for finding ALL shortest paths starting at a give 
node. We only want one.
b) IF the Cember SQL solution has the same -algorithmic- inefficiency as 
Graham's solution that will explain the explosions.
c) Those on the mail lists who are proposing cacheing are missing the 
point. If we keep the neighbour lists in primary memory, this problem is 
trivial. If there is a performance problem, do -not- cache the shortest 
paths (it is a list of size O(n^3)!) Cache the neighbour lists!! We know 
when we update the neighbour lists in the database, so we can keep them 
in a simple write through cache.
d) Language choice is not important. Whatever language the existing 
system is written in, use that. PHP gives extensible arrays, efficiently 
implemented as hash tables, and easy interface to the database. Given 
that you then only have to write seven lines of code, even I would be 
prepared to (in fact prefer to!) write it in PHP: then wash my hands, of 
course. Writing this particular algorithm efficiently in LISP/Scheme 
requires doing some unlispy things or writing some complicated code. Why 
bother with the interfacing problems for no significant gain? Actually 
you are exaggerating the interfacing problems.


Emre, put Cember in touch with me. I will solve their problem. It is 
trivial.


After 0900 on Wednesday I will publish my solutions.

Sorry, Can Burak, shortest path is an -easy- problem!

CS




Can Burak Cilingir wrote:


[ ... ]


What you say is: Once your server is crunched and cached
the results of those queries, ok, it won't crash if the
same queries are made. But of course, each time brand new
queries with different Contacts are generated.

Could I make myself clear this time?



I was already clear on that but trying to implement caching somehow. 
My question for the previous mail was not is caching can handle the 
load or not. It was the point of my first mail (do that once a day) 
and understood that is not possible.


so my question is is there a better way to cache this? (see my 
paragragh below Maybe we need a trade-off here)




 function shortest-path (membera memberb)
 {
 if ispathcached (membera memberb)

Probably not.


You are absolutely right. When I browse such sites, I rarely click on 
people whom I already know.




  p = getcachedpath (membera memberb)
  t = getcachedtime (membera memberb)

 //is cache still valid?
 for each member of p as m
  mt = getmodificationtimeofconnlist(m)
  if (mt  t)
  {
  np = regeneratecache(membera memberb)
  return np
  }

And you imagine connections are rock hard?
Maybe our good old acquaintance has just left the
network. I'm making the same query, you and me
but the network data has changed. So you have
to modify your cache. That means recalculating.
What an acquaintance! Anyway, again you had to
calculate. Lots of calculations, people are
clicking, think of 10.000 people network, a few
thousand online, every minute a few 10 people
are coming, partially connected and making queries
which are not cached yet.

Maybe we need a trade-off here.



we can cache some intermediate paths and somehow calculate the not so 
shortest path.  a - c is (a g j o d c) for a-d, you can assume (a g 
j o d) although there may be a path such that (a w d) if you need a 
connection, we have that. but if you need the shortest path this is 
not the answer. I think this is better than showing nothing.


We are also talking about shortest path which is not an easy to 
solve problem. and doing this over and over again. I am curious how 
orkut 

[cs-lisp] Re: Another programming challenge - Another Clue Re: [cs-discuss] PHP+MySQL versus Lisp: Shortest Path problemi ile ilgili -

[Chris Stephenson]

Emre and everyone

Kod dzgn almyor
The Graham code , even with input in the correct format, does NOT work
correctly.

Consider this input

(shortest-path 1 54 '((1 5 ) (5 1 12 17) ( 12 26 28 55) (17 1)))

This should produce the answer () or nil, because there is no path from
1 to 54.

It does not. The fact that it does not also exposes indirectly the
algorithmic problem with his code.

CS

Emre Sevinc wrote:

  
  
  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 zdgn iddia ettigini grmek
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 zmyor, 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 kt bir sonu!
assoc bildigimiz assoc ise, bu kod alisamaz.
  
Kod calisiyor. Tabii ben, elimde kitap olmadan giristigim
icin ne tr 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 aisindan byk
listeler
iin berbat olmasi lazim. Performansini da zmek de zor degil.
  
Yukaridaki Common Lisp kodu grdgm kadari ile dzgn
calisiyor (biraz daha bytp karmasiklastirdim inputu gene
dzgn 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 grlebiliyor.
  
Tail-recursive hale getirilirse herhalde hafiza problemi
halledilebilir, hiz konusunda ise su anda bir fikrim yok.
  
 Bu sorun zm 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 demo

[cs-lisp] Another programming challenge - Re: [cs-discuss] PHP+MySQL versus Lisp: Shortest Path problemi ile ilgili -

[Chris Stephenson]

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
512
517
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
cs-lisp@cs.bilgi.edu.tr
http://church.cs.bilgi.edu.tr/lcg
http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp

[cs-lisp] Re: [cs-discuss] Java - Scheme ki yaslamasi, somut proje üzerinden

[Chris Stephenson]

SISC bir tür Scheme implementasyonu değil. Tam R5RS Scheme. SISC 
kullanarak Java'da yazdığım Robotworld'un Scheme versiyonu çıkardım. 
SISC'i epey bir taramadan sonra seçtim. Tıkır tıkır çalışıyor.


Bu RW versiyonu hem 2004 lise yarışmamız hem ilkokul çocuklara yönelik 
programlama deneylerimiz  için kullandık. Gerçekten kolaydı. Vaktimin 
çoğu RW'nin editörü yazarak gitti.


SISCWeb de çok ilginç. Java'da olan herşey Scheme den erişebilir oluyor. 
Dolaysıyla çok güzel web  uygulamalar yazmak kolay oluyor. Birden  bütün 
Java kutuphaneler Scheme içinde senin oluyor çünkü. Ayrıca continuation 
tarzında web uygulama yazabilirsin.


Merak edenlere tavsiye ederim.

cs



Emre Sevinc wrote:



Meşhur Java Internet programlama demo projesi Pet Store bu sefer bir tür
Scheme implementasyonu olan SISC ile yazilmis:


http://schemepetstore.pbwiki.com/

http://java.sun.com/blueprints/code/index.html#java_pet_store_demo

http://sisc.sourceforge.net/



___
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

[Fwd: Re: [cs-lisp] Common Lisp ve gercek hayatta ne isimize yariycak aabi?]

[Chris Stephenson]

I like this job advertisement - very much.

http://www.itasoftware.com/careers/eng/job1.php

Thanks to Haldun for posting the link that led to it!

I await solutions to all the programming problems from our students!

CS

 Original Message 
Subject: 	Re: [cs-lisp] Common Lisp ve gercek hayatta ne isimize 
yariycak aabi?

Date:   Sun, 23 Oct 2005 00:40:47 +0300
From:   Haldun Bayhantopcu [EMAIL PROTECTED]
Reply-To:   cs-lisp@cs.bilgi.edu.tr
To: cs-lisp@cs.bilgi.edu.tr
References: [EMAIL PROTECTED]



Liste cogaltilabilir tabii:
 http://www.itasoftware.com
 http://www.gensym.com

Emre Sevinç wrote:



CL ile yapilmis bazi seyler:

http://www.fazlamesai.net/index.php?a=articlesid=3425





___
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


___
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