BinarySearch ve MergeSort kullandıysanız kodunuzu kontrol edin!

0
FZ
FZ
5 Haziran 2006 , 1 dakika okuma süresi
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.
yazilim
50
Linkedin Facebook Twitter Google plus

Görüşler

ahmetaa
0
ahmetaa
Evet gercekten tatsiz gorunen bir hata. bu hatanin sadece 1 milyar ve uzeri boyutlu dizilerde gerceklesmesi bu ana kadar gozden kacmasina neden olmus gorunuyor. Bu boyutlu diziler uzerinde binary search islemine pratik olarak rastlamak pek mumkun olmasa gerek. Burada eger bu sekil bir islem ihtiyaci olan varsa sanirim uc cozum onerilebilir, 1- binary-search islemini elle yazin 2- O projeniz icin IBM ya da BEA ya da baska bir Java kullanin.. 3- Eger cok kritik degilse Mustang'in cikmasini ya da bu hatanin geri 5 surumune atilmasini bekleyin..
newman
0
newman
>>>2- O projeniz icin IBM ya da BEA ya da baska bir Java kullanin.. Ya da Java kullanmayin! Tamamen sakdir, lutfen kirilmayin :). Yoksa Java guzel bir arac.
ahmetaa
0
ahmetaa
Eger yeni bir projede bir milyarlik bir dizide binary search ihtiyaciniz olacaksa dediginiz mantikli, ama var olan bir projede bu hata ortaya cikmis ise (neyseki array index out of bound exception firlatiyor..) sanirim bu uc yoldan birini secmeniz gerekir.. ;) bir de saniyorum bu konudan cikarilmasi gereken ders algoritmalarin ne kadar basit olursa olsun cok detayli sekilde test edilmeleri gerektigi.
FZ
0
FZ

Yahut böyle bir probleme yol açmayacak programlama dillerinden birini kullanmak? Bu da bir seçenek.
newman
0
newman
Lisp demek istiyorsun :). Yani kasiniyorsunuz kardes ;)
ahmetaa
0
ahmetaa
aslinda bir bos vaktinizde lisp icinde bir milyarlik bir dizide binary search yapabilirseniz sevinirim..
bm
0
bm
Simit paraniz artinca 64 bitlik ve 16-32 gig hafizasi olan bir makine aliverirseniz bana, memnuniyetle yaparim.

Saka bir tarafa, lisp bu islere yariyor. Buyuk ve zor problemler icin var, eger hakikaten bunun bir zorlugu oldugunu dusunuyorsaniz yanlis dusunuyorsunuz.

ahmetaa
0
ahmetaa
valla 1Gig bellek byte dizisi icin yeter saniyorum bu operasyon icin. Lisp'i kucumsemek icin soylememistim, sadece merak ettim acaba benzeri bir problem olur mu diye. Java'da da Collections siniflari integer ile sinirli degildir (List icin long index, 64 bit), ama bu miktarda bir List olusturmak icin 1GB bellekyetmez saniyorum.
bm
0
bm
Yok, dogru lisple problem olmaz. Lispte integer overflow olmasi icin zaten 'safety' denen compiler ozelligini azaltmaniz lazim cunku dil taniminda aritmetik islemler mod --birsey-- degil. (Hafiza bitmedigi surece.)

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.

ahmetaa
0
ahmetaa
Selamlar. acikcasi bir platformun cekirdek yeteneklerinin donanima ya da isletim sistmeine desgimesi cok istenen bir sey degildir. Bu nedenle Java'nin yaklasimini daha tuttugumu ifade etmeliyim. yani int her zaman 32bit, long64 bittir hesabi. en azindan tasinabilirligi garantilemis oluyor. Bu arada JAva'nin buyuk sistemlerle ilgili bir sorunu oldugu konusunda kafanizda bir soru olusmasin..
bm
0
bm
Buyuk bir zarari yok belki ama bit seviyesinde sabit bir spec olunca buna da mahkum olunuyor. Javayi yazanlarin gayeleri Lispcilerin gayelerinden farkli elbette, o zaman bu 32bit int iyi fikirdi belki onlarin gayeleri icin. (Bunu bilmiyorum ->) Eger int'i 32bit, array indexlerini de ille de int diye tanimladilarsa, dev arrayleri baska sekilde indexliyorlar herhalde. Farzedelim oyle, yani array int ile indexlenir diye yayinlanmis bir kural var, int the sabit 32 bit. O zaman dev arraylarde problem 'benim platformum/implementasyonum bunu yapabilir mi?' yerine, 'Java bunu yapabilir mi?' oluyor, yapabilen de Java olmuyor. Yaklasimlar arasindaki fark burada herhalde. Herneyse, var mi boyle bir 'array indexi kesin int ola' speci?
bm
0
bm
Herneyse, var mi boyle bir 'array indexi kesin int ola' speci?

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.

