RSS

İyi Lisp, Kötü Lisp, Güzel Lisp: Karakter katarları üzerinden arama tarama optimizasyonu

08 Dec

1500 küsur kadar karakter katarını (string) bir yerde depola ve ardından verilen bir karakter katarının o 1500lük listede olup olmadığına bakıp doğru ya da yanlış döndüren bir fonksiyon yaz.

Gayet basit, sıradan, kısa bir işlevsellik.

Çömez Lisp hacker tarzı:


CG-USER(19): *alive-entities*
("abanoz" "abi" "abla" "acaip" "adam" "ahtapot" ... )

(find "zebra" *alive-entities* :test #'string-equal)

Sonuç: Çalışır ve gayet yavaş çalışır. Her şey bir liste olarak düşünülemez mi ki sendromu.

Cin gibi Lisp hacker tarzı:


(ellerimle-sana-kek-yaptim-binary-search "zebra" *alive-entities*)

Sonuç: Kendi implementasyonunu test etmek zorunda kal, hata ayıkla, algoritmik karmaşıklık ancak O(log n) seviyesine inebilsin.

Deneyimli Lisp hacker tarzı:


(defparameter *alive-entities* (make-hash-table :test (function equalp)))

(loop :for word in *words* :do (setf (gethash word *alive-entities*) word))

(time (loop :repeat 10000 :do (gethash "zebra" *alive-entities*)))

Sonuç: Çömez uygulamaya kıyasla 10-15 kat hız artışı, daha az hafıza kullanımı. Hazırda duran hash tablosu işlevselliğinden faydalanma rahatlığı. Algoritmik karmaşıklık O(1) seviyesine iner.

Tabii derlenmiş düzenli ifadeler yahut trie gibi veriyapıları da kullanılabilir. Deneyimli bir Lisp ustasının dediği gibi mevcut “hash” işlevselliği hayat kurtarır ve ani optimizasyon hevesi ölümle sonuçlanabilir.

Detaylar ve güzel çözümler için: [Usenet] c.l.l. – How optimized is this string searching method?

Advertisements
 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: