From: Bora Güngören (bora@boragungoren.com)
Date: Mon 29 Aug 2005 - 17:55:35 EEST
Merhaba,
Bu tartışmada anlaşılamayan nokta, uygulama alanı ile ilgili. DNA yada
benzeri kodlanmış bilgilerde "birebir eşleme tabanlı arama" yapılması
sadece çok asgari bir uygulama. Düz metin işlemiyoruz. Bunu asla göz
ardı etmemek gerekli.
Esas yapılan şey "bilginin keşfedilmesi" (knowledge discovery). Yani
aradığınız belli bir biçim yok. Veri içerisinde sık karşımıza çıkan
biçimleri "keşfetmeniz" bazen de eksik gelen verileri "tamamlamanız"
gerekiyor. Bunların yoğun istatistiksel algoritmaları var. Bu tür
işlemler için C standart kitaplığındaki str... işlevlerini temel alan
düz mantık çözümler ne yazık ki kodlanamıyor.
Bu nedenle baytlar üzerinde, bol bit kaydırmalı, bol mantıksal işlemli
deyim yerindeyse "abuk subuk" operatörler tanımlamanız bile gerekebilir.
Elbette C için bunlar birer işlev olacaktır. Ancak yine de iki bitlik
yada başka biçimde kullanılan bir alanın, daha önce dediğim gibi
kodlamaya dikkat edilen bir duruma göre bellek tasarrufu sağlaması
mümkün olmayacaktır.
Kodlama işlerinin hızlı yapılması da mümkün.
Bu şekilde bir baytda 4 adet "baz"ın olduğu bir yapıyı (yada bir int
içinde 16 "baz" olan bir yapıyı) işlemek yerine her bir baytın sadece
tek bir "baz" içermesi (1 baz = 1 char değişkeni) daha hızlı olabilir
olmayabilir. 1 baytın yada daha yaygını, bir int'in içerdiği "baz"
kombinasyonlarını, (int için 4 x 4 x 4 x 4 =256 tane) bir tabloda
tutarsanız bu tabloda arama / karşılaştırma çok hızlı yapılabilir. ASCII
tablosundan hareketle C standart kitaplığı ile çok dil desteği vermek de
böyle oluyor zaten. Yani dikkatli kodlanan bir tablo ile çok hızlı
erişimler olabilir.
Veri tabanında da her bir DNA örneğinin bütün yapısını yani çok uzun
bayt dizilerini tek bir kayıt olarak saklayacağımız ve bu kayıtların
azami uzunluğu da en sık rastlanan uzunluğa eşit olduğu için sabit
boyutlu bir tamsayı alanı da mantıklı olur herhalde. Dolayısı ile VT
olarak ne kullandığımızdan bağımsız bir noktaya geliyoruz.
Ticari uygulamalarda veri madenciliği iş nesnelerinin olduğu veri tabanı
tablolarından beslenmek zorunda olduğundan iş daha karışık ama bu tür
amaçlarla kurulan veri tabanları ve onların işlenmesinde veri tabanı
tasarımı kesinlikle ikincil noktada.
Sevgiler.
Bora.
Ergin ALTINTAS wrote:
>Bence hem hız hem de yer kazancı sağlanabilir. Fakat kullanım
>kolaylığı azalacaktır. Elinizdeki 1000 adet 2 şer bitlik DNA kodunu
>bir bayt içerisine 4 tane DNA kodu girecek şekilde düzenleyin.
>Üzerinde tarama yapılacak olan kodu da aynı şekilde düzenleyin. En
>büyük sorun elinizdeki kodları 4 ün katları olarak düzenlemeniz
>gekemesi. 1000 DNA için 250 byte yeterli oluyor. Fakat eğer 1001 adet
>DNA nız var ise sondaki DNA yı ayrı bir byte içinde tutmalısınız. Daha
>sonra standart srtcmp() fonksiyonu veya benzeri bir fonks. ile
>karşılaştırmanızı yapabilirsiniz. Bu adım toplam karşılaştırma işinin
>4 te birine denk gelecektir. Bir sonraki karşılaştırma adımında,
>elinizdeki anahtar (ARANAN) DNA kodlarını temsil eden tüm baytları 2
>bit sağa kaydırmanız gerekecek. Sonra tekrar strcmp() yapacaksınız.
>Sonra tekrar 2 bit kayıdıracak ve vb.. toplam 3 kaydırma yaptığınızda.
>Tüm karşılaştırmalarınız tamamlanmış olur. Karşılaştırmlarınızı bit
>bazında değil de bayt bazında yaptığınız için hem hızdan hem de yerden
>kazanırsınız. Ancak strcmp() komutu tek bit (veya iki bit) farklı
>olduğunda tüm byte ın farklı olduğunu varsayar. Dolayısıyla
>hassasiyetinizden kaybedersiniz. Yani bir DNA kodunun farklı olması
>aynı bayt içindeki diğer 3 DNA kodunun da farklı olması şeklinde
>yorumlanacaktır. Eğer bu hassasiyet sizin için yeterli ise DNA
>kodlarınızı bir bayta 4 tane sığacak şekilde düzenleyebilirsiniz. Eğer
>bu hassasiyet sizin için yeterli değilse. DNA kodularınızı bir bayta 4
>tane girecek şekilde düzenlemek size zaman kazandırmaz, tersine
>işlemler umutun da dediği gibi çevirmelerden dolayı daha yavaş
>olacaktır, fakat sadece yerden %75 kazanabilirsiniz.
>
>On 8/29/05, Bora Güngören <bora@boragungoren.com> wrote:
>
>>Merhaba,
>>
>>Elimizde 8 milyar bit lik alan olsun. Ben bunu 1 milyar char yada 4 milyar
>>adet 2 bitlik bit alanı ile saklayabilirim. Ve "bellekte" tamamen aynı
>>şekilde organize olurlar. Yani aynı alanı kaplarlar :-)
>>
>>Belleğe yüklenmesi, işlenmesi, bit karşılaştırma için yazılmış API'lerin
>>(char*) yani char dizisi işleyeceğini düşünürsek, "işlem hızı" tarafında
>>char kullanımı daha hızlı bile olabilir. Bunu daha detaylı açıklayan
>>mesajlar yazılmıştı.
>>
>>"Veri madenciliği" amacı ile kurulacak olan algoritmalar (vaktiyle
>>yazmışlığım var) ağırlıklı olarak bellekte çalışacaktır ve sistemin
>>darboğazını oluşturacaktır. Bu nedenle veri tabanı yönetim sistemi seçimi
>>bile (duruma göre) önemsiz olabilir.
>>
>>Bora Güngören.
>>
>>
>>------------------------------------------------------------------------
>>
>>_______________________________________________
>>Linux-programlama mailing list
>>Linux-programlama@liste.linux.org.tr
>>http://liste.linux.org.tr/mailman/listinfo/linux-programlama
>>
_______________________________________________
Linux-programlama mailing list
Linux-programlama@liste.linux.org.tr
http://liste.linux.org.tr/mailman/listinfo/linux-programlama