281817 181476855250691 6784756 n
0
tongucyumruk
Öhüm, Chris Stephenson'ın bir e-postasında konu hakkında yaptığı yorumu izninizle buraya taşıyorum...
You will note that you need NOT look at your binary search, quicksort etc if you wrote in a programming language where "integers" are actually integers, not integers modulo 2^32 The bug is an integer overflow bug.... So users of Scheme, Common LISP, Python can, at least for this bug, breathe easily! cs
Kısa bir Türkçe özet geçmek gerekirse: Sorunun kaynağı tamsayıların gerçek tamsayılar yerine "sayı mod 2^32" şeklinde tanımlanmasından kaynaklanan bir tamsayı taşması durumu. Eğer "gerçek" tamsayılara sahip Scheme, Common Lisp veya Python gibi bir dil kullanıyorsanız bu hata için endişe etmenize gerek yok.
newman
0
newman
Belki bu yuzden "integer" yerine int deyip kesip atmislardir C/C++' da :). Saka bir yana, yuksek-seviyeli dillerin performans yerine dogrulugu vurgulamasi gerekir diye dusunuyorum. Dile rahatlikla optimizasyon icin ozel ama acikca belirtilmesi gereken komutlar konulabilir. Riski goze alan onlari kullanir. Boylece, bu tip sorunlar ciktiginda dil/derleyici, vs. yerine programciya "kendin ettin, kendin buldun!" denilebilir.
ahmetaa
0
ahmetaa
tabi sunu da not ediniz, butun bu diller C-C++ kokenli oldugundan bu tur hatalari. hatta daha kotulerini icerisinde her an barindirabilirler ;). Isin sakasi bir yana, acikcasi bu hatadan alinmasi gereken ders hatanin kendisi degil, ki pratikte ortaya cikabilecek bir sey de degil zaten, sadece platform gelistirme ve algortima yazmanin ne kadar dikkat istedigi ve test kriterlerinin gunun kosullarina gore tekrar elden gecirilmesi gerektigi.
281817 181476855250691 6784756 n
0
tongucyumruk
Dilden bağımsız olarak aklıma takılan bir nokta var yalnız. Bir algoritma temelde soyut, matematiksel bir ifadedir. Algoritmalar tasarlanırken belli bir dilin veya donanım platformunun sınırları gözönüne alınarak tasarlanmaz. Belki algoritmanın gerçeklemesini* yaparken buna dikkat etmek gerekir fakat zaten gerçeklemelerde her zaman başka hatalar da çıkabilir. Yanılıyor muyum?

