Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Deterministic or keys in random order

by andreas1234567 (Vicar)
on May 14, 2008 at 13:08 UTC ( #686505=perlquestion: print w/replies, xml ) Need Help??

andreas1234567 has asked for the wisdom of the Perl Monks concerning the following question:

I did an online Perl exam today and it made we wonder: Is the answer to this question really deterministic?
# Enter the output of the following: use strict; use warnings; my %hash = ("Zero","0","One","1","Two","2"); my @array = keys %hash; print "$array[0]\n"; __END__
keys says:
The keys are returned in an apparently random order. The actual random order is subject to change in future versions of perl, but it is guaranteed to be the same order as either the "values" or "each" function produces (given that the hash has not been modified). Since Perl 5.8.1 the ordering is different even between different runs of Perl for security reasons (see "Algorithmic Complexity Attacks" in perlsec).
Nevertheless, I'm not able to see the that the keys are returned in random order. What am I missing?
$ cat foo.t use strict; use warnings; use Test::More; plan tests => 10_000; sub get { my %hash = ("Zero","0","One","1","Two","2"); my @array = keys %hash; return $array[0]; } for (1 .. 10_000) { ok(get() eq 'Zero', q{Expect Zero}); } __END__ $ /usr/bin/prove foo.t foo....ok All tests successful. Files=1, Tests=10000, 5 wallclock secs ( 2.18 cusr + 0.06 csys = 2. +24 CPU)
For the record:
This is perl, v5.8.5 built for i386-linux-thread-multi
--
No matter how great and destructive your problems may seem now, remember, you've probably only seen the tip of them. [1]

Replies are listed 'Best First'.
Re: Deterministic or keys in random order
by ikegami (Patriarch) on May 14, 2008 at 14:14 UTC

    The order is not random in a cryptographic sense. It simply has no bearing on the order in which elements were added and no apparent bearing on the keys. The order in which keys, values and each return their results is based on the internal format of the hash.

    The internal format of the hash does not change if no keys are added to the hash, so the order is guaranteed not change if no change is made to the hash. @hash1{keys %hash2} = values %hash2; will work, for example.

    In fact, if you repeat the steps you used to create a hash to create a new hash in the same process, the new hash should be in the same order.

    Anyway, the point is that "random" is not a goal, but a possible side-effect.

    Unrelated, a security measure has been in place since Perl 5.8.1 to randomize the order between perl processes. That means if repeat the steps you used to create a hash to create a new hash in the different process, the new hash may be in a different order.

    So your test fails (by not returning failures) for two reasons:
    An unchanged hash doesn't change its order.
    You only have one process involved, so the security measure isn't applicable.

Re: Deterministic or keys in random order
by psini (Deacon) on May 14, 2008 at 13:19 UTC

    It isn't random id that sense of word.

    Any given instance of a hash variable has an intrinsic order which is mantained until the hash is modified. So if you repeatedly check the first result of keys on the same hash you'll find always the same key

    The order of the keys is "random" in the sense that it is not (easily) predictable; if you add a new key to the hash it could be in any position.

    Rule One: Do not act incautiously when confronting a little bald wrinkly smiling man.
Re: Deterministic or keys in random order
by almut (Canon) on May 14, 2008 at 13:42 UTC

    If you're specifically referring to "Since Perl 5.8.1 the ordering is different even between different runs of Perl...", I think the "different runs of Perl" is meant to be taken literally, i.e. executing the perl binary. I.e. when dumping the HASH_SEED value, you should in fact get different values each time (unless perl has been built with -DUSE_HASH_SEED_EXPLICIT — see perlrun):

    $ PERL_HASH_SEED_DEBUG=1 perl -e1 HASH_SEED = 12018612040932336001 $ PERL_HASH_SEED_DEBUG=1 perl -e1 HASH_SEED = 4459772231957961225 ...

    That being said, I still always do get the same ordering every time I do keys %hash ...   So, I'd be interested in an explanation just as much you seem to be :)

    Update:  here's some test code:

    #!/usr/bin/perl use Test::More; plan tests => 1; my %hash = ( "Zero","0","One","1","Two","2", "Three", "3", "Four", "4", "Five", "5", "Six", "6", ); print "$ENV{PERL_INVOCATION_COUNT}: "; # note: test string has been determined experimentally # (i.e. it might differ with your Perl) ok(join(' ', keys %hash) eq 'Five Four Three Zero Two Six One', q{same + ordering}); if (++$ENV{PERL_INVOCATION_COUNT} < 100 ) { exec $0; }

    (prints 100 times "ok ..." with my Perl — despite different hash seed values)

Re: Deterministic or keys in random order
by reasonablekeith (Deacon) on May 14, 2008 at 14:39 UTC
    Just to be explict. You do realise that the fact Zero is returned as the first key has nothing to do with the order of insertion?

    All of these print "Zero" on my build of perl (5.8.7)

    my %hash = ( "Zero" =>"0", "One" => "1", "Two" => "2", ); my @array = keys %hash; print $array[0] . "\n"; -------------------------- my %hash = ( "One" => "1", "Zero" =>"0", "Two" => "2", ); my @array = keys %hash; print $array[0] . "\n"; -------------------------- my %hash = ( "Two" => "2", "One" => "1", "Zero" =>"0", ); my @array = keys %hash; print $array[0] . "\n";
    As a Perl programmer you should never write code which relies on the order returned by keys/each (apart from it being the same as the list time you checked, if you’ve not updated the array).
    ---
    my name's not Keith, and I'm not reasonable.
      As a Perl programmer you should never write code which relies on the order returned by keys/each.
      That's exactly why I think this particular exam question is flawed.
      --
      No matter how great and destructive your problems may seem now, remember, you've probably only seen the tip of them. [1]
Re: Deterministic or keys in random order
by Hue-Bond (Priest) on May 14, 2008 at 14:13 UTC

    Check this thread out for a couple of deep explanations.

    --
    David Serrano

Re: Deterministic or keys in random order
by moritz (Cardinal) on May 14, 2008 at 13:44 UTC
    It's random in the sense the ordering is arbitrary, and that you shouldn't rely on any particular ordering.

    If perl detects that a program has unusually many hash collisions it might change the hash functions, and thus the ordering. (I don't know if perl actually does that, but it's certainly allowed to do so).

Re: Deterministic or keys in random order
by mscharrer (Hermit) on May 14, 2008 at 14:26 UTC
    The above posts give good explanations already, I just like to add the following:
    For the above given hash I get the following constant order of keys:

    Zero Two One

    I think the reason for your "constant"/"deterministic" behavior is that your test hash is very very small so that there aren't much different ways to order the keys. It's just by chance that the first given key is the first returned. As soon you have more keys a different key is the first returned.

      ... As soon you have more keys a different key is the first returned.

      don't think so (tried it with quite a number of keys — for each set of keys, the pseudorandom order obtained is replicably the same)...  But demerphq seems to have the explanation (in the thread already referenced above).

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://686505]
Approved by almut
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (3)
As of 2022-09-25 12:13 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I prefer my indexes to start at:




    Results (116 votes). Check out past polls.

    Notices?