Subject: | Performance problem: ord_values() used when non-ordered would suffice |
Date: | Thu, 4 Apr 2019 20:28:26 -0400 |
To: | bug-Graph-Easy [...] rt.cpan.org |
From: | "Tels" <nospam-abuse [...] bloodgate.com> |
Thank you for working on Graph::Easy :)
outgoing() and similiar routines have this snippet:
sub outgoing
{
# return all edges that start at this node
my $self = shift;
# no graph, no dice
return unless ref $self->{graph};
if (!wantarray)
{
my $count = 0;
for my $edge (ord_values ( $self->{edges} ))
{
$count++ if $edge->{from} == $self;
}
return $count;
}
...
The ord_values() here sorts the edges, which is unnec. when all we want is
a count of values. This changes outgoing() from O(N) to O(N log N), which
matters for graphs with many edges/nodes.
The documentation for outgoing()/incoming() could also mention that:
my $count = scalar $node->outgoing();
is faster than getting all outgoing edges and counting them by yourself.
Best regards,
Tels