*İmplementasyon
newman
0
newman
Ama hata gercekten integer overflow ise, zaten soyut algoritmada hata oldugunu sanmam. Ama iste kodlama yaparken dillerdeki kisitlamalardan dolayi her andim basina bir hata kontrolu yerlestirmek zorunda kaliyorsunuz. Boyle bir adimi kacirmak demek ki daha kolay. Bu anlasilabilir bir durum. Ben gecen yaz bir Taylor serisinin katsayilarini hesaplayan kucuk bir kod yaziyordum: Ama istemin ozellilerinden dolayi katsayilar cok hizli buyuyor ve sonucta double precision yetersiz kaliyordu. Ilk yaptigim is hatalari kontrol edip ona gore ozel durum kodu yazmak yerine "itle dalasmaktansa caliyi dolasmak" kabilinden birsey yapmak oldu :). Hata kontrolu zorunlu birsey, ama programlamanin en zevkli yonu degil. Mesela C++'da dilin bir parcasi olarak yavas da olsa biraz dogru calismasi garanti bir sayi unitesi olsaydi, ben buna raziydim. Ama maalesef yok :/. Tabii istersen cozum var bu tip seylere ama, insan kolayda birsey arzuluyor bazen: Ben bekleyebilirdim kodun yavas calismasini, vaktim vardi :). Fakat Ahmetaa hakli tabii ki, asil cikarilmasi gereken ders dikkat edilmesi (JAVA'yi veya baska bir dili duzeltmek elimizde olmadigina gore :/).
FZ
0
FZ

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.
newman
0
newman
Ama iste temel sayi tipleri bu sekilde calismadigi icin, bunu ogrendiginizde zaten dile de dizayn edene de bir guzel rahmet okumus oluyorsunuz zaten :). Ben sahsen tum bu yuksek seviyeli diye gecinen dileri dizayn eden kisilerin bir durup dusunmesini ve dizaynlarini gozden gecirmelerini dilerdim. Tabii ki problemlerin hepsinin cozumu var, ama iyi bir dizayn isleri cok cok kolaylastiran bir etken. Adam zaten performansin her damlasina ihtiyac duydugu bir problem ile karsi karsiya ise gerekli arastirmayi yapar ve tedbirini alir (ne bileyim iste, Fortran veya C kodu yazar kritik noktalar icin; veya eger kullandigi dil gerekli olanaklari sagliyorsa onlari kullanir. Sizde diger durumlarda aman ayagim kaymasin diye kodu yerli yersiz hata kontrolleri yerlestirerek bogmak zorunda kalmazsiniz). Bunun disindaki durumlarda performansa dogrulugu kurban etmek ve yarsayilan davranisin hayali bir performansi dogrulugun onune koymasi benim pek anlayabildigim bir dizayn karari degil. Ama iste dunya, hersey insanin istedigi gibi olmuyor :). Yanlis anlamalar da olmasin, Java'nin mesela cok guzel ve sIk yanlari var: sanirim hatasiz kul olmaz deyip gececegiz :). Ee, siz de matematik okudugunuza gore hislerimi daha iyi anlamissinizdir: dert dokecek birini bulabilmek guzel birsey :)
FZ
0
FZ
Tam bu bahsettiğiniz türden durumları filan bildiğim için hiç değilse matematik bölümlerinde öncelikle Common Lisp veya Scheme, sonra Macsyma / Mathemetica tarzı şeyler (paralelinde Octave / Matlab) ve sonra da C ve assembly gösterilmesi gerektiğini düşünüyorum.
newman
0
newman
Kulaga siir gibi geliyor, ama olacagini sanmiyorum :). Ben o konuda cok beklenti icerisinde degilim. Guzel olurdu vallahi!
FZ
0
FZ
Sizin durumunuzun kötü olduğunu sanmıyorum, bu tür tartışmaları takip ettiğinize göre birtakım şeylerden haberdarsınız ve eldeki olanakları kullanarak çok daha fazlasını öğrenebilecek durumdasınız. Yani bireysel olarak bir problem yok. Tabii benim kafam biraz daha kurumsal tarafa, müfredat hazırlamaya filan gidiyor, yoksa yani Internet'i kullanıp soru sormasını bilen, önyargısız ve farklı ortamları kurcalamayı seven gençler için ister matematik bölümünde olsunlar isterlerse başka bölümde, pek bir engel yok.
newman
0
newman
Ben de mufredat olayini kasdetmistim. Bogazicindeki tecrubelerimden dolayi cok sanmiyorum. Baska yerlerde durum daha farkli olabilir. Ama cok isterim ki yaniliyor olayim: 3 yil gecti, kimbilir belki de su anda imkanlar daha uygundur. Ama olsaydi bu tip imkanlar, insanlardaha dogru ve etkin olarak egitilmis ve daha verimli olurlardi: ister kariyerlerini matematikci olarak devam ettirsinler, ister baska bir yol secsinler. Gercekten onemli bir konu bu. Ama siz haklisiniz, asla umitsiz olmamak lazim. Ben umitsiz oldugumdan degil, sadece her guzel gelisme gibi, bunun da onunde asilmasi gereken gucluklerin oldugunu gorup bildigimden sanmiyorum dedim.
ahmetaa
0
ahmetaa
Gercekten algoritmalar soyut ve matematiksel ifadeler ancak bilgisayar dillerindeki gerceklemeleri haliyle donanim kisitlamalari nedeniyle soyut olamiyor. Bunun bir nedeni de kaynak ve performans kaygilari nedeniyle cogu noktada "pratik" kullanilabilirlik teorik "dogruluk"'un yerini aliyor. Bu problemde oldugu gibi. Diger dilleri bilemiyorum ama zaten Java'da bir diziye atanabilecek eleman sayisi pozitif integer siniri kadar. yani index degeri yanilmiyorsam maximum 2^31-1 kadar olabiliyor eger bu boyle olmasaydi, kanaatimce performastan fedakarlik edilecekti. Zaten range-check ile yeterince dizi performansindan fedakarlik edildiginden ve pratik limitler dusunuldugunde bu tur dizilerin bellekte bulunmasinin soz konusu olmayacagi kestirilerek bu yola gidilmis. Elbette bu tur devasa nesne kumelerini tasimak icin Collections nesneleri (Map, List) zaten kullanilabiliyor .
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
ahmetaa
0
ahmetaa
"... -pi/4 +pi/4 arasi degerler..."
sinus ve kosinus icin -pi/4 +pi/4 arasi degerler... olacakti.
FZ
0
FZ
Bir kez daha Knuth'un karşısında ceketimizi ilikleyip saygı duruşunda bulunalım:

