"Compresser" les clés d'un hash

Le
JalaL
Bonjour a tous,

J'ai un serieux probleme avec un gros hash auquel je dois ajouter de
nouvelles valeurs pendant l'execution du programme.

Le hash est sous forme de %hash->{$url} = $url_id;

Pour le reduire, j'ai utilisé Digest::MD5. En encodant les URLs, parfois
trop longues, et parfois trop courtes en 32 characteres j'arrive a reduire
la taille totale (length) de toutes les clés à 1/3 de la taille originale
(sans md5). Ce qui est déjà une belle performance.

Inutile d'utiliser Compress::Zlib::memGzip parce qu'en plus de sa leuteur
elle augmente la taille totale des clés.

J'aimerai savoir s'il y a un autre moyen plus efficace et plus performant
que MD5 pour reduire la taille des clés tout en conservant la structure du
hash et des clés uniques.
Vos réponses Page 1 / 2
Trier par : date / pertinence
JalaL
Le #135321
"JalaL" 45927ea9$0$8236$
Bonjour a tous,

J'ai un serieux probleme avec un gros hash auquel je dois ajouter de
nouvelles valeurs pendant l'execution du programme.

Le hash est sous forme de %hash->{$url} = $url_id;

Pour le reduire, j'ai utilisé Digest::MD5. En encodant les URLs, parfois
trop longues, et parfois trop courtes en 32 characteres j'arrive a reduire
la taille totale (length) de toutes les clés à 1/3 de la taille originale
(sans md5). Ce qui est déjà une belle performance.

Inutile d'utiliser Compress::Zlib::memGzip parce qu'en plus de sa leuteur
elle augmente la taille totale des clés.

J'aimerai savoir s'il y a un autre moyen plus efficace et plus performant
que MD5 pour reduire la taille des clés tout en conservant la structure du
hash et des clés uniques.



Pour optimizer encore plus, je voulais MD5er les URLs plus longues que 32
caracteres seulement, les autres URLs plus courtes seront stockées sans
modification. je pensais faire mieux mais non... un peu bizare.

Bah c'est là que je decouvre que MD5 donne un hash de 16 caracteres
seulement. Ca permet d'economiser quelques Ko de memoire, et a long terme ca
economisera quelques centaines de Ko voire quelques Mo.

Je cherche toujours a faire mieux, vos suggestions sont les bienvenues.

Nicolas George
Le #135320
"JalaL" wrote in message
economisera quelques centaines de Ko voire quelques Mo.


Autant dire rien dans la plupart des situations courantes.

Je cherche toujours a faire mieux, vos suggestions sont les bienvenues.


Décrire ce que tu veux faire au final, et pas les moyens techniques que tu
mets en oeuvre pour y parvenir.

JalaL
Le #135319
"Nicolas George" news: 4592a168$0$25425$
"JalaL" wrote in message
economisera quelques centaines de Ko voire quelques Mo.


Autant dire rien dans la plupart des situations courantes.

Je cherche toujours a faire mieux, vos suggestions sont les bienvenues.


Décrire ce que tu veux faire au final, et pas les moyens techniques que tu
mets en oeuvre pour y parvenir.


Faut lire un peu ce que j'ai ecrit !!!

J'aimerai savoir s'il y a UN AUTRE MOYEN plus efficace et plus
performant que MD5 pour reduire la taille des clés tout en conservant la
structure du hash et des clés uniques.


Si je continu mes recherches en parallele c'est just pour ne pas attendre 3h
une reponse de ce genre.


Nicolas George
Le #135318
"JalaL" wrote in message
Faut lire un peu ce que j'ai ecrit !!!


J'ai lu : tu veux bidouiller des hashes de hashes d'URL pour que ça prenne
moins de place, mais tu ne dis pas ce que tu veux faire avec.

JalaL
Le #135317
"Nicolas George" news: 4592ae08$0$30302$
"JalaL" wrote in message
Faut lire un peu ce que j'ai ecrit !!!


J'ai lu : tu veux bidouiller des hashes de hashes d'URL pour que ça prenne
moins de place, mais tu ne dis pas ce que tu veux faire avec.


Pouvoir chercher dans le hash l'identifiant d'une URL, si l'URL n'existe pas
je la rajoute avec son identifiant. L'identifiant c'est un entier que
j'incremente en cas de nouvelle URL. Ca m'evitera d'utiliser une base de
données ou un fichier texte.


Nicolas George
Le #135316
"JalaL" wrote in message
Pouvoir chercher dans le hash l'identifiant d'une URL, si l'URL n'existe pas
je la rajoute avec son identifiant. L'identifiant c'est un entier que
j'incremente en cas de nouvelle URL. Ca m'evitera d'utiliser une base de
données ou un fichier texte.


Tu es fatiguant. Si tu ne veux pas d'aide, n'en demande pas, mais si tu veux
de l'aide, décris ce que tu veux faire de manière complète : serveur,
application ponctuelle, bibliothèque ? sur de l'embarqué ou sur un
ordinateur normal ? Et j'en passe.

