Je dispose de code Java que je voudrais réécrire en Perl, et j'ai toutes les peines du monde sur la fonction longHashcode(String str) que voici :
public static long longHashCode(String str) {
long h = 0;
byte val[] = str.getBytes();
int len = str.length();
for (int i = 0; i < len; i++)
h = 31 * h + val[i];
return h;
}Voici deux exemples de ce que me renvoie ce code pour deux entrées :
short_string => 3010251491749729588
rather_longer_longer_string => -3822599824667020448
En cherchant sur le Web, j'ai trouvé une piste (http://poeticcode.wordpress.com/2008/03/10/perl-string-hashc(...) ), que j'ai adaptée avec Math::BigInt pour avoir des entiers longs :
use Math::BigInt;
sub hashCode {
my $hash = Math::BigInt->new();
foreach(split //,shift) {
$hash = 31*$hash+ord($_);
}
return $hash->bstr();
}
Ce qui est un début, mais pas le résultat final, loin s'en faut : pour les chaînes de caractères courtes ("short_string" par exemple), tout va bien et j'ai le même résultat en Perl et Java, mais quand la chaîne s'allonge, Perl continue d'incrémenter la valeur de $hash là où Java ne dépasse jamais la longueur max d'un long. Comment dire à Perl de se comporter autrement?
J'ai essayé toutes sortes des trucs tordus et inefficaces, en vain ! Pourtant, j'ai l'impression que c'est pas si compliqué, mais les compétences me manquent... quelqu'un saurait-il m'aider ?
Merci d'avance de votre aide !
# pb encodage sur la fonction java
Posté par norbs . Évalué à 2.
# Commentaire supprimé
Posté par Anonyme . Évalué à 4.
Ce commentaire a été supprimé par l’équipe de modération.
[^] # Re: Quel est ton but ?
Posté par mouling . Évalué à 1.
Le code existant, en l'occurrence, crée des clés numériques à partir d'urls, qui servent de clé primaire dans une BDD ensuite ; j'ai donc besoin de reproduire cette fonction de transformation à l'identique.
J'avais aussi regardé les modules Digest, mais aucun ne semblait reproduire le comportement du HashCode java que je dois cloner...
# Hash ?
Posté par Frédéric Perrin (site web personnel) . Évalué à 2.
Faudrait savoir, tu veux un hash modulo 2^(sizeof long) ou une sorte de polynôme dont les coefficients sont les valeurs des octets de la chaîne ?
Si c'est le premier, à vue de nez il faudrait ajouter un $hash = $hash % (2 ** 64); à la fin du calcul (à vérifier, je me trompe peut-être de puissance de deux).
[^] # Re: Hash ?
Posté par mouling . Évalué à 2.
J'ai fait un test idiot comme ceci :
public static void testlongHashCode() {
long h = Long.MAX_VALUE;
System.out.println( " h vaut : "+h);
h++ ;
System.out.println("h vaut : "+h);
}
qui me renvoie :
h vaut : 9223372036854775807
h vaut : -9223372036854775808
Ca me laisse penser qu'il passe du MAX au MIN, mais je n'ai pas les compétences pour interpréter ce comportement et le reproduire en Perl.
[^] # Re: Hash ?
Posté par jigso . Évalué à 3.
my $MAX_VALUE = Math::BigInt->new("9223372036854775808");
foreach(split //,shift) {
$hash = 31*$hash+ord($_);
if ($hash >= $MAX_VALUE) {
$hash = $hash - 2*MAX_VALUE;
}
}
En fait Java doit coder les longs sur 64bits, dont un bit de signe. Quand il dépasse 2^63-1, la retenue tombe sur le bit de signe, et on repart à -2^63. Classique des langages de soit-disant haut niveau, qui devraient être indépendants des détails d'implémentations, mais qui gère mal (cad pas du tout) ce genre de cas...
[^] # Re: Hash ?
Posté par TortuXm . Évalué à 3.
http://java.sun.com/docs/books/jls/third_edition/html/lexica(...)
Les long sont des entiers codés sur 64 bits quelle que soit l'architecture.
Concernant l'overflow :
http://java.sun.com/docs/books/jls/third_edition/html/conver(...)
En gros ils ne gardent que les bits de poids faible en cas d'overflow. Je n'ai pas testé sur d'autres archis pour savoir si c'est vraiment portable par contre...
[^] # Re: Hash ?
Posté par mouling . Évalué à 1.
Outre le fait qu'avec les objets BigInt, il faut passer par les méthodes ad-hoc pour les opérations arithmétiques ($x->badd($y), $x->bmul($y)...), même en décomposant, je n'y arrive pas.
Dans la fonction, il y a deux opérations : une multiplication par 31 et une addition.
Pour la multiplication, j'essaye pourtant de gérer les deux bornes inférieure et supérieure, mais même en la décomposant en une série de 30 additions, et en vérifiant qu'on est bien dans les bornes et en corrigeant par (2*MAX - 1), je ne retrouve pas la sortie attendue, même pour le cas d'une chaîne courte.
Je me demande sur le fond comment, dans un cas de multiplication, un langage qui code sur 64 bits opère : est-ce qu'il décompose en une série d'additions ou de soustractions (qui devrait être gérable) ou fait-il une seule transformation qui nécessiterait de travailler en Perl non plus avec BigInt mais plutôt au niveau des bits ?
[^] # Re: Hash ?
Posté par Frédéric Perrin (site web personnel) . Évalué à 2.
Par contre, je n'avais pas compris que tu *voulais* des clefs négatives... Comme dit plus haut, fais les calculs en précision arbitraire avec Math::BigInt, puis tu te remets à la main dans le domaine -2^63; 2^63-1.
# La solution
Posté par mouling . Évalué à 1.
Je partage donc cette solution avec vous ; elle reprend les idées de Fred, jigso et TortuXm consistant à ''remettre dans le domaine'' toute addition/soustraction qui sorte du min et du max d'un entier codé sur 64 bits.
Comme il faut utiliser Math::BigInt, il faut bien prendre soin de passer par les méthodes idoines pour l'arithmétique et les comparaisons de ce type d'objets (cf http://search.cpan.org/~tels/Math-BigInt-1.89/lib/Math/BigIn(...) ), d'où un code un peu verbeux, et pas forcément optimisé, mais la performance est secondaire pour le problème qui m'occupe ici.
Voici, donc :
sub hashCode {my $hash = Math::BigInt->new();
my $MAX_VALUE = Math::BigInt->new('9223372036854775808');
my $MIN_VALUE = Math::BigInt->new('-9223372036854775807');
foreach(split //,shift) {
my $tmp = Math::BigInt->new();
$tmp=$hash->copy();
for ($i=1 ; $i<=30 ; $i++) {
$hash->badd($tmp);
if ($hash->bcmp($MAX_VALUE)>0) {
$hash->bsub($MAX_VALUE);
$hash->bsub($MAX_VALUE);
}
if ($hash->bcmp($MIN_VALUE)<0) {
$hash->badd($MAX_VALUE);
$hash->badd($MAX_VALUE);
}
}
$hash->badd(ord($_));
if ($hash->bcmp($MAX_VALUE)>0) {
$hash->bsub($MAX_VALUE);
$hash->bsub($MAX_VALUE);
}
}
return $hash->bstr();
}
[^] # Re: La solution
Posté par mouling . Évalué à 1.
J'étais tellement content d'avoir un truc qui marche, que je me suis empressé de le couler dans le marbre !
sub hashCode {
my $hash = Math::BigInt->new();
my $MAX_VALUE = Math::BigInt->new('9223372036854775808');
my $MIN_VALUE = Math::BigInt->new('-9223372036854775807');
foreach(split //,shift) {
$hash->bmul(31);
$hash->badd(ord($_));
while ($hash->bcmp($MAX_VALUE)>0) {
$hash->bsub($MAX_VALUE);
$hash->bsub($MAX_VALUE);
}
while ($hash->bcmp($MIN_VALUE)<0) {
$hash->badd($MAX_VALUE);
$hash->badd($MAX_VALUE);
}
}
return $hash->bstr();
}
[^] # Re: La solution
Posté par jigso . Évalué à 2.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.