Profile of /homes/dcw/src/perl/weeklychallenge/perlweeklychallenge-club/challenge-025/duncan-c-white/perl5/ch-1.pl

Filename	/homes/dcw/src/perl/weeklychallenge/perlweeklychallenge-club/challenge-025/duncan-c-white/perl5/ch-1.pl
Statements	Executed 55702783 statements in 28.8s

Subroutines
Calls	P	F	Exclusive Time	Inclusive Time	Subroutine
5016078	2	1	27.8s	28.8s	main::::findseq main::findseq (recurses: max depth 22, inclusive time 401s)
5016148	2	1	986ms	986ms	main::::CORE:match main::CORE:match (opcode)
1	1	1	4.24ms	4.26ms	main::::BEGIN@22 main::BEGIN@22
1	1	1	3.15ms	13.5ms	main::::BEGIN@23 main::BEGIN@23
1	1	1	880µs	958µs	main::::BEGIN@21 main::BEGIN@21
1	1	1	33µs	33µs	main::::BEGIN@20 main::BEGIN@20
1	1	1	16µs	16µs	main::::CORE:print main::CORE:print (opcode)
1	1	1	13µs	13µs	UNIVERSAL::::VERSIONUNIVERSAL::VERSION (xsub)
0	0	0	0s	0s	main::::RUNTIME main::RUNTIME

Call graph for these subroutines as a Graphviz dot language file.