"Beware of bugs in the above code; I have only proved it correct, not tried it."
Tarık
0
Tarık
Aslında algoritmaların tamamen dilden/platformdan bağımsız geliştirilebilir olduklarını söylemek imkansız. Algoritma ne kadar ayrıntılı hazırlarnırsa dil/paltform ayrımına o kadar yaklaşıyor demektir. Neticede bunlar gözönünde tutulursa hataların ortaya çıkabilme olasılıklarıda da o kadar ortada olur. Böylece dilin esnekliği kullanılarak kurtarmak üzere birşeyler yapılabilir.
anonim
0
anonim
şu "sayı mod 2^32" kısmını tam anlayamadım buradaki sayı 2'lik düzendeki bir sayı mı oluyor ?
newman
0
newman
Bilgisayarin kutusu icindeki hersey gibi :), evet... Aslinda tam moduler aritmetik degil, cunku bu siniri astiginizda overflow hatasi almaniz lazim. Ama tabii ki hatayi gormek icin kontrol etmek gerek :)
anonim
0
anonim
Ben de öyle tahmin etmiştim. Bu durumda lisp, python gibi dillerin nasıl kendilerini 2 lik sayı sisteminin kıskacından kurtarıp, nirvanaya erdiklerini şöyle basitçe anlatabilir mi birisi, bu tamsayı mevzusu için...
newman
0
newman
Teknik olarak da gerektiginde sayilari gostermek icin 4 bytedan fazla hafiza kullanarak. Mesela Guile scheme yorumlayicisi vs. isin teknik tarafini GMP kutuphanesi kullanarak hallediyorlardi. Isin teknik/matematiksel boyutlari icin GMP kilavuzuna bakabilirsiniz. Bu kutuphane C ile yazilmis izlenimi veriyor, ama bu biraz yaniltici: asil is assembly duzeyinde yapiliyor. Bunun performansa olumsuz etkisi olabilir, ama bu etki hissedilir duzeye ulastiginda gerekli onleyici optimizasyon komutlari programciya saglanabilir. Fakat nedense bu ihmal edilegelmis hep.
newman
0
newman
Yanlis anlama olmasin "Bunun performansa olumsuz etkisi olabilir..." derken assembly kullanilmasini kasdetmedim :), problemi cozmek icin kullanilan extra isi kasdettim.
FZ
0
FZ
Performans konusu ile ilgili Gabriel'in güzel bir yazısı vardı (tabii bir sürü şeyden bahsediyor ama bakış açısını yansıtmak bakımından güzel): The Art of Lisp & Writing
FZ
0
FZ
Çok gizemli görünmüyor:

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.
anonim
0
anonim
Açıkcası bu bana çok fazla birşey ifade etmedi şöyle ki; Eğer ben Chris hocanın mesajını doğru anladıysam hoca hatanın integer için 2 lik düzende tutulan sayı değişkeninin mod 2^32 ile çevrilmesinden kaynaklandığını söylüyor.

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 ?

