use strict;
use warnings;

use Benchmark qw/timeit :hireswallclock/;

my $num_repeats = 50;

my @bobjs;
my %ahash;
my @anarray;
my @results;
my $linreg;
# map { $_ * 1000 } 10..30 simulates a loop with step of 1000

# Do array inserts
@results = ();
@bobjs = ();
@anarray = ();
for my $num_inserts ( map { $_ * 1000 } 10..30 ){
	# warmup
	do_array_inserts($num_inserts, \@anarray); @anarray = ();
	# time it
	my $abobj = timeit($num_repeats,
		sub { do_array_inserts($num_inserts, \@anarray); @anarray = (); }
	);
	push @bobjs, [$num_inserts, $abobj];
	push @results, [$num_inserts, $abobj->real];
	print $num_inserts." array insertions took ". $abobj->real . " seconds.\n"
}

$linreg = ordinary_least_squares(@results);
print "Array inserts:\n";
print "Y = ".$linreg->{A}." * X + ".$linreg->{B}." with error ".$linreg->{E}."\n";
print "Y : total time to insert X elements.\n";

# Do hash inserts
@results = ();
%ahash = ();
@bobjs = ();
for my $num_inserts ( map { $_ * 1000 } 10..30 ){
	# warmup
	do_hash_inserts($num_inserts, \%ahash); %ahash = ();
	# time it
	my $abobj = timeit($num_repeats,
		sub { do_hash_inserts($num_inserts, \%ahash); %ahash = (); }
	);
	push @bobjs, [$num_inserts, $abobj];
	push @results, [$num_inserts, $abobj->real];
	print $num_inserts." hash insertions took ". $abobj->real . " seconds.\n"
}
$linreg = ordinary_least_squares(@results);
print "Hash inserts:\n";
print "Y = ".$linreg->{A}." * X + ".$linreg->{B}." with error ".$linreg->{E}."\n";
print "Y : total time to insert X elements.\n";

#### end

sub do_hash_inserts {
	my ($repeats, $container) = @_;
	for (1..$repeats){
		$container->{random_key()} = random_value();
	}
}

sub do_array_inserts {
	my ($repeats, $container) = @_;
	for (1..$repeats){
		push @$container, random_value();
	}
}

sub random_key {
	return join '', map { rand } 1..3
}
sub random_value {
	return join '', map { rand } 1..3
}

sub ordinary_least_squares {
	# each element of input array is [num_insertions, time_seconds]
	my @observations = @_;

	# coefficients to find assuming Y = A*X + B
	my ($A, $B);
	my $diff;
	my $num_observations = @observations;
	my $cov = 0.0;
	my $var = 0.0;
	my $meanx = 0.0;
	my $meany = 0.0;
	for my $anobs (@observations){
		my ($x, $y) = @$anobs;
		$meanx += $x;
		$meany += $y;
	}
	$meanx /= $num_observations;
	$meany /= $num_observations;

	for my $anobs (@observations){
		my ($x, $y) = @$anobs;
		my $diffx = ($x - $meanx);
		$cov += $diffx * ($y - $meany);
		$var += $diffx * $diffx;
	}
	$A = $cov / $var;
	$B = $meany - $A * $meanx;

	my $error = 0.0;
	for my $anobs (@observations){
		my ($x, $y) = @$anobs;
		my $ypred = $A * $x + $B;
		$error += ($y - $ypred)**2
	}
	$error = sqrt($error) / $num_observations;
	return { A => $A, B => $B, E => $error }
}