JalaL
Le #135314
"Nicolas George" news: 4592b4e4$0$14850$
"JalaL" wrote in message
Pouvoir chercher dans le hash l'identifiant d'une URL, si l'URL n'existe
pas
je la rajoute avec son identifiant. L'identifiant c'est un entier que
j'incremente en cas de nouvelle URL. Ca m'evitera d'utiliser une base de
données ou un fichier texte.


Tu es fatiguant. Si tu ne veux pas d'aide, n'en demande pas, mais si tu
veux
de l'aide, décris ce que tu veux faire de manière complète : serveur,
application ponctuelle, bibliothèque ? sur de l'embarqué ou sur un
ordinateur normal ? Et j'en passe.


Tu vas trop loin là... !!!

Je ne sais pas si ca va changer quelque chose si je fais un cahier des
charges de ce que je vais faire avec ce de hash, la question est posée,
comment optimiser les clés du hash pour economiser la memoire et accelerer
la recherche dans le hash ? Si t'as pas de reponse a apporter pour une
question simple, ne cherche pas plus de complication.


Nicolas George
Le #135313
"JalaL" wrote in message
Je ne sais pas si ca va changer quelque chose si je fais un cahier des
charges de ce que je vais faire avec ce de hash, la question est posée,
comment optimiser les clés du hash pour economiser la memoire et accelerer
la recherche dans le hash ? Si t'as pas de reponse a apporter pour une
question simple, ne cherche pas plus de complication.


Le problème est que ce genre de question en général, et ta question en
particulière, ne soulèvent pas le bon problème. Je ne sais pas ce que tu
cherches à faire au juste, mais rien qu'à l'énoncé de la question, je suis à
peu près sûr que ton véritable problème est ailleurs. Sans détails, je ne
peux qu'hasarder deux hypothèses :

- L'architecture de ta solution est à revoir.

- Tu cherches à micro-optimiser des choses qui n'en ont pas le moins du
monde besoin.

Mais je suis bien certain que l'une ou l'autre est correcte.

JalaL
Le #135312
"Nicolas George" news: 4593132d$0$22856$
Le problème est que ce genre de question en général, et ta question en
particulière, ne soulèvent pas le bon problème. Je ne sais pas ce que tu
cherches à faire au juste, mais rien qu'à l'énoncé de la question, je suis
à
peu près sûr que ton véritable problème est ailleurs. Sans détails, je ne
peux qu'hasarder deux hypothèses :

- L'architecture de ta solution est à revoir.

- Tu cherches à micro-optimiser des choses qui n'en ont pas le moins du
monde besoin.

Mais je suis bien certain que l'une ou l'autre est correcte.


Je suppose que ma question etait precise, tu n'es pas obligé de repondre.

espie
Le #135188
In article JalaL
Bonjour a tous,

J'ai un serieux probleme avec un gros hash auquel je dois ajouter de
nouvelles valeurs pendant l'execution du programme.

Le hash est sous forme de %hash->{$url} = $url_id;

Pour le reduire, j'ai utilisé Digest::MD5. En encodant les URLs, parfois
trop longues, et parfois trop courtes en 32 characteres j'arrive a reduire
la taille totale (length) de toutes les clés à 1/3 de la taille originale
(sans md5). Ce qui est déjà une belle performance.

Inutile d'utiliser Compress::Zlib::memGzip parce qu'en plus de sa leuteur
elle augmente la taille totale des clés.

J'aimerai savoir s'il y a un autre moyen plus efficace et plus performant
que MD5 pour reduire la taille des clés tout en conservant la structure du
hash et des clés uniques.


Attention, deja MD5 ne te garantit pas les cles uniques.

Comme le disait Nicolas, on n'a pas vraiment de chiffres precis sur
ce que tu essaies de faire. Tu parles d'un gros hash, mais c'est quoi,
pour toi un gros hash ? 10000 urls, 10000000 urls ? plus ?

Deja, si tu as suffisamment d'urls, tu vas avoir des collisions. Est-ce que
c'est un probleme pour ton programme, ou est-ce que tu fais juste des
statistiques et tu t'en fous d'avoir des collisions de temps en temps ?

Si c'est des statistitiques, une bete fonction de CRC plus simple que MD5
devrait suffire, voire un algo de crypto `casse', il y a peu de chance que
tu tombes sur un cas d'attaque...

Si tu veux un vrai hash a cles uniques, tu n'as pas le choix, il faut que
tu gardes les urls ou une facon de retomber dessus quelque part. Le md5
n'est pas une garantie absolue d'unicite, alors un truc plus court, encore
moins...

A priori, peut-etre que ce qu'il te faut, c'est un hash plus court, avec les
urls en reserve pour verifier que le hash a fonctionne. J'ai du mal a voir
ce que tu vas pouvoir gagner par rapport a perl lui-meme.... de toutes
facons, si tu reduis tes cles, tu augmentes la probabilite de collision.

Est-ce que ton probleme possede une autre structure qui permettrait de
stocker l'information de maniere plus intelligente ? Quelle est la
repartition de tes urls, par exemple ?

Publicité
Poster une réponse
Anonyme