Blog de Vincent Brabant : NetBeans, Java et autres

15
décembre
2007

Événements Java // Javapolis 2007

Javapolis 2007 : à l’année prochaine.

Un article de vbrabant Comments

8 Commentaires

Et bien voilà. Javapolis est terminé. Fini.

Un grand merci à Stephan Janssen, le fondateur de cet événement, et toute son équipe pour cet excellent événement.

Pour terminer en beauté, sachez que Joshua Bloch vous recommande des lubrifiants en polygène.
(j’espère que j’ai traduit correctement)

Bien évidemment ceci n’est pas sérieux. C’est l’un des Puzzles que Joshua Bloch co-présentait avec Neal Gafter jeudi en fin d’après midi. Mais celui-là m’a bien fait rire.

Voici un bout de son code qu’il nous proposait :

public class Histogram {
private static final String[] words =
{ "I", "recommend", "polygene", "lubricants"};
public static void main(String[] args) {
int[] histogram = new int[5];
for (String word1 : words) {
for (String word2 : words) {
String pair = word1+word2;
int bucket = Math.abs(pair.hashCode()) % histogram.length;
histogram[bucket]++;
}
}
//Suis plus trop sûr du code ci-dessous, mais le résultat est le même
int total = 0;
for (int i : histogram) {
total+=i;
}
System.out.println(total);
}
}

Et la question était de ce style :

Quel est le résultat ?
4, 16, change tout le temps, erreur à l’exécution

J’attends vos réponses, et les explications qui vont avec (que ceux qui connaissent la réponse parce qu’ils ont assisté à la session laisse la parole aux autres. Merci)

8 Commentaires + Ajouter un commentaire

Uther 17 décembre 2007 à 17 h 56 min

Que « polygenelubricants ».hashcode() donne Integer.MIN_VALUE c’est vraiment pas de bol. C’est clairement le genre de problème qu’on ne peut pas deviner si on n’execute pas le code.

ilaborie>Personnelement je coderai plutot le Math.abs() avec une exception pour le cas Integer.MIN_VALUE, un peux comme la division par Zéro.

C’est vrai que lancer une exception peut paraitre illogique. C’est aussi ce que j’ai pensé au début. Mais en fait c’est tout à fait conforme à la logique JAVA: pas d’execptions pour les overflows sur les entiers.
En java « MAX_VALUE+1 == MIN_VALUE » sera vrai et ne levera pas d’exception.
Pour les division par 0 par contre, il y a exception car c’est une opération mathématiquement interdite.

La valeur absolue de MIN_VALUE existe bel et bien : c’est -MIN_VALUE.
Pas de chance, le mécanisme des overflows fait que -MIN_VALUE donne MIN_VALUE, sans générer d’exceptions.

Connectez-vous pour répondre
n!co 17 décembre 2007 à 15 h 53 min

La solution proposée par le yam’s n’est pas possible car elle modifie le hascode de pair et eronne donc la valeur de bucket servant à stocker l’information dans l’histogram.

En faite je crois que je me suis un peu avancé après avoir regardé de plus près les autres solutions proposées

Connectez-vous pour répondre
n!co 17 décembre 2007 à 15 h 50 min

> vbrabant
Effectivement j’ai ecrit une connerie !!

Math.abs(Integer.MIN_VALUE) == -Integer.MIN_VALUE == -(-2147483648) == 2147483648 => IMPOSSIBLE car on depasse la valeur maximum d’un integer Integer.MAX_VALUE == 2147483647 == -2³¹-1

Java à alors fait le choix de renvoyer Integer.MIN_VALUE, mais là je ne sais pas l’expliquer.

La solution proposée par le yam’s n’est pas possible car elle modifie le hascode de pair et eronne donc la valeur de bucket servant à stocker l’information dans l’histogram.

Un solution simple est alors de faire le modulo avant de faire l’abs :
int bucket = Math.abs(pair.hashCode() % histogram.length);

D’autres solutions que je ne m’aventurerais pas a exlipquer proposées dans la solution du puzzle ;-P :

