Algoritmalar mükemmel olabilir ama uygulamaları her zaman öyle olmayabiliyor!
Google'dan Joshua Bloch, yeni günlük girdilerinden birinde Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken diye konuya girip Java standart kütüphanesinde kendi yazdığı BinarySearch fonksiyonunun nasıl bir hata barındırdığını anlatıyor.
Sun Microsystems'e 11 Mayıs 2004 yılında gönderilen hata raporunun yorum kısmı ise epey eğlenceli: "Should be fixed in the next release. Not for Tiger. xxxxx@xxxxx 2004-05-11 Finally fixing for Mustang. Can't even compute average of two ints is pretty embarrassing."
3 Haziran 2006 Cumartesi günü yollanan yorumlara göre ise, benzer problemden ötürü Solaris'teki look komutu yaklaşık 1 GB'den büyük dosyalar için düzgün çalışmıyor.
Google'dan Joshua Bloch, yeni günlük girdilerinden birinde Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken diye konuya girip Java standart kütüphanesinde kendi yazdığı BinarySearch fonksiyonunun nasıl bir hata barındırdığını anlatıyor.
Sun Microsystems'e 11 Mayıs 2004 yılında gönderilen hata raporunun yorum kısmı ise epey eğlenceli: "Should be fixed in the next release. Not for Tiger. xxxxx@xxxxx 2004-05-11 Finally fixing for Mustang. Can't even compute average of two ints is pretty embarrassing."
3 Haziran 2006 Cumartesi günü yollanan yorumlara göre ise, benzer problemden ötürü Solaris'teki look komutu yaklaşık 1 GB'den büyük dosyalar için düzgün çalışmıyor.
Görüşler
Yahut böyle bir probleme yol açmayacak programlama dillerinden birini kullanmak? Bu da bir seçenek.
Saka bir tarafa, lisp bu islere yariyor. Buyuk ve zor problemler icin var, eger hakikaten bunun bir zorlugu oldugunu dusunuyorsaniz yanlis dusunuyorsunuz.
Burada limit/problem 'fixnum' dedigimiz kucuk tamsayilarda. 32 bitlik makinelerdeki lisplerde, bunlar 27-29 bit filan olabiliyor. Suradan spece bakabilirsiniz. 64 bit makinelerdeki lisplerde bu haliyle daha buyuk. 64 bit ihtiyaci oradan geliyor. Bir de tabii elinizde 80lerin sonunda filan yapilmis bir Lisp makinesi varsa onun yeterli olmasi lazim, yanlis hatirlamiyorsam onlar tagler haric 32 bit fixnum veriyorlardi, ve word-addressable idiler -- yani temiz temiz 16gig'e ulasabiliyordunuz. Bu buyukluklere varan program var miydi bilmiyorum ama buyuk problemler icin su anda muhakkak vardir (lisp makinesiyle degil 64 bit lispler ile). Vardir diyorum cunku 64 bit lisp satan sirketler bunlari satip duruyorlar. Keyif icin alinmiyor bunlar.
Varmis:
"Arrays must be indexed by int values; short, byte, or char values may also be used as index values because they are subjected to unary numeric promotion (§) and become int values. An attempt to access an array component with a long index value results in a compile-time error."
Ben bunun Javacilar icin yanlis bir tercih oldugunu ima etmek istemiyorum. Sadece bu sekilde tanimlar yapildigi zaman baska problemlerin de cikabilecegine bir ornek bu. Buyuk array konustuk oradan bu cikti sansa.
*İmplementasyon
dilin bir parcasi olarak yavas da olsa biraz dogru calismasi garanti bir sayi unitesi olsaydi, ben buna raziydim.
Çok ama çok önemli bir konuya değinmişsiniz, matematik bölümünde okumuş biri olarak böyle güzel bir örnek sunduğunuz için kendi adıma teşekkür etmek istedim.
Bahsettiğiniz durumla ilgili olarak Java, C# gibi dillerdeki Decimal veritipi güzel bir örnektir. Çok hızlı çalışmaz ama doğru sonuç verecek şekilde çalışır.
Benzeri bir sorun Floating point islemlerde karsiniza cikiyor. Mesela java'da C kutuphanelerinden biraz farkli bir yol secilip -pi/4 +pi/4 arasi degerler haricinde daha kesin degerler hesaplanmis, ama performanstan fedakarlik edilmis. bilmiyorum diger dillerde bu yola gidilmismidir.
baglanti
sinus ve kosinus icin -pi/4 +pi/4 arasi degerler... olacakti.
"Beware of bugs in the above code; I have only proved it correct, not tried it."
CLHS: System Class INTEGER
"Description: An integer is a mathematical integer. There is no limit on the magnitude of an integer."
Muhtemelen benzer şey Python için de geçerli. Alt seviye implementasyonlarında farklar olabilir tabii ama programcıya sunulan arayüzde matematik tamsayı - bilgisayardaki tamsayı kavramları arasında bu sayede bir fark oluşmamış oluyor.
Sonuçta biz bilgisayar belleğinde sayıları 2 lik düzende tutmak veya en azından öyle işlemek zorunda olduğumuza göre lisp ve diğerleri de bir yerlerde bu veya buna benzer bir çevirim yapmak zorunda değiller mi ?
Ve eğer yanlış algılamıyorsam lispdeki " integer, rational, real, number, t " yapısı gereğide böyle bir dönüşüm var olmalı diye düşünüyorum.
Yoksa sorun dönüşüm yapılması değilde yapılan dönüşüm de ki mod un değerinin ( 2^32 sayısı ) statik olması mı ? Yani lisp ve diğerleri bu dönüşümü yapıyorlar ama alınan mod un değeri dönüştürülecek sayıya göre büyüyüp küçülüyor mu ?
Peki a = a mod birşey olmayan dillerde(Mesela Lisp'de), tamsayı sınırı aşıldığında neler oluyor? Mesela bir lisp makinasında bu sınır aşımı sorunu nasıl "çözülüyor"? Örneğin çok büyük matrisleri çarparken.
Ayrıca Bilgisayar biliminde "gerçek tamsayı" ne demektir? Tam sayıların bilgisayarda reprezentasyonu açısından böyle bir tanımlama gerçekten var mıdır?
Cozulmuyor, hafiza bitiyor sonunda. Sayiyi saklamak icin hafiza lazim. N buyuklugundeki bir sayiyi ikili sistemde saklamak icin kac bit lazim? Pekiyi, o kadar bitimiz var mi?
CPU'nun hazir komutlariyla toplayamayacagi buyuklukteki sayilar icin Newman'in tavsiyeleri iyi. Wikipedia'da yazana da ben link vereyim.
Digerlerinin de soyledigi gibi burada en az iki farkli seviyede hata var: (1) Bentley'den kopya cekip rahat etmek, (2) C/Java filan tipi dillerdeki tamsayi toplamasinin aslinda tamsayi toplamasi olmadigini dusunememek. Benzer hatalar floating point aritmetigi icin de yapiliyor.
Soylenen Lisp vs. ozelligi dogru. Dogru durust type inference yapan derleyiciler de o kodu hem dogru hem hizli yazmayi saglarlardi. (meraklisi varsa mesela sbcl ile bir denesin)
Ne oldu?
Niye oldu?
Hangi tip kac bit, nasil bakariz?
Toplamada kurallar nedir?
Haa ben de simdi bir yanlis yapmis olabilirim, onu bulmayi da Skoylu'ye birakiyorum, kitap karistirmaya spec bakmaya usendim.
Not: 32 bit x86 makinede, gcc 4.0.
Yapılması gereken iki şey var: 1) size_t isimli standart ve (standart olduğu için haliyle) portable bir tip var. Bu tipin özelliği makinenin hafızasının alabileceği (sanal hafıza dahil) en büyük uzunluğu tutabilmesi. Bu durumda merge sort (sanıyorum ki) sadece hafıza içindeki bir arrayi sıralamak için kullanılacağı için sadece bu tipin seçilmesi gerekirdi.
2) size_t tipinde iki büyük sayının toplanmasının overflow yaratacağı sıradan bir C programcısının zaten bilmesi gereken bir şey olduğundan (max + min)/2 yerine max + (max - min)/2 ifadesinin kullanılması.
Bu algoritma Lisp ile yazılsaydı bu hata olmazdı gibi bir yaklaşım size_t'den bir haber daha doğrusu C bilmeyen insanlar üzerinde belirli bir önyargı oluşturabilir ancak C'yi bilen biri elmayla armutu karşılaştırmanın manasızlığının farkındadır. C'ye middle level language ya da portable assembly yakıştırmaları yapılır bu örnekte de görüldüğü gibi doğruluk payı vardır. Bu durumda C'nin örneğin int tipini Integer sanacak kadar naif insanlar varsa bu dili öğrenmeden önce kullanmamalıdır bu doğrudur. Ayrıca Lisp'in programcıyı bu tip ayrıntılardan kurtararak (yani daha fazla soyutlayarak) işini kolaylaştırdığı da doğrudur ancak C'nin bu yolla çalışmasının bir nedeni vardır. C işletim sistemlerinin yazıldığı bir dildir. Şimdi bir C programcısı çıkıp bana hayır katılmıyorum C ile her şey yazılır derse o da haklıdır. Çünkü GMP isimli bir kütüphane vardır ve bunu kullanarak Lisp'in sağladığını sandığım türden bir soyutlama (bu integer mevzusunda) C ile de sağlanabilir. Hatta ben daha da ileri giderek C++ bana daha güzel soyutlama fırsatları yaratırken gerekli gördüğümde C ile kod yazmama engel olmaz diyerek bir başka karşılaştırma daha yapabilirim ve ben de haklı olurum. Görüldüğü gibi dilleri her fırsatta karşılaştırmaya çalışmak pek anlamlı değildir.
Sonuç olarak: a) elma ile armutu karşılaştırmayalım b) Bu algoritma implementasyonu yanlış yazılmıştır. Kitaptan aynen kopyalayan olmuşsa onlar da yanlış yapmıştır.
"yazdığınız kod/tasarladığınız algoritmayı uç değerler için test edin."