newman
0
newman
Sorun sayilarin hangi tabanda saklandigi degil (tamsayilar icin). Sorun bellegin sinirlandirilmasi. Her sayi icin 4 byte kullandiginizda, bu iki sayisi birtek islemci komutu ile carpabiliyorsunuz. Ama eger sonuc 4 byte'a sigmayan bir sayiysa, "elde var ..." kismi yerine bir tasma biti isaretleniyor islemci tarafindan, sayinin geri kalan 4 byte'a sigan kismi sonuca yaziliyor. Mesela varsayalim siz bu sayilari bir tek komut ile carpmak yerine, 16 bitlik 4 parcayi alip bunlari elle carpma yapar gibi carptiniz: burada bir tasma mumkun degil, ondalik carma yapmaktan da daha efektif: cunku sayi tabani 2^16 imis de elle ilkokul cocugu gibi carpma yapmissiniz sanki... Sonuc icin 8 byte alan ayirip 4 carpma ve birkac toplama ile sonucu buraya bir tasma olmadan yaziyorsunuz diyelim. Tabii sayilarin buyuklukleri icin baslangicta iki tane test yapmaniz lazim. Bu, yapilabilecek gercekten en toyca bir implementasyon. Ama sanirim fikir vermistir. Daha akillica teknikler ile sorun oldukca kabul edilebilir duzeyde cozulebilir. Eger dil gerekli optimizasyon komutlarini iceriyorsa, ve siz de mesela sayilarinizin sinirli ve kucuk olacagini kesinlikle biliyorsaniz, daha hizli ama guvensiz makine kodu urettirebilirsiniz derleyicinize. Fikir, hata kontrolu yerine buyukluk kontrolu yapmak, ve sayilar buyukse matematiksel teknikler kullanilarak tasmanin konsept olarak mumkun olamayacagi sekilde islemi mumkun olan en hizli sekilde yapmak.
ahmetaa
0
ahmetaa
acikcasi konunun nirvanadan cok performans-kaynak kullanimi ile iliskisi var. yani ne kadar cok esneklik-guvenlik-soyutlama o kadar performans-kaynak kullanimina negatif etki olarak Python icin de benzeri problemlerin oldugunu saniyorum. daha dogrusu calistiginiz platforma gore farkli sonuclar alabilirsiniz gibi gorunuyor. Python arrays kodunu inceleyin isterseniz, dizi indexleri C int'i.. Python arraymodule.c
Chaosopher
0
Chaosopher
Öncelikle Bu güzel tartışma ve yorumlar için herkese teşekkürler. Ben kafama takılan birkaç şeyi google'lamak yerine buradan sormak istiyorum:
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?
newman
0
newman
Is assembly duzeyinde programlama gerektiriyor. Zaten diller ve derleyiciler de bu isi bizim icin yapiyorlar degil mi? Giris seviyesinde isi akla yaklastirma kabilinden bir yaziyi su linkte bulabilirsiniz: http://webster.cs.ucr.edu/AoA/Windows/HTML/AdvancedArithmetic.html#998258 Daha ileri duzeyde nasil yapilabilir, isin arkasindaki matematik teknikler nelerdir diye merak ediyorsaniz, Gnu MP kutuphanesinin kilavuz ve kaynak kodlari yardimci olacaktir. Ama isin esasi yukaridaki linkte anlatiliyor. Umarim yardimci olur.
bm
0
bm
Mesela bir lisp makinasında bu sınır aşımı sorunu nasıl "çözülüyor"?

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.

bm
0
bm
Hmm, Bentley bunu atlayacak bir adam degil. O kitap var bende, baktim, bunlari anlattigi bolumun sonundaki egzersizlerde "bazi standartlara gore bu ispat tamamlanmis degil" deyip arasinda 'word overflow' da olan bir suru fikri listelemis.

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)

