Bug storico...

Posted by Lucio Benfante Fri, 16 Jun 2006 05:03:00 GMT

...presente nel JDK, e probabilmente nella maggior parte delle implementazioni di algoritmi con approccio “divide et impera”.

Quanti di noi non hanno mai scritto questa semplice e innocente riga di codice (con low e high di tipo int)?

int mid = (low+high)/2;

Il problema è che la somma dei due interi può risultare in un overflow…gosh…

L’implementazione corretta sarebbe qualcosa di simile a:

int mid = low + ((high-low)/2);

Provate a cercare in qualunque libro di algoritmi e vedrete che anche i grandi sbagliano. Io ho guardato in ‘The Art of Computer Programming’), e anche l’implementazione dell’algoritmo di ricerca binaria di Donald E. Knuth soffre dello stesso bug.

Per quanto riguarda il JDK, il bug si trova (almeno) nel metodo binarySearch della classe java.utils.Arrays. A me non è mai capitato, ma ve l’immaginate la sorpresa (per non dire altro) di vedervi sollevare un ArrayIndexOutOfBoundsException da un metodo di quella classe?

L’annuncio e la discussione del bug li fa lo stesso autore della classe, Josh Bloch, in questo blog.

Posted in  | Tags , , ,  | 5 comments | no trackbacks

JUGMeeting #25 - "Aop e Motori di Ricerca"

Posted by Andrea Nasato Sat, 18 Feb 2006 14:44:00 GMT

Quando: Sabato 18 Febbraio 2006 dalle 09:00 alle 12:30

Dove: aula De – piano terra al DEI, via Gradenigo 6/B (ingresso studenti) Padova

Programma:
09:00 Accoglienza
09:15 “Algoritmi di analisi dei link per motori di ricerca” a cura del prof. Luca Pretto (slides)
10:15 D&R – Domande e Risposte
10:30 Pausa caffe’ – Java Break
10:45 “Programmazione Orientata agli Aspetti e AspectJ” a cura di Mariano Ceccato (slides)
11:45 D&R – Domande e Risposte
12:00 “Eventi e Proposte” a cura di tutto il JUGPadova
12:30 Fine meeting 25
13:00 Pizza con chi vuole fermarsi con noi ;-)


Ingresso sempre libero!

Il PDF della locandina lo trovate a questo indirizzo

Vi aspettiamo!!!

Posted in  | Tags , ,