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

Görüşler

ahmetaa
18 yıl önce

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
18 yıl önce

>>>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
18 yıl önce

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
18 yıl önce

Yahut böyle bir probleme yol açmayacak programlama dillerinden birini kullanmak? Bu da bir seçenek.

newman
18 yıl önce

Lisp demek istiyorsun :). Yani kasiniyorsunuz kardes ;)

ahmetaa
18 yıl önce

aslinda bir bos vaktinizde lisp icinde bir milyarlik bir dizide binary search yapabilirseniz sevinirim..

bm
18 yıl önce

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
18 yıl önce

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
18 yıl önce

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
18 yıl önce

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
18 yıl önce

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
18 yıl önce

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.

tongucyumruk
18 yıl önce

Ö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
18 yıl önce

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
18 yıl önce

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.

tongucyumruk
18 yıl önce

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
18 yıl önce

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
18 yıl önce

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
18 yıl önce

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
18 yıl önce

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
18 yıl önce

Kulaga siir gibi geliyor, ama olacagini sanmiyorum :). Ben o konuda cok beklenti icerisinde degilim. Guzel olurdu vallahi!

FZ
18 yıl önce

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
18 yıl önce

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
18 yıl önce

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
18 yıl önce

"... -pi/4 +pi/4 arasi degerler..."
sinus ve kosinus icin -pi/4 +pi/4 arasi degerler... olacakti.

FZ
18 yıl önce

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
18 yıl önce

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
18 yıl önce

şu "sayı mod 2^32" kısmını tam anlayamadım buradaki sayı 2'lik düzendeki bir sayı mı oluyor ?

newman
18 yıl önce

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
18 yıl önce

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
18 yıl önce

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
18 yıl önce

Yanlis anlama olmasin "Bunun performansa olumsuz etkisi olabilir..." derken assembly kullanilmasini kasdetmedim :), problemi cozmek icin kullanilan extra isi kasdettim.

FZ
18 yıl önce

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
18 yıl önce

Ç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
18 yıl önce

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
18 yıl önce

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
18 yıl önce

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
18 yıl önce

Ö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
18 yıl önce

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
18 yıl önce

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
18 yıl önce

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
18 yıl önce

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
18 yıl önce

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
18 yıl önce

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
18 yıl önce

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
18 yıl önce

İ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
18 yıl önce

Pardon min + (max - min)/2 olacaktı; bir roket de biz düşürmeyelim ;)

myavuzselim
18 yıl önce

Kalkamazdi ki bile :)

bm
18 yıl önce

Bu arada bu overflow islerini populer dergilere kadar indiren Ariane roketi bugini bilmeyenler vardir belki diye size ongoolelanmis bir link vereyim dedim.

cbc
18 yıl önce

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...

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

Görüşler

İlgili Yazılar

Sony PSP ve Lua Programlama

Firebird v1.5 kararlı sürüm duyuruldu.

Eclipse İçin Türkçe İmla Denetimi Eklentisi: Musahhih

Kayıtsız kalmayın!

PostgreSQL 7.4 sürümü duyuruldu