In [1]:
# Load modules
import sys
from __future__ import print_function
from collections import defaultdict
import helper_functions as hf
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
import time
from pqt import PQTDecomposition
from splice import splice_alg
from asplice import asplice_alg
from plg import plg_alg
In [2]:
def compute_avg_times(n_pairs_li, n_reps, gen_pd_edges, p_hat=0.01, verbose=False):
"""
Parameters:
n_pairs_li - a list of the number of pairs to generate
n_reps - the number of repetitions of experiment with that number of pairs
gen_pd_edges - function the generates n pairs
include_pqt_time - whether or not the time to compute the pqt should be included
verbose - whether or not to print the repetitions to stdout
"""
splice_avg_times = []
plg_avg_times = []
asplice_avg_times = []
pqt_avg_times = []
# Run experiment
for n_pairs in n_pairs_li:
splice_cum_runtime = 0.
asplice_cum_runtime = 0.
plg_cum_runtime = 0.
pqt_cum_runtime = 0.
for rep in xrange(n_reps):
if verbose:
print("Number of pairs: {} Rep: {} at ({})".format(n_pairs,
rep, time.strftime("%H:%M %S", time.gmtime())))
sys.stdout.flush()
# Generate pairs
pd_edges = gen_pd_edges(n_pairs)
# Run SPLICE
start_time = time.clock()
_, cost = splice_alg(pd_edges)
splice_runtime = time.clock() - start_time
splice_cum_runtime += splice_runtime
# Generate PQT
start_time = time.clock()
pqt = PQTDecomposition().from_points(pd_edges.keys(), p_hat=p_hat)
pqt_time = time.clock() - start_time
pqt_cum_runtime += pqt_time
# Run ASPLICE
start_time = time.clock()
_, cost = asplice_alg(pd_edges, pqt=pqt)
asplice_cum_runtime = time.clock() - start_time
# Run PLG
start_time = time.clock()
_, cost = plg_alg(pd_edges, pqt=pqt)
plg_cum_runtime = time.clock() - start_time
splice_avg_times.append(np.mean(splice_cum_runtime))
plg_avg_times.append(np.mean(plg_cum_runtime))
asplice_avg_times.append(np.mean(asplice_cum_runtime))
pqt_avg_times.append(np.mean(pqt_cum_runtime))
return splice_avg_times, plg_avg_times, asplice_avg_times, pqt_avg_times
In [23]:
# Experiment parameters
n_pairs_li = list(xrange(10, 120, 4)) #+ list(xrange(100, 200, 20))
print(n_pairs_li)
p_hat = 0.1
n_reps = 3
gen_pd_edges = hf.gen_pd_edges
In [24]:
splice_avg_times, plg_avg_times, asplice_avg_times, pqt_avg_times = \
compute_avg_times(n_pairs_li, n_reps, gen_pd_edges, p_hat, verbose=True)
In [28]:
fig, ax = plt.subplots()
ax.set_yscale('log')
ax.plot(n_pairs_li, splice_avg_times, color='b', linestyle='-',
label=r"SPLICE")
ax.plot(n_pairs_li, plg_avg_times, color='g', linestyle='-.',
label=r"PLG ($\,\hat{{p}}={}$)".format(p_hat))
ax.plot(n_pairs_li, asplice_avg_times, color='r', linestyle='--',
label=r"ASPLICE ($\,\hat{{p}}={}$)".format(p_hat))
ax.set_xlabel("Number of pd Pairs", fontsize=15)
ax.set_ylabel("Runtime (s)", fontsize=15)
ax.set_title('Algorithm Runtime vs Number of Pairs (excluding PQT)')
ax.legend(loc=2)
ax.grid(True)
fig.tight_layout()
In [29]:
splice_avg_times_inc = np.array(splice_avg_times) + np.array(pqt_avg_times)
asplice_avg_times_inc = np.array(asplice_avg_times) + np.array(pqt_avg_times)
plg_avg_times_inc = np.array(plg_avg_times) + np.array(pqt_avg_times)
In [30]:
fig, ax = plt.subplots()
ax.set_yscale('log')
ax.plot(n_pairs_li, splice_avg_times, color='b', linestyle='-',
label=r"SPLICE")
ax.plot(n_pairs_li, plg_avg_times, color='g', linestyle='-.',
label=r"PLG")
ax.plot(n_pairs_li, asplice_avg_times, color='r', linestyle='--',
label=r"ASPLICE")
ax.plot(n_pairs_li, plg_avg_times_inc, color='g', linestyle='-.',
label=r"PLG inc")
ax.plot(n_pairs_li, asplice_avg_times_inc, color='r', linestyle='--',
label=r"ASPLICE inc")
ax.set_xlabel("Number of pd Pairs", fontsize=15)
ax.set_ylabel("Runtime (s)", fontsize=15)
ax.set_title(r"Algorithm Runtime vs Number of Pairs ($\,\hat{{p}}={}$)".format(p_hat))
ax.legend(loc=2, labelspacing=0)
ax.grid(True)
fig.tight_layout()
In [ ]:
print()
In [ ]:
def compute_avg_costs(n_pairs_li, n_reps, gen_pd_edges, p_hat=0.01, verbose=False):
"""
Parameters:
n_pairs_li - a list of the number of pairs to generate
n_reps - the number of repetitions of experiment with that number of pairs
gen_pd_edges - function the generates n pairs
include_pqt_time - whether or not the time to compute the pqt should be included
verbose - whether or not to print the repetitions to stdout
"""
splice_avg_costs = []
plg_avg_costs = []
asplice_avg_costs = []
pqt_avg_costs = []
# Run experiment
for n_pairs in n_pairs_li:
splice_cum_cost = 0.
asplice_cum_cost = 0.
plg_cum_cost = 0.
for rep in xrange(n_reps):
if verbose:
print("Number of pairs: {} Rep: {} at ({})".format(n_pairs,
rep, time.strftime("%H:%M %S", time.gmtime())))
sys.stdout.flush()
# Generate pairs
pd_edges = gen_pd_edges(n_pairs)
# Run SPLICE
_, cost = splice_alg(pd_edges)
splice_cum_cost += cost
# Generate PQT
pqt = PQTDecomposition().from_points(pd_edges.keys(), p_hat=p_hat)
# Run ASPLICE
_, cost = asplice_alg(pd_edges, pqt=pqt)
asplice_cum_cost += cost
# Run PLG
_, cost = plg_alg(pd_edges, pqt=pqt)
plg_cum_cost += cost
splice_avg_costs.append(np.mean(splice_cum_cost))
plg_avg_costs.append(np.mean(plg_cum_cost))
asplice_avg_costs.append(np.mean(asplice_cum_cost))
return splice_avg_costs, plg_avg_costs, asplice_avg_costs
In [ ]:
splice_avg_costs, plg_avg_costs, asplice_avg_costs = \
compute_avg_costs(n_pairs_li, n_reps, gen_pd_edges, p_hat, verbose=True)
In [ ]:
fig, ax = plt.subplots()
#ax.set_yscale('log')
ax.plot(n_pairs_li, splice_avg_costs, color='b', linestyle='-',
label=r"SPLICE")
ax.plot(n_pairs_li, plg_avg_costs, color='g', linestyle='-.',
label=r"PLG")
ax.plot(n_pairs_li, asplice_avg_costs, color='r', linestyle='--',
label=r"ASPLICE")
ax.set_xlabel("Number of pd Pairs", fontsize=15)
ax.set_ylabel("Runtime (s)", fontsize=15)
ax.set_title(r"Algorithm Cost vs Number of Pairs ($\,\hat{{p}}={}$)".format(p_hat))
ax.legend(loc=2, labelspacing=0)
ax.grid(True)
fig.tight_layout()
In [ ]: