in reply to Re^2: An iterator for (not "iterating") a recursive data structure. (terser)
in thread An iterator for (not "iterating") a recursive data structure.

I'm wondering if this could also be done with nested hashes.

A stored array index has a natural successor, but a hash key hasn't.°

Using each is accessing an internal iterator "cursor", but can't be used multiple times with the same hash.

The only solution which comes to mind is to initially cache the keys into an array and to go by index. But this static copy defies the idea of a dynamic iterator.

Any better idea?

update

Tie::Hash requires us to implement a NEXTKEY this, lastkey method. But there doesn't seem to be a way to access this API with a native hash.

update

Is (keys %hash)[$idx++] optimized to be performant, or will it create a long list of keys to be thrown away?

Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery

°) well there is an internal order but this is a) kept secret and b) shuffled with every new run of perl

  • Comment on Re^3: An iterator for (not "iterating") a recursive data structure. (index into keys?)
  • Select or Download Code

Replies are listed 'Best First'.
Re^4: An iterator for (not "iterating") a recursive data structure. (updated x 2)
by LanX (Saint) on Jun 19, 2020 at 00:32 UTC

    UPDATE: Please don't trust the benchmark, turns out, that when operating on the same hash they are sabotaging each other*

    > Is (keys %hash)[$idx++] optimized to be performant, or will it create a long list of keys to be thrown away?

    it's way faster than each !?!

    UPDATE Sorry I misread the results, it's late. :)

    The approach with (keys %hash)[$idx++] is far slower.

    use 5.12.0; use strict; use warnings; use Data::Dump qw/pp dd/; use Benchmark qw/cmpthese/; # --------- fetch all defined generators my %generators; for my $generator ( grep {/^gen_/} keys %Generators::) { my $g_generator = $Generators::{$generator}; $generators{$generator} = $g_generator; } #warn pp \%generators; # --------- init test data my %hash; my @entries = 0..1e3; @hash{@entries} = reverse @entries; my %copy = %hash; # --------- run tests while( my ($gen,$glob) = each %generators ) { say "\n*** Testing $gen"; Tests::all( "$gen", $glob->(\%hash), \%copy ); } Test::More::done_testing(); # --------- run benchmarks # --- expand test data @entries = 0..1e6; @hash{@entries} = reverse @entries; # --- init iterators my %iterators; while ( my ($gen,$glob) = each %generators ) { (my $name = $gen) =~ s/^gen_//; $iterators{$name} = $glob->(\%hash); } #warn pp \%iterators; # --- benchmark cmpthese(-1, \%iterators ); package Generators; sub gen_copy_keys { my ($h_hash) = @_; my $idx = 0; my @keys = keys %$h_hash; return sub { # --- reset? if ($idx >= @keys) { $idx = 0; return; } # --- return key, value my $key = $keys[$idx++]; return $key, $h_hash->{$key}; } } sub gen_copy_hash_and_each { my ($h_hash) = @_; my %copy = %$h_hash; return sub { # --- return key, value return each %copy } } sub gen_each { my ($h_hash) = @_; return sub { # --- return key, value return each %$h_hash; } } sub gen_idx_keys { my ($h_hash) = @_; my $idx = 0; return sub { if ($idx >= keys %$h_hash) { $idx = 0; return; } # --- return key, value my $key = (keys %$h_hash)[$idx++]; return $key, $h_hash->{$key}; } } package Tests; use Test::More; sub all { my ( $name, $c_iter, $h_expected ) = @_; # --- gathers all entries my %got = (); while ( my ($k,$v) = &$c_iter ) { $got{$k} = $v; } is_deeply(\%got, $h_expected, "'$name' iterates over all entries") +; # --- cycles to restart %got = (); while ( my ($k,$v) = &$c_iter ) { $got{$k} = $v; } is_deeply(\%got, $h_expected, "'$name' cycles and iterates again") +; }

    Compilation started at Fri Jun 19 02:17:48 C:/Perl_524/bin\perl.exe d:/exp/hash_iter.pl *** Testing gen_idx_keys ok 1 - 'gen_idx_keys' iterates over all entries ok 2 - 'gen_idx_keys' cycles and iterates again *** Testing gen_copy_hash_and_each ok 3 - 'gen_copy_hash_and_each' iterates over all entries ok 4 - 'gen_copy_hash_and_each' cycles and iterates again *** Testing gen_copy_keys ok 5 - 'gen_copy_keys' iterates over all entries ok 6 - 'gen_copy_keys' cycles and iterates again *** Testing gen_each ok 7 - 'gen_each' iterates over all entries ok 8 - 'gen_each' cycles and iterates again 1..8 Rate idx_keys copy_keys each copy_has +h_and_each idx_keys 3.05/s -- -100% -100% + -100% copy_keys 2361328/s 77510489% -- -6% + -23% each 2522717/s 82808095% 7% -- + -17% copy_hash_and_each 3047966/s 100049391% 29% 21% + -- Compilation finished at Fri Jun 19 02:18:05

    Cheers Rolf
    (addicted to the Perl Programming Language :)
    Wikisyntax for the Monastery