[cs-lisp] Re: Liste icindeki belli bir elemanin hangi pozisyonlarda oldugunun listesi..?
On Thu, Apr 24, 2008 at 01:40:39PM +0300, Volkan YAZICI wrote: > Can Burak Cilingir <[EMAIL PROTECTED]> writes: > > (N)ear (e)valuated (p)riority (t)ree veri tipi icerisinde sakladiginiz > > veriyi sirali olsun, olmasin BST (binary search tree) benzeri bir > > sekilde calisarak aradiginiz veriye en fazla agacin derinligi kadar > > islemde erismenizi saglar. Bu da en kotu durumda bahsettiginiz gibi > > O(n) yerine O(log(n)) performans saglayacak, n'in ozellikle buyuk > > degerleri icin kiyaslanamayacak kadar iyi bir basarim getirecektir. > > Benim burada değinmek istediğim nokta, bahsi geçen arama işlemini sadece > tek bir kez yapacaksanız doğrudan sequential scan ile listeyi taramak en > doğrusu olacaktır -- bu O(n) karmaşıklığında. Çünkü bunu herhangi bir > ağaca yerleştirmek istediğinizde veri yapısının yeni hale aktarımı için > en azından O(nlogn) adım gerekmektedir, kaldı ki bu çok iyimser bir > oran. Eğer bu arama işlemleri birden fazla kez yapılacaksa, tabii ki > sorgu tipine özel bir arama ağacı kullanmanız kaçınılmaz olacaktır. > > Şu da var ki, her veri tipi için istenilen ağaç yapısı > oluşturulamayabilir. Çünkü herhangi bir veriyi ağaçta saklayabilmeniz > için o ağaç tarafından şart koşulan karşılaştırma operatörlerinin > saklanacak veri üzerinde tanımlanması gerekmektedir. :) sanirim hala pun intended yonteminden medet umdugumu tam olarak ifade edemiyorum. > > > İyi çalışmalar. > -- Can Burak Çilingir -+-\n--+\n+++ Precise language is not the problem. Clear language is the problem. - R. Feynman signature.asc Description: Digital signature ___ 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: Liste icindeki belli bir elemanin hangi pozisyonlarda oldugunun listesi..?
Can Burak Cilingir <[EMAIL PROTECTED]> writes: > (N)ear (e)valuated (p)riority (t)ree veri tipi icerisinde sakladiginiz > veriyi sirali olsun, olmasin BST (binary search tree) benzeri bir > sekilde calisarak aradiginiz veriye en fazla agacin derinligi kadar > islemde erismenizi saglar. Bu da en kotu durumda bahsettiginiz gibi > O(n) yerine O(log(n)) performans saglayacak, n'in ozellikle buyuk > degerleri icin kiyaslanamayacak kadar iyi bir basarim getirecektir. Benim burada değinmek istediğim nokta, bahsi geçen arama işlemini sadece tek bir kez yapacaksanız doğrudan sequential scan ile listeyi taramak en doğrusu olacaktır -- bu O(n) karmaşıklığında. Çünkü bunu herhangi bir ağaca yerleştirmek istediğinizde veri yapısının yeni hale aktarımı için en azından O(nlogn) adım gerekmektedir, kaldı ki bu çok iyimser bir oran. Eğer bu arama işlemleri birden fazla kez yapılacaksa, tabii ki sorgu tipine özel bir arama ağacı kullanmanız kaçınılmaz olacaktır. Şu da var ki, her veri tipi için istenilen ağaç yapısı oluşturulamayabilir. Çünkü herhangi bir veriyi ağaçta saklayabilmeniz için o ağaç tarafından şart koşulan karşılaştırma operatörlerinin saklanacak veri üzerinde tanımlanması gerekmektedir. İyi çalışmalar. ___ 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: Liste icindeki belli bir elemanin hangi pozisyonlarda oldugunun listesi..?
On Thu, Apr 24, 2008 at 09:36:22AM +0300, Volkan YAZICI wrote: > Merhaba, > > Can Burak Cilingir <[EMAIL PROTECTED]> writes: > > Problemi eger dogru tahmin ediyorsam, bahsettiginiz isi list veritipi > > kullanarak yapmak yerine girdilerini nept veritipine cevirerek daha > > performansli calisabileceginizi tahmin ediyorum. > > Anladığım kadarı ile Aykut Bey herhangi bir elemanın belirtilen bir > liste içinde hangi pozisyonlarda yer aldığını öğrenmek istiyor. Bu her > halukarda -- liste özel bir sıralama içermediği sürece -- zaten O(n) > işlem karmaşıklığında bir problem. Bunu liste yerine başka bir veri > yapısı kullanarak yapmanın bize kayda değer bir başarım artışı > sağlayacağını zannetmiyorum. > > > list -> nept cevrimini ... > > Cahilliğimi mazur görün, "nept" nedir? (N)ear (e)valuated (p)riority (t)ree veri tipi icerisinde sakladiginiz veriyi sirali olsun, olmasin BST (binary search tree) benzeri bir sekilde calisarak aradiginiz veriye en fazla agacin derinligi kadar islemde erismenizi saglar. Bu da en kotu durumda bahsettiginiz gibi O(n) yerine O(log(n)) performans saglayacak, n'in ozellikle buyuk degerleri icin kiyaslanamayacak kadar iyi bir basarim getirecektir. tabi n yeteri kadar buyur ise klasik 4 islemin O(1) zamanda yapilamayacagini animsarsak bu sekilde bir iyilestirmeye de gitmemiz olasi. PS: Daha once belirtme geregi duymamistim ama simdi sanirim belirtmeliyim. puns intended. > > > İyi çalışmalar. > -- Can Burak Çilingir -+-\n--+\n+++ If we really understand the problem, the answer will come out of it, because the answer is not separate from the problem. - J. Krishnamurti signature.asc Description: Digital signature ___ 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: Liste icindeki belli bir elemanin hangi pozisyonlarda oldugunun listesi..?
On Thu, 24 Apr 2008, Volkan YAZICI <[EMAIL PROTECTED]> writes: > Ağız tadınıza uygun olarak KEY ve TEST seçeneklerini de -- POSITION > işlevinde olduğu gibi -- POSITIONS'a da ekleyebilirsiniz. (defun positions (item sequence &key (start 0) end (key #'identity) (test #'eql)) "Return list of positions of ITEM occuring in SEQUENCE." (check-type sequence (or vector list)) (let ((get-next-item (cond ((vectorp sequence) (let ((index 0) (size (length sequence))) (lambda () (when (< index size) (prog1 (aref sequence index) (incf index)) ((listp sequence) (lambda () (pop sequence)) (labels ((collect (position accum) (let ((candidate (funcall get-next-item))) (cond ((or (null candidate) (and end (<= end position))) accum) ((and (<= start position) (funcall test item (funcall key candidate))) (collect (1+ position) (cons position accum))) (t (collect (1+ position) accum)) (nreverse (collect 0 nil) (positions 1 '(2 1 3 4 5 11 6 7 1 9)) (positions 1 #(2 1 3 4 5 11 6 7 1 9)) (positions #\a "Yok dahA neler Artık!" :test #'char-equal :key #'char-downcase) Tabii ki kullanılmayan START, END, KEY ve TEST değişkenlerinin her adımda bir yavaşlığa neden olacağı aşikardır. Fakat çoğu CL implementasyonu (örneğin SBCL) bu tür ölü kodları optimize edebilmekte. İyi çalışmalar. ___ 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: Liste icindeki belli bir elemanin hangi pozisyonlarda oldugunun listesi..?
Merhaba, Can Burak Cilingir <[EMAIL PROTECTED]> writes: > Problemi eger dogru tahmin ediyorsam, bahsettiginiz isi list veritipi > kullanarak yapmak yerine girdilerini nept veritipine cevirerek daha > performansli calisabileceginizi tahmin ediyorum. Anladığım kadarı ile Aykut Bey herhangi bir elemanın belirtilen bir liste içinde hangi pozisyonlarda yer aldığını öğrenmek istiyor. Bu her halukarda -- liste özel bir sıralama içermediği sürece -- zaten O(n) işlem karmaşıklığında bir problem. Bunu liste yerine başka bir veri yapısı kullanarak yapmanın bize kayda değer bir başarım artışı sağlayacağını zannetmiyorum. > list -> nept cevrimini ... Cahilliğimi mazur görün, "nept" nedir? İyi çalışmalar. ___ 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: Liste icindeki belli bir elemanin hangi pozisyonlarda oldugunun listesi..?
On Wed, 23 Apr 2008, Aykut Caglayan <[EMAIL PROTECTED]> writes: > Ornegin soyle bir listem var:>'(0 1 1 0 0 1 1) > ve ben su cevabi ariyorum:> '(1 2 5 6) CL-USER> (defun positions (item list) "POSITION derivate returns list of positions of the supplied ITEM occuring in the specified LIST." (labels ((collect-positions (position accum list) (cond ((endp list) accum) ((eql item (first list)) (collect-positions (1+ position) (cons position accum) (rest list))) (t (collect-positions (1+ position) accum (rest list)) (nreverse (collect-positions 0 nil list STYLE-WARNING: redefining POSITIONS in DEFUN POSITIONS CL-USER> (positions 1 '(0 1 1 0 0 1 1)) (1 2 5 6) Ağız tadınıza uygun olarak KEY ve TEST seçeneklerini de -- POSITION işlevinde olduğu gibi -- POSITIONS'a da ekleyebilirsiniz. İyi çalışmalar. ___ 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
