<jupyter_start><jupyter_text>Fréchet distanceThis will compare the performance of calculating the discrete Fréchet distance with the recursive and dynamic programming algorithms.<jupyter_code>import similaritymeasures as sm
import numpy as np
import matplotlib.pyplot as plt
import toleranceinterval as ti
from scipy.spatial import minkowski_distance
from time import time

def dp_frechet_dist(P, Q, pnorm=2):
    """ dynamic programming for discrete frechet distance
    
    by SenZHANG https://github.com/SenZHANG-GitHub
    https://github.com/cjekel/similarity_measures/issues/6#issuecomment-544350039
    """
    n = len(P)
    m = len(Q)
    ca = np.ones((n, m))
    ca = np.multiply(ca, -1)
    ca[0, 0] = minkowski_distance(P[0], Q[0], p=pnorm)
    for i in range(1, n):
        ca[i, 0] = max(ca[i-1, 0], minkowski_distance(P[i], Q[0], p=pnorm))
    for j in range(1, m):
        ca[0, j] = max(ca[0, j-1], minkowski_distance(P[0], Q[j], p=pnorm))
    for i in range(1, n):
        for j in range(1, m):
            ca[i, j] = max(min(ca[i-1, j], ca[i, j-1], ca[i-1, j-1]), minkowski_distance(P[i], Q[j], p=pnorm))
    return ca[n-1, m-1]
def benchmark_frechet(sizes, method, seed):
    np.random.seed(seed)
    n_dim = 5
    n_rep = 100
    times = np.zeros((len(sizes), n_rep))
    for i, size in enumerate(sizes):
        for j in range(n_rep):
            P = np.random.random((size, n_dim))
            Q = np.random.random((size, n_dim))
            t0 = time()
            d = method(P, Q)
            t1 = time()
            times[i, j] = t1 - t0
    return times
sizes = [20, 40, 50, 100, 200, 400, 500, 1000]
# recursion times
times_recursion = benchmark_frechet(sizes, sm.frechet_dist, 123)
# dynamic programming times
times_dp = benchmark_frechet(sizes, dp_frechet_dist, 123)
# compute means of runtimes
times_recursion_mean = times_recursion.mean(axis=1)
times_dp_mean = times_dp.mean(axis=1)

# compute the 99th percntile to 99% confidence
bounds_recursion = ti.twoside.normal(times_recursion, 0.99, 0.99)
bounds_dp = ti.twoside.normal(times_dp, 0.99, 0.99)

# get the - and plus values for error bars
k_sigma_recursion = bounds_recursion[:, 1] - times_recursion_mean
k_sigma_dp = bounds_dp[:, 1] - times_dp_mean

fig = plt.figure()

plt.errorbar(sizes, times_recursion_mean,
             yerr=k_sigma_recursion,
             capsize=2.0,
             label='Recursion')
plt.errorbar(sizes, times_dp_mean,
             yerr=k_sigma_dp,
             capsize=2.0,
             label='Dynamic Programming')

plt.semilogx(True)
plt.semilogy(True)
plt.xlabel(r'size of both $n$ and $m$')
plt.ylabel('Run time, seconds')
plt.legend()

bounds_dp
k_sigma_dp
times_recursion_mean
times_dp_mean
times_recursion_mean/times_dp_mean
import seaborn as sns
sns.set()
sns.distplot(times_recursion[-1])
sns.distplot(times_dp[-1])<jupyter_output><empty_output><jupyter_text>Conclusion**The iterative code was about 1.2 times faster (on average, with 5 dimensions) than the recursive code.** The iterative code also has the benefit of not dealing with recursion limits. I think it's time to replace the recursive code.<jupyter_code>sm.__version__<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12075471698113208, 'fraction_numerical': 0.031132075471698113, 'mean_word_length': 3.643795620437956, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '58173', 'license': 'MIT', 'n_tokens_mistral': 1245, 'n_tokens_neox': 1144, 'n_words': 295, 'path': 'frechet_distance_recursion_vs_dp.ipynb', 'repo_name': 'cjekel/similarity_measures', 'size': '3180'}