The Computer Language
Benchmarks Game

binary-trees Perl program

source code

# The Computer Language Benchmarks Game
# http://benchmarksgame.alioth.debian.org/
# 
# contributed by Emanuele Zeppieri

sub bottomup_tree {
    my ($value, $depth) = @_;
    return $value unless $depth;
    my $value2 = $value * 2; $depth--;
    [ bottomup_tree($value2-1, $depth), bottomup_tree($value2, $depth), $value ]
}

sub check_tree {
    my ($left, $right, $value) = @{ $_[0] };
    $value + (
        ref $left ? check_tree($left) - check_tree($right) : $left - $right
    )
}

my $max_depth = shift @ARGV;
my $min_depth = 4;

$max_depth = $min_depth + 2 if $min_depth + 2 > $max_depth;

my $stretch_depth = $max_depth + 1;
my $stretch_tree = bottomup_tree(0, $stretch_depth);
print "stretch tree of depth $stretch_depth\t check: ",
    check_tree($stretch_tree), "\n";
undef $stretch_tree;

my $longlived_tree = bottomup_tree(0, $max_depth);

for ( my $depth = $min_depth; $depth <= $max_depth; $depth += 2 ) {
    my $iterations = 2 << $max_depth - $depth + $min_depth - 1;
    my $check = 0;
    
    foreach (1..$iterations) {
        $check += check_tree( bottomup_tree(0, $depth) );
        $check += check_tree( bottomup_tree(0, $depth) )
    }
    
    print 2*$iterations, "\t trees of depth $depth\t check: ", $check, "\n"
}

print "long lived tree of depth $max_depth\t check: ",
    check_tree($longlived_tree), "\n"
    

notes, command-line, and program output

NOTES:
32-bit Ubuntu one core
This is perl 5, version 20, subversion 2 (v5.20.2) built for i686-linux
Compile-time options: HAS_TIMES PERLIO_LAYERS PERL_DONT_CREATE_GVSV
                        PERL_HASH_FUNC_ONE_AT_A_TIME_HARD PERL_MALLOC_WRAP
                        PERL_NEW_COPY_ON_WRITE PERL_PRESERVE_IVUV
                        USE_LARGE_FILES USE_LOCALE USE_LOCALE_COLLATE
                        USE_LOCALE_CTYPE USE_LOCALE_NUMERIC USE_PERLIO
                        USE_PERL_ATOF


Sun, 15 Mar 2015 12:18:58 GMT

COMMAND LINE:
/usr/local/src/perl-5.20.2_no_ithreads_no_multi/bin/perl binarytrees.perl 20

PROGRAM OUTPUT:
stretch tree of depth 21	 check: -1
2097152	 trees of depth 4	 check: -2097152
524288	 trees of depth 6	 check: -524288
131072	 trees of depth 8	 check: -131072
32768	 trees of depth 10	 check: -32768
8192	 trees of depth 12	 check: -8192
2048	 trees of depth 14	 check: -2048
512	 trees of depth 16	 check: -512
128	 trees of depth 18	 check: -128
32	 trees of depth 20	 check: -32
long lived tree of depth 20	 check: -1