skoylu
0
skoylu
BU aslında temel programlama eğitiminden kaynaklanan bir sorun. Bir şeyin sayısı, hiç bir zaman negatif olmaz. Yani -2 elma olmaz. O halde -2 değeri alabilen bir sayı burada kullanılmaz. Bu yüzden size_t, off_t gibi değerler tarif edilmiştir. ELbette, hep söyleriz, C öğrenin diye.. Programlama pratiğini böyle üst seviye dillerle yapanlar için bu hususlar hep mayın tarlası olarak kalmaya devam edecektir. Baktım, 1980'lerde BASIC ile benzer bir binary search algoritması yazmışım. En büyük sayı 32767. VE kullanılan formül şu: ORT = MIN + (MAX - MIN) / 2 Bilmiyorum, belki sadeleştimeyi düşünmediğimden belki bilmediğimden böyle yaptım. Ama ilginç olan, demekki atraksiyon yapmaya çıkmak, macera aramak her zaman baş ağrıtabiliyormuş. Bu yüzden sade ve ne söylediği anlaşılan kod yazmak her daim faydalıdır derim..
bm
0
bm
O 16 bit sayilari tuketmeye alisik oldugumuz icin oyle yapmis olabilirsiniz belki. Herneyse, 'unsigned' veya C cozum degil aslinda. Dediginiz gibi bilmek cozum. Unsigned o kodda isi bitirecekti belki ama overflow problemi isaret bitinden farkli bir problem. Siz bunu biliyorsunuzdur gayet tabii, ama ogrenen arkadaslarla asagidaki koda bakalim:
#include int main () { unsigned int max = 0xffffffff, min = 0x00000002, mid; unsigned long long maxl = 0xffffffff, minl = 0x00000002, midl; mid = (max+min)/2; midl = (maxl+minl)/2; printf("Birinci sayi=%u, Ikinci sayi=%u, ortalamalar: %u %llu \ ", max, min, mid, midl); return 0; //muffle -Wall }
Derleyip calistiralim:
p4:~/lisp-tr> gcc -Wall unsignedof.c p4:~/lisp-tr> ./a.out Birinci sayi=4294967295, Ikinci sayi=2, ortalamalar: 0 2147483648 p4:~/lisp-tr>
Sorular:

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.

rickdangerous
0
rickdangerous
Hayır çözüm tipi unsigned yapmak değil fakat skoylu doğru tipi söylemiş zaten: size_t

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.
bm
0
bm
Dediginizin teknik acidan hepsi dogru (size_t dahil). Ses cikartacagim sey su: burada word overflow, mod n aritmetik filan duyup merak edip ilgilenen insanlar varken bu firsati kullanip kolayca bir iki kavrami ogrenmelerine yardimci olacak baska bir ornek vermek istedim ben. Isi C/Lisp'e dokmek degildi maksat yani.
rickdangerous
0
rickdangerous
İster istemez (C ile nasıl doğru yazılacağı söylenmediği için sanırım) buraya (C/Lisp karşılaştırması) gelmiş gibi görünüyor konu ancak herkes için faydalı olduğuna katılıyorum. Bu arada, haberde linki verilen blogdaki unsigned'a cast doğru çözüm olmadığı gibi sanıyorum ki portable da değildir.
rickdangerous
0
rickdangerous
Pardon min + (max - min)/2 olacaktı; bir roket de biz düşürmeyelim ;)
myavuzselim
0
myavuzselim
Kalkamazdi ki bile :)
bm
0
bm
Bu arada bu overflow islerini populer dergilere kadar indiren Ariane roketi bugini bilmeyenler vardir belki diye size ongoolelanmis bir link vereyim dedim.
cbc
0
cbc
temel ve basit kuralı hiçbir zaman atlamamak gerekiyor.

"yazdığınız kod/tasarladığınız algoritmayı uç değerler için test edin."
Görüş belirtmek için giriş yapın...

İlgili Yazılar

YZC Sözlük v0.0.6 Çıktı
anonim
10 Ekim 2006, 1 dakika okuma süresi

YZC Sözlük, GNU/Linux için GPL lisanslı sözlük uygulamamız 0.0.6 sürümüne ulaşmıştır.

Bu sürümdeki en önemli özellik, programa dahil edilen sınavcı ve -- festival ses sentezleme programını kullanılarak -- kelime seslendirme özelliğidir.

Sözlüğe kaynak kodları ile http://www.yzcsozluk.info adresinden ulaşabilirsiniz.

Açık Kodlu Özgür Bir Yazılım Projesi: FlightGear Uçuş Simülatörü
FZ
16 Ocak 2004, 1 dakika okuma süresi

