"Quality Percentage" of hashes as reported by Devel::Peek

This is a multipart message in MIME format.
--===============1102342263==
Content-Type: multipart/alternative;
boundary="=_alternative 00657705862573A6_="

This is a multipart message in MIME format.
--=_alternative 00657705862573A6_=
Content-Type: text/plain; charset="US-ASCII"

Gurus,

I tried directing this query to the module's author, but the e-mail
address as listed in the module's documentation is no longer valid--not
surprising, after nearly a decade, I guess. Anyhoo, I thought I'd ask if
any of you folks might know the answer...

In the documentation for this module's Dump subroutine, a hash's "quality"
is described as a ratio of "total" comparisons versus "expected"
comparisons. There is a formula given for total comparisons, n +
n(n-1)/2k, but no formula is given to determine expected comparisons. The
question is then, how can a user determine mathematically what an expected
quality percentage might be?

I know that Dump outputs the percentage, I'd just like to be able to
calculate it predictively, instead of fiddling keys(%hash) = X assignments
and TIAS-ing for differing values of 'X.'

Is there a formula for expected comparisons available?

Thanks,

Deane Rothenmaier
Programmer/Analyst
Walgreens Corp.
847-914-5150

A word to the wise ain't necessary, it's the stupid ones who need the
advice. -- Bill Cosby
--=_alternative 00657705862573A6_=
Content-Type: text/html; charset="US-ASCII"



Gurus,



I tried directing this query to the
module's author, but the e-mail address as listed in the module's documentation
is no longer valid--not surprising, after nearly a decade, I guess.  Anyhoo,
I thought I'd ask if any of you folks might know the answer...



In the documentation for this module's
Dump subroutine, a hash's "quality" is described as a ratio of
"total" comparisons versus "expected" comparisons.
There is a formula given for total comparisons, n + n(n-1)/2k, but no formula
is given to determine expected comparisons. The question is then, how can
a user determine mathematically what an expected quality percentage might
be?



I know that Dump outputs the percentage,
I'd just like to be able to calculate it predictively, instead of fiddling
keys(%hash) = X assignments and TIAS-ing for differing values of 'X.'



Is there a formula for expected comparisons
available?



Thanks,



Deane Rothenmaier

Programmer/Analyst

Walgreens Corp.

847-914-5150



A word to the wise ain't necessary, it's the stupid ones who need the advice.
-- Bill Cosby              
 
--=_alternative 00657705862573A6_=--


--===============1102342263==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

_______________________________________________
ActivePerl mailing list
ActivePerl@listserv.ActiveState.com
To unsubscribe: http://listserv.ActiveState.com/mailman/mysubs
--===============1102342263==--

RE: "Quality Percentage" of hashes as reported by Devel::Peek

This is a multipart message in MIME format.

--===============1980735802==
Content-Type: multipart/alternative;
boundary="----=_NextPart_000_0A61_01C8359F.852C6310"
Content-Language: en-ca

This is a multipart message in MIME format.

------=_NextPart_000_0A61_01C8359F.852C6310
Content-Type: text/plain;
charset="us-ascii"
Content-Transfer-Encoding: 7bit

You are misreading the documentation. n + N(n-1)/2k is the formula for expected comparisons for a random hash where each bucket is
filled to the same level. The total number of comparisons for the actual hash is equal to the sum of the squares of the number of
entries in each bucket.



>From looking at the code, I wonder if the numbers are correct though, as the ratio seems to be reversed and therefore should be less
than 100%. I don't have time to investigate this though. The actual code lives in dump.c in the core Perl distribution:



