Liste icindeki belli bir elemanin hangi pozisyonlarda oldugunun listesi..?

[Aykut Caglayan]

Selamlar,

Ornegin soyle bir listem var:>'(0 1 1 0 0 1 1)
ve ben su cevabi ariyorum:> '(1 2 5 6)

Ivedilikle cevabinizi bekliyorum

Tesekkurler


____________________________________________________________________________________
Be a better friend, newshound, and
know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ

[Can Burak Cilingir]

Post by Aykut Caglayan
Selamlar,
Ornegin soyle bir listem var:>'(0 1 1 0 0 1 1)
ve ben su cevabi ariyorum:> '(1 2 5 6)

Problemi daha iyi anlamak icin soruyorum,

Soyle bir listeniz var ise: (2 4 5 7 3)
hangi cevabi ariyorsunuz?

Problemi eger dogru tahmin ediyorsam, bahsettiginiz isi list veritipi
kullanarak yapmak yerine girdilerini nept veritipine cevirerek daha
performansli calisabileceginizi tahmin ediyorum.

list -> nept cevrimini yanlis animsamiyorsam SBCL O(1) de yapabiliyor.
CLISP te listenin boyutuna bagli olarak en kotu durumda O(n^n)
calisiyor ama farkedeceginiz uzere O(1) kadar kotu degil. bu yuzden
CLISP tavsiye edebilirim.

Post by Aykut Caglayan
Ivedilikle cevabinizi bekliyorum
Tesekkurler
____________________________________________________________________________________
Be a better friend, newshound, and
know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ
_______________________________________________
cs-lisp mailing list
http://church.cs.bilgi.edu.tr/lcg
http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp

[Volkan YAZICI]

Merhaba,

Post by Can Burak Cilingir
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.

Post by Can Burak Cilingir
list -> nept cevrimini ...

Cahilliğimi mazur görün, "nept" nedir?


İyi çalışmalar.

[Can Burak Cilingir]

Post by Volkan YAZICI
Merhaba,

Post by Can Burak Cilingir
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.

Post by Can Burak Cilingir
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.

Post by Volkan YAZICI
İyi çalışmalar.

[Volkan YAZICI]

Post by Can Burak Cilingir
(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.

[Can Burak Cilingir]

Post by Can Burak Cilingir
(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.

[Aykut Caglayan]

Ornegin soyle bir listem var '(a b c) >

bu listeyi cagirdigimda ongoremedigim (randomized) bir siralamayla gelmesini istiyorum;
Ornegin '(b a c) olarak__

Eminim bunun da cok basit bir yolu vardir benim bulamadigim_

Tesekkurler



____________________________________________________________________________________
Be a better friend, newshound, and
know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ

[Chris Stephenson]

Post by Aykut Caglayan
Ornegin soyle bir listem var '(a b c) >
bu listeyi cagirdigimda ongoremedigim (randomized) bir siralamayla gelmesini istiyorum;
Ornegin '(b a c) olarak__
Eminim bunun da cok basit bir yolu vardir benim bulamadigim_

Benim basit kafa için hep bunu yaptım (spreadsheetlerde de)

Listenin her elemanını "random" fonksiyondan gelen bir rakamla
çiftleşmek. (burada random seed in rastlantasal olması çok önemli tabii,
ytoksa hep aynıo sıralama çıkabilir).

Scheme'de iki satır:

(random-seed (current-seconds))
(define (randomize l) (map cdr (quicksort (map (lambda (x) (cons
(random) x)) l) (lambda (x y) (< (car x) (car y))))))

CS

[Volkan YAZICI]

Selam Aykut,

Post by Aykut Caglayan
Ornegin soyle bir listem var '(a b c) >
bu listeyi cagirdigimda ongoremedigim (randomized) bir siralamayla
gelmesini istiyorum; Ornegin '(b a c) olarak__
Eminim bunun da cok basit bir yolu vardir benim bulamadigim_

Muhtemelen bu da başka bir ödev sorusu. Umarım sorduğun bu sorular
listedekilerin insiyatiflerini suistimal etmenin dışında gerçekten senin
Lisp'e olan ilgini de kamçılıyordur.

CL-USER> (sort '(a b c)
#'>
:key (lambda (item)
(declare (ignore item))
(random 1.0)))
(C A B)


İyi dersler.

[Volkan YAZICI]

Post by Aykut Caglayan
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.

[Ruhan Alpaydin]

;; binary position
(defun pos (item list pos-list)
(if (not (null list))
(if (= item (car list))
(pos item (cdr list) (cons 1 pos-list))
(pos item (cdr list) (cons 0 pos-list)))
(reverse pos-list)))

;; cumulative position
(defun bin2cum (pos cum-pos cum)
(if (not (null pos))
(if (= 0 (car pos))
(bin2cum (cdr pos) cum-pos (+ cum 1))
(bin2cum (cdr pos) (cons cum cum-pos) (+ cum 1)))
(reverse cum-pos)))

[112]> (pos 4 '(3 4 1 0 1 7 8 9 11 4 12 1 6) NIL)
(0 1 0 0 0 0 0 0 0 1 0 0 0)
[113]> (bin2cum (pos 4 '(3 4 1 0 1 7 8 9 11 4 12 1 6) NIL) NIL 0)
(1 9)

Post by Volkan YAZICI

Post by Aykut Caglayan
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
http://church.cs.bilgi.edu.tr/lcg
http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp

[Volkan YAZICI]

Post by Volkan YAZICI
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.

[Volkan YAZICI]

[Aykut Bey, mesaj doğrudan bana gelmiş olmasına rağmen, bu konuyu liste
ile paylaşmak istedim. Umarım sizin için sorun olmamıştır.]

Ogrenci degilim, esasen muzikle ugrasmaktayim _ Algoritmik kompozisyon
uygulamalarinda Common Music'i kullanmaktayim.

Çok iyi! Projenin gelişimi hakkında bizleri de haberdar etmeniz
gerçekten çok güzel olur.

Post by Volkan YAZICI
Muhtemelen bu da başka bir ödev sorusu. Umarım sorduğun bu sorular
listedekilerin insiyatiflerini suistimal etmenin dışında gerçekten
senin Lisp'e olan ilgini de kamçılıyordur.

Suistimal ile tam olarak neyi kast ettiginizi anlayamadim. Cevap verip
vermemek size kalmis; ayrica bu cevaplarla sirket kurulmaz.
Sorularima aldigim cevaplar Lisp'e olan ilgimi kamcilamiyor, hali
hazirda uzerinde calistigim uygulamamin ilerlemesini sagliyor.

Buna gerçekten çok sevindim. Bu tür sorular listeye hep ödev sorularını
soran öğrenciler tarafından taşındığından, sizi de aynı kefeye koyma
eğilimi gösterdim. Ne güzel bir gaf ki, böyle ilginç bir projeden
haberdar oluyorum!

Takıldığınız her konuda lütfen soru sormaktan çekinmeyin. Listenin en
cahili olarak, sizi cevapsız bırakmayacağımızı temin edebilirim.


İyi çalışmalar.