1995 yılında havacılık simülasyonları konusunda uzmanlaşmış Curtis Olson isimli bir mühedis Microsoft Flight Simulator´a bir eklenti (add-on) yapmaya çalışırken vaktinin büyük bir kısmını asıl iş yerine bu yazılımın dosya formatlarını, iç yapısını, işleyişini, vs. anlamak için enerji harcayarak geçirdiğini fark etti. Ve kendine şöyle dedi: Oturup kendi uçuş simülatörümü yazmaya başlasam, bunu açık kodlu ve GPL lisanslı olarak kamuoyuna sunsam ve sonra...

Olson´un bu çabası ABD´de çılgın bir mühendisin delidolu idealizmi olarak algılanmadı tahmin edebileceğiniz gibi. Proje başladıktan kısa bir süre NASA´daki uzay mekiği programının önemli mühendislerinden biri olan Jon Berndt de projeye destek vermeye başladı. Bu katılımı takiben, bir başka mühendis Tony Peden de projeye katılmakta tereddüt etmedi. Ve gerisi büyük hızla geldi.

FlightGear isimli bu özgür yazılım projesine destek veren deneyimli programcı ve mühendislerin yaş ortalaması 35´in üstünde. Hepsi de kendi alanlarındaki mühendislik ve fizik konularında usta isimler. Geliştirdikleri sistem uç noktadaki havacılık mühendisliği modellerini, grafik (OpenGL) ve ağ programlama tekniklerini kullanıyor. Herkesi sistemlerini incelemeye ve katkıda bulunmaya davet ediyorlar.

Bağış Toplamanın Yeni Yolu: Fundable
arikan
9 Temmuz 2005, 1 dakika okuma süresi

Fundable bir grup insanın paralarını bir araya koyarak bir projeyi desteklemesini veya daha hesaplı ortak birşey satın almasini sağlayan bir web hizmeti. Örneğin açık kaynaklı bir yazılım geliştirmek için, veya bir sanat etkinliği duzenlemek için burada para toplanabiliyor. Belirlenen zaman aralığında belirlenen miktarda para toplanabilirse kampanya başarıya ulaşmış sayılıyor, eğer yeteri kadar para toplanamazsa toplanan paralar sahiplerine geri veriliyor. En son açık kaynaklı Internet text editoru FCKEditor için başlatılan kampanyada 6 kisinin katkısıyla $600 toplandı. Henüz yeni olan sistem online ilişkilerin mikro boyutta ekonomiye bulaşmasına güzel bir örnek.

CD Player ararken...
conan
5 Mart 2002, 1 dakika okuma süresi

Demin monster`ıma CD Player arıyordum (monster benim penguenin adi) console based olmayan, grafik arabirimli, CDDB ozelliği olan ekranda da fazla yer tutmayacak bi program bakınıyordum. grip ile karşılaştım. Çok cici bir arabirimi var. Sonra bir baktım CD-RiP, RiP+Encode gibi özellikleri de varmış. lame, cdparanoia gibi toolları toparlayıp, güzel bir arabirimde sunmuşlar. binary dosya stripped halde 454 K. GUI yaratmak için GTK kullanılmış. İçinde built-in Help menüsü de çıkıyor ki bu beni şaşırttı biraz :) Help`i çalıştırdım şimdi... Nautilus açıldı! Ne alakaysa. :)) [Naklen yayın oldu biraz]

Neyse en sevdiğim yönü ise küçük bir şekilde bi kenara koyup da sakin sakin çalmasını sağlayabiliyorsunuz. Bence oldukça güzel bir program. Herkeslere tavsiye ediyorum. Özellikle benim gibi CD dinlemeyi seviyorsanız. blackbox menüme hemen ekledim :) Sayfada screenshot`lar var.

Müzikli günler.

Nokia: Python Kullanmak İçin Bir Sebep Daha
FZ
1 Şubat 2006, 1 dakika okuma süresi

Cep telefonu üreticisi Nokia, S60 serisi cep telefonlarının artık Python ile programlanabileceğini duyurdu. Açık kodlu olarak geliştirilen bu proje ile cep telefonlarını programlamak çok daha kolay hale gelmiş durumda. Bir kıyaslama yapmak gerekirse Hello World in C++, Epoc style (for Symbian OS) koduna bakılabilir. Benzer işi yapan bir Python programı ise 4-5 satır uzunlukta. (C++ linki için Hakan Latifaoğlu'na teşekkürler.)