if (HvARRAY(sv) && HvKEYS(sv)) {

/* Show distribution of HEs in the ARRAY */

int freq[200];

#define FREQ_MAX ((int)(sizeof freq / sizeof freq[0] - 1))

int i;

int max = 0;

U32 pow2 = 2, keys = HvKEYS(sv);

NV theoret, sum = 0;



PerlIO_printf(file, " (");

Zero(freq, FREQ_MAX + 1, int);

for (i = 0; (STRLEN)i <= HvMAX(sv); i++) {

HE* h;

int count = 0;

for (h = HvARRAY(sv)[i]; h; h = HeNEXT(h))

count++;

if (count > FREQ_MAX)

count = FREQ_MAX;

freq[count]++;

if (max < count)

max = count;

}

for (i = 0; i <= max; i++) {

if (freq[i]) {

PerlIO_printf(file, "%d%s:%d", i,

(i == FREQ_MAX) ? "+" : "",

freq[i]);

if (i != max)

PerlIO_printf(file, ", ");

}

}

PerlIO_putc(file, ')');

/* The "quality" of a hash is defined as the total number of

comparisons needed to access every element once, relative

to the expected number needed for a random hash.



The total number of comparisons is equal to the sum of

the squares of the number of entries in each bucket.

For a random hash of n keys into k buckets, the expected

value is

n + n(n-1)/2k

*/



for (i = max; i > 0; i--) { /* Precision: count down. */

sum += freq[i] * i * i;

}

while ((keys = keys >> 1))

pow2 = pow2 << 1;

theoret = HvKEYS(sv);

theoret += theoret * (theoret-1)/pow2;

PerlIO_putc(file, '\n');

Perl_dump_indent(aTHX_ level, file, " hash quality = %.1"NVff"%%", theoret/sum*100);

}



Cheers,

-Jan



From: activeperl-bounces@listserv.ActiveState.com [mailto:activeperl-bounces@listserv.ActiveState.com] On Behalf Of
Deane.Rothenmaier@walgreens.com
Sent: December 3, 2007 10:28 AM
To: activeperl@listserv.ActiveState.com
Subject: "Quality Percentage" of hashes as reported by Devel::Peek




Gurus,

I tried directing this query to the module's author, but the e-mail address as listed in the module's documentation is no longer
valid--not surprising, after nearly a decade, I guess. Anyhoo, I thought I'd ask if any of you folks might know the answer...

In the documentation for this module's Dump subroutine, a hash's "quality" is described as a ratio of "total" comparisons versus
"expected" comparisons. There is a formula given for total comparisons, n + n(n-1)/2k, but no formula is given to determine expected
comparisons. The question is then, how can a user determine mathematically what an expected quality percentage might be?

I know that Dump outputs the percentage, I'd just like to be able to calculate it predictively, instead of fiddling keys(%hash) = X
assignments and TIAS-ing for differing values of 'X.'

Is there a formula for expected comparisons available?

Thanks,

Deane Rothenmaier
Programmer/Analyst
Walgreens Corp.
847-914-5150

A word to the wise ain't necessary, it's the stupid ones who need the advice. -- Bill Cosby


------=_NextPart_000_0A61_01C8359F.852C6310
Content-Type: text/html;
charset="us-ascii"
Content-Transfer-Encoding: quoted-printable

xmlns:o=3D"urn:schemas-microsoft-com:office:office" =
xmlns:w=3D"urn:schemas-microsoft-com:office:word" =
xmlns:m=3D"http://schemas.microsoft.com/office/2004/12/omml" =
xmlns=3D"http://www.w3.org/TR/REC-html40">


charset=3Dus-ascii">

RE: "Quality Percentage" of hashes as reported by Devel::Peek

Could you clarify a bit more on what you mean by hash quality and expected =
comparisons? I took a look at the devel::peek module, specifically the outp=
uts of its dump function and I couldn't find what you were looking for. It =
sounds like you are attempting to implement a hashing function for an objec=
t but I can't be sure. The CPAN documentation for devel::peek (http://searc=
h.cpan.org/~ilyaz/Devel-Peek-0.96/Peek.pm) doesn't mention quality either. =


Were you referring to another module?


Sean Tobin
byrdhuntr@hotmail.com


________________________________
To: activeperl@listserv.ActiveState.com
Subject: "Quality Percentage" of hashes as reported by Devel::Peek
From: Deane.Rothenmaier@walgreens.com
Date: Mon, 3 Dec 2007 12:28:03 -0600



Gurus,



I tried directing this query to the
module's author, but the e-mail address as listed in the module's documenta=
tion
is no longer valid--not surprising, after nearly a decade, I guess. Anyhoo,
I thought I'd ask if any of you folks might know the answer...



In the documentation for this module's
Dump subroutine, a hash's "quality" is described as a ratio of
"total" comparisons versus "expected" comparisons.
There is a formula given for total comparisons, n + n(n-1)/2k, but no formu=
la
is given to determine expected comparisons. The question is then, how can
a user determine mathematically what an expected quality percentage might
be?