Line	State ments	Time on line	Calls	Time in subs	Code
1					#!/usr/bin/perl
2					#
3					# Challenge 1: "Generate a longest sequence of the following "English Pokemon"
4					# names where each name starts with the last letter of the previous name:
5					#
6					# audino bagon baltoy banette bidoof braviary bronzor carracosta
7					# charmeleon cresselia croagunk darmanitan deino emboar emolga
8					# exeggcute gabite girafarig gulpin haxorus heatmor heatran ivysaur
9					# jellicent jumpluff kangaskhan kricketune landorus ledyba loudred
10					# lumineon lunatone machamp magnezone mamoswine nosepass petilil
11					# pidgeotto pikachu pinsir poliwrath poochyena porygon2 porygonz
12					# registeel relicanth remoraid rufflet sableye scolipede scrafty
13					# seaking sealeo silcoon simisear snivy snorlax spoink starly
14					# tirtouga trapinch treecko tyrogue vigoroth vulpix wailord
15					# wartortle whismur wingull yamask"
16					#
17					# My notes: Clearly defined, nice, potentially tricky, let's do it.
18					#
19
20	2	110µs	1	33µs	# spent 33µs within main::BEGIN@20 which was called: # once (33µs+0s) by main::NULL at line 20 use v5.10; # to get "say" # spent 33µs making 1 call to main::BEGIN@20
21	2	563µs	2	966µs	# spent 958µs (880+78) within main::BEGIN@21 which was called: # once (880µs+78µs) by main::NULL at line 21 use strict; # spent 958µs making 1 call to main::BEGIN@21 # spent 7µs making 1 call to strict::import
22	2	4.05ms	2	4.28ms	# spent 4.26ms (4.24+19µs) within main::BEGIN@22 which was called: # once (4.24ms+19µs) by main::NULL at line 22 use warnings; # spent 4.26ms making 1 call to main::BEGIN@22 # spent 13µs making 1 call to warnings::import
23	2	559µs	2	13.8ms	# spent 13.5ms (3.15+10.4) within main::BEGIN@23 which was called: # once (3.15ms+10.4ms) by main::NULL at line 23 use Function::Parameters; # spent 13.5ms making 1 call to main::BEGIN@23 # spent 274µs making 1 call to Function::Parameters::import
24					#use Data::Dumper;
25
26	1	2µs			my $debug = @ARGV>0;
27
28	1	7µs			my @words = qw(audino bagon baltoy banette bidoof braviary bronzor carracosta
29					charmeleon cresselia croagunk darmanitan deino emboar emolga
30					exeggcute gabite girafarig gulpin haxorus heatmor heatran ivysaur
31					jellicent jumpluff kangaskhan kricketune landorus ledyba loudred
32					lumineon lunatone machamp magnezone mamoswine nosepass petilil
33					pidgeotto pikachu pinsir poliwrath poochyena porygon2 porygonz
34					registeel relicanth remoraid rufflet sableye scolipede scrafty
35					seaking sealeo silcoon simisear snivy snorlax spoink starly
36					tirtouga trapinch treecko tyrogue vigoroth vulpix wailord
37					wartortle whismur wingull yamask);
38					#@words = qw(hello ollie excellent thanks shelter runaround set to);
39
40	1	200ns			my %sw; # hash from letter to list of words starting with that letter.
41
42	1	800ns			foreach my $word (@words)
43					{
44	70	135µs	70	42µs	$word =~ /^(.)/; # spent 42µs making 70 calls to main::CORE:match, avg 599ns/call
45	70	39µs			my $letter = $1;
46	70	28µs			$sw{$letter} //= [];
47	70	50µs			push @{$sw{$letter}}, $word;
48					}
49
50					#die Dumper \%sw;
51
52	1	600ns			my @longseq = (); # longest sequence found so far..
53
54					# ok, start searching..
55	1	600ns			foreach my $sw (@words)
56					{
57	70	100µs	70	28.8s	findseq( $sw, {}, () ); # spent 28.8s making 70 calls to main::findseq, avg 412ms/call
58					}
59
60	1	100ns			my $longest = @longseq;
61
62	1	23µs	1	16µs	print "\nlongest sequence is length $longest: @longseq\n"; # spent 16µs making 1 call to main::CORE:print
63	1	0s			exit 0;
64
65
66					#
67					# findseq( $currw, $used, @seq );
68					# Find all sequences of words from $currw onwards,
69					# given that we've already visited words in @seq,
70					# (the same info, as a set, is in %$used)
71					# and update the global @longseq if any sequences
72					# we find are longer than that.
73					#
74					# spent 28.8s (27.8+986ms) within main::findseq which was called 5016078 times, avg 6µs/call: # 5016008 times (27.8s+-27.8s) by main::findseq at line 90, avg 0s/call # 70 times (316µs+28.8s) by main::RUNTIME at line 57, avg 412ms/call fun findseq( $currw, $used, @seq )
75	10032156	2.83s			{
76	5016078	503ms			push @seq, $currw; # extend @seq sequence
77
78	5016078	6.16s			my %used = %$used;
79	5016078	735ms			$used{$currw}++;
80
81	5016078	6.19s	5016078	986ms	$currw =~ /(.)$/; # find the last letter of currw # spent 986ms making 5016078 calls to main::CORE:match, avg 197ns/call
82	5016078	581ms			my $lastletter = $1;
83
84	5016078	519ms			my $nextw = $sw{$lastletter}; # words starting with lastletter
85	5016078	7.95s			if( defined $nextw ) # continue searching
86					{
87					foreach my $nextword (@$nextw)
88					{
89					findseq( $nextword, \%used, @seq )
90	7864514	3.12s	5016008	0s	unless $used{$nextword}; # spent 401s making 5016008 calls to main::findseq, avg 80µs/call, recursion: max depth 22, sum of overlapping time 401s
91					}
92					} else # @seq is finished
93					{
94					#print "found sequence @seq\n";
95	1346584	114ms			my $len = @seq;
96	1346584	113ms			if( $len > @longseq )
97					{
98	16	2µs			print "seq len $len, @seq\n" if $debug;
99	16	21µs			@longseq = @seq;
100					}
101					}
102	1	86µs	1	10µs	} # spent 10µs making 1 call to Function::Parameters::_register_info

					# spent 13µs within UNIVERSAL::VERSION which was called: # once (13µs+0s) by Function::Parameters::BEGIN@7 at line 24 of Scalar/Util.pm sub UNIVERSAL::VERSION; # xsub
					# spent 986ms within main::CORE:match which was called 5016148 times, avg 197ns/call: # 5016078 times (986ms+0s) by main::findseq at line 81, avg 197ns/call # 70 times (42µs+0s) by main::RUNTIME at line 44, avg 599ns/call sub main::CORE:match; # opcode
					# spent 16µs within main::CORE:print which was called: # once (16µs+0s) by main::RUNTIME at line 62 sub main::CORE:print; # opcode