Re: H of A optimization

I would create a HoH in addition to the HoA and replace that double nested foreach loop:


next if exists $edgeHoH{$a}{$b};

$edgeHoH{$a}{$b} = undef;
[download]

Then you can get rid of the whole 'if $good' if/else statement, and just push unconditionally (and there was no difference in your 'if' and 'else' actions anyway).

Update: Oops, misread another question. But now it seems like you just need a simple hash to store the b's, and skip if you've already seen it.

Comment on Re: H of A optimization Download Code

Replies are listed 'Best First'.
Re: Re: H of A optimization by ferrency (Deacon) on Aug 30, 2002 at 20:36 UTC
I think abitkin wants to make sure that $b isn't in any of the lists in %edgeHash, not to make sure that this specific edge didn't already exist. I think a better answer is: `next if $already_seen{$b}++;` [download] If the values are $b are densely packed small positive integers, an array may be a better choice of data structures for `already_seen` The new code: `my %edgeHash; my %countHash; my %already_seen; while(<stdin>){ # Reading an edge list if(/^\s([0-9]+)\s+([0-9]+)\S$/){ my $a = "$1"; my $b = "$2"; # Eliminate loops next if $already_seen{$b}; push @{$edgeHash{$a}}, $b; } }` [download] I hope this helps. Alan	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re: Re: H of A optimization
by ferrency (Deacon) on Aug 30, 2002 at 20:36 UTC

abitkin

I think a better answer is:

next if $already_seen{$b}++;
[download]

already_seen

The new code:


my %edgeHash;
my %countHash;
my %already_seen;
while(<stdin>){

    # Reading an edge list
    if(/^\s*([0-9]+)\s+([0-9]+)\S*$/){
        my $a = "$1";
        my $b = "$2";

        # Eliminate loops
        next if $already_seen{$b};

        push @{$edgeHash{$a}}, $b;
    }
}
[download]

Alan

[reply]
[d/l]
[select]