I know that Dump outputs the percentage,
I'd just like to be able to calculate it predictively, instead of fiddling
keys(%hash) =3D X assignments and TIAS-ing for differing values of 'X.'



Is there a formula for expected comparisons
available?



Thanks,



Deane Rothenmaier

Programmer/Analyst

Walgreens Corp.

847-914-5150



A word to the wise ain't necessary, it's the stupid ones who need the advic=
e.
-- Bill Cosby


____________________________________________________________ _____
Put your friends on the big screen with Windows Vista=AE + Windows Live=99.
http://www.microsoft.com/windows/shop/specialoffers.mspx?oci d=3DTXT_TAGLM_C=
PC_MediaCtr_bigscreen_102007
_______________________________________________
ActivePerl mailing list
ActivePerl@listserv.ActiveState.com
To unsubscribe: http://listserv.ActiveState.com/mailman/mysubs

RE: "Quality Percentage" of hashes as reported by Devel::Peek

From: activeperl-bounces@listserv.ActiveState.com
[mailto:activeperl-bounces@listserv.ActiveState.com] On Behalf Of
Deane.Rothenmaier@walgreens.com
Sent: 03 December 2007 18:28
To: activeperl@listserv.ActiveState.com
Subject: "Quality Percentage" of hashes as reported by Devel::Peek

> Gurus, =

> =

> I tried directing this query to the module's author, but the e-mail
address as listed in the module's =

> documentation is no longer valid--not surprising, after nearly a
decade, I guess. Anyhoo, I thought I'd ask if > any of you folks might
know the answer... =


The email address given here may be more valid,
http://search.cpan.org/~ilyaz/.

HTH

-- =

Brian Raven =


==================== =====3D=
================
Atos Euronext Market Solutions Disclaimer
==================== =====3D=
================

The information contained in this e-mail is confidential and solely for the=
intended addressee(s). Unauthorised reproduction, disclosure, modification=
, and/or distribution of this email may be unlawful.
If you have received this email in error, please notify the sender immediat=
ely and delete it from your system. The views expressed in this message do =
not necessarily reflect those of Atos Euronext Market Solutions.

Atos Euronext Market Solutions Limited - Registered in England & Wales with=
registration no. 3962327. Registered office address at 25 Bank Street Lon=
don E14 5NQ United Kingdom. =

Atos Euronext Market Solutions SAS - Registered in France with registration=
no. 425 100 294. Registered office address at 6/8 Boulevard Haussmann 750=
09 Paris France.

L'information contenue dans cet e-mail est confidentielle et uniquement des=
tinee a la (aux) personnes a laquelle (auxquelle(s)) elle est adressee. Tou=
te copie, publication ou diffusion de cet email est interdite. Si cet e-mai=
l vous parvient par erreur, nous vous prions de bien vouloir prevenir l'exp=
editeur immediatement et d'effacer le e-mail et annexes jointes de votre sy=
steme. Le contenu de ce message electronique ne represente pas necessaireme=
nt la position ou le point de vue d'Atos Euronext Market Solutions.
Atos Euronext Market Solutions Limited Soci=E9t=E9 de droit anglais, enregi=
str=E9e au Royaume Uni sous le num=E9ro 3962327, dont le si=E8ge social se =
situe 25 Bank Street E14 5NQ Londres Royaume Uni.

Atos Euronext Market Solutions SAS, soci=E9t=E9 par actions simplifi=E9e, e=
nregistr=E9 au registre dui commerce et des soci=E9t=E9s sous le num=E9ro 4=
25 100 294 RCS Paris et dont le si=E8ge social se situe 6/8 Boulevard Hauss=
mann 75009 Paris France.
==================== =====3D=
================

_______________________________________________
ActivePerl mailing list
ActivePerl@listserv.ActiveState.com
To unsubscribe: http://listserv.ActiveState.com/mailman/mysubs

RE: "Quality Percentage" of hashes as reported by Devel::Peek