• Or (pair.hashCode() >>> 1) % histogram.length
• Or (pair.hashCode() & 0x7fffffff) % histogram.length
• Or use power-of-two length array
(pair.hashCode() & (histogram.length – 1))

Connectez-vous pour répondre
ilaborie 17 décembre 2007 à 14 h 37 min

Les Integer sont codés sur 32 bits avec
Integer.MAX_VALUE = 2147483647 (2^31 – 1)
Integer.MIN_VALUE = -2147483648 -(2^31)
car il nous faut un Zéro…

D’après la javadoc de Math.abs avec l’entier minimal:
Math.abs(Integer.MIN_VALUE) = Integer.MIN_VALUE
Donc c’est un nombre négatif !

Et pas de de bol polygenelubricants ».hascode() = Integer.MIN_VALUE d’ou le OutOfBoundException.

Personnelement je coderai plutot le Math.abs() avec une exception pour le cas Integer.MIN_VALUE, un peux comme la division par Zéro.

Connectez-vous pour répondre
$Avatar de le y@m\$

le y@m\'s 17 décembre 2007 à 12 h 00 min

Le problème a en effet un rapport avec le fait que « polygenelubricants ».hascode() == Integer.MIN_VALUE.
Mais c’est la méthode Math.abs() qui pose problème et non le modulo.
En effet, selon la Javadoc de la méthode Math.abs() :

Note that if the argument is equal to the value of Integer.MIN_VALUE, the most negative representable int value, the result is that same value, which is negative.

Pour corriger le problème je ferais un truc comme ça :

public class Histogram {   
  private static final String[] words = { "I", "recommend", "polygene", "lubricants"};   
  public static void main(String[] args) {   
  int[] histogram = new int[5];   
  for (String word1 : words) {   
  for (String word2 : words) {   
  String pair = word1+word2;   
  int hashcode = Math.abs(pair.hashCode());  
  if(hashcode == Integer.MIN_VALUE) {  
  hashcode = Integer.MAX_VALUE;  
  }  
  int bucket = hashcode % histogram.length;  
  System.out.println("bucket = " + bucket);  
  histogram[bucket]++;   
  }   
  }   
  int total = 0;   
  for (int i : histogram) {   
  total+=i;   
  }   
  System.out.println(total);   
  }   
}

Le résultat donné est alors : 16

Connectez-vous pour répondre
vbrabant 16 décembre 2007 à 22 h 10 min

nico, désolé, mais je ne t’ai pas suivi dans tes explications. Tu dis que MIN_VALUE == MAX_VALUE (0x80000000). Pourrais tu expliquer un peu plus.
Et que faut-il faire pour solutionner le problème ? Et qu’elle est le résultat une fois le problème résolu et pourquoi ?

Connectez-vous pour répondre
n!co 16 décembre 2007 à 20 h 34 min

Erreur à l’exécution

La valeur retournée par Math.abs() n’est pas assurée d’être positif, l’exception est Math.abs(Integer.MIN_VALUE) car Integer.MIN_VALUE == Integer.MAX_VALUE (0x80000000) !!! .
Et dans le code, « polygenelubricants ».hascode() == Integer.MIN_VALUE.
Le modulo pouvant renvoyer un valeur négative, cela provoque un ArrayOfBoundException.

Il ma tout de même fallu exécuter le code pour constater le problème et remonter à la source. Par contre je ne sais pas pour le hashcode de « polygenelubricants » renvoi une valeur à la limite des capacités du int, hazard ?

Ce code a été utilisé plusieurs fois dans des projets d’envergure, sûrement corrigé depuis !
http://bmaurer.blogspot.com/2006/10/mathabs-returns-negative-number.html

Connectez-vous pour répondre
Matthieu Brucher 16 décembre 2007 à 9 h 39 min

Ne connaissant pas Java, je ne sais pas si histogram est initialisé à zéro, donc :
– si c’est le cas, je dirai 16
– si ce n’est pas le cas, ça change tout le temps ?

Connectez-vous pour répondre