[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
[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, 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