Sean Tobin <> wrote:
> Could you clarify a bit more on what you mean by hash quality and
> expected comparisons? I took a look at the devel::peek module,
> specifically the outputs of its dump function and I couldn't find
> what you were looking for. It sounds like you are attempting to
> implement a hashing function for an object but I can't be sure. The
> CPAN documentation for devel::peek
> (http://search.cpan.org/~ilyaz/Devel-Peek-0.96/Peek.pm) doesn't
> mention quality either. =

> =

> Were you referring to another module?

While the version on CPAN, which doesn't mention hash quality, is 0.96,
the version shipped with Activestate version 5.8.8 (build 822) is 1.03,
which does mention it.

As to the question of why is the version of Devel::Peek on CPAN is
older, there you have me. It could be to do with the module now being
part of the core distribution.

HTH

-- =

Brian Raven =


==================== =====3D=
================
Atos Euronext Market Solutions Disclaimer
==================== =====3D=
================

The information contained in this e-mail is confidential and solely for the=
intended addressee(s). Unauthorised reproduction, disclosure, modification=
, and/or distribution of this email may be unlawful.
If you have received this email in error, please notify the sender immediat=
ely and delete it from your system. The views expressed in this message do =
not necessarily reflect those of Atos Euronext Market Solutions.

Atos Euronext Market Solutions Limited - Registered in England & Wales with=
registration no. 3962327. Registered office address at 25 Bank Street Lon=
don E14 5NQ United Kingdom. =

Atos Euronext Market Solutions SAS - Registered in France with registration=
no. 425 100 294. Registered office address at 6/8 Boulevard Haussmann 750=
09 Paris France.

L'information contenue dans cet e-mail est confidentielle et uniquement des=
tinee a la (aux) personnes a laquelle (auxquelle(s)) elle est adressee. Tou=
te copie, publication ou diffusion de cet email est interdite. Si cet e-mai=
l vous parvient par erreur, nous vous prions de bien vouloir prevenir l'exp=
editeur immediatement et d'effacer le e-mail et annexes jointes de votre sy=
steme. Le contenu de ce message electronique ne represente pas necessaireme=
nt la position ou le point de vue d'Atos Euronext Market Solutions.
Atos Euronext Market Solutions Limited Soci=E9t=E9 de droit anglais, enregi=
str=E9e au Royaume Uni sous le num=E9ro 3962327, dont le si=E8ge social se =
situe 25 Bank Street E14 5NQ Londres Royaume Uni.

Atos Euronext Market Solutions SAS, soci=E9t=E9 par actions simplifi=E9e, e=
nregistr=E9 au registre dui commerce et des soci=E9t=E9s sous le num=E9ro 4=
25 100 294 RCS Paris et dont le si=E8ge social se situe 6/8 Boulevard Hauss=
mann 75009 Paris France.
==================== =====3D=
================

_______________________________________________
ActivePerl mailing list
ActivePerl@listserv.ActiveState.com
To unsubscribe: http://listserv.ActiveState.com/mailman/mysubs

RE: "Quality Percentage" of hashes as reported by Devel::Peek

This is a multipart message in MIME format.
--===============2040989182==
Content-Type: multipart/alternative;
boundary="=_alternative 004C7B91862573A7_="

This is a multipart message in MIME format.
--=_alternative 004C7B91862573A7_=
Content-Type: text/plain; charset="US-ASCII"

Thanks to all who answered, but Mr. Dubos provided the guts of the
question--he sent some source code that explained it all.

Thanks again!

Deane Rothenmaier
Programmer/Analyst
Walgreens Corp.
847-914-5150

Let us permit nature to have her way; she understands her business better
than we do. -- Michel de Montaigne
--=_alternative 004C7B91862573A7_=
Content-Type: text/html; charset="US-ASCII"



Thanks to all who answered, but Mr.
Dubos provided the guts of the question--he sent some source code that
 explained it all.



Thanks again!



Deane Rothenmaier

Programmer/Analyst

Walgreens Corp.

847-914-5150



Let us permit nature to have her way; she understands her business better
than we do. -- Michel de Montaigne
--=_alternative 004C7B91862573A7_=--


--===============2040989182==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

_______________________________________________
ActivePerl mailing list
ActivePerl@listserv.ActiveState.com
To unsubscribe: http://listserv.ActiveState.com/mailman/mysubs
--===============2040989182==--