tempo.py

from __future__ import division, print_function

def partial_differences(xs):
	return [x2 - x1 for (x1, x2) in zip(xs, xs[1:])]

def index_of_max(xs):
	return max(enumerate(xs), key=lambda pair: pair[1])[0]

# given a list of floats, compute a tempo and a timestamp
def tempo(xs, max_beats):
	gaps = partial_differences(xs)
	beat_counts = [1] * len(gaps)
	best_tempo = None
	best_error = None

	while True:
		# calculate current error
		derived_tempos = [gap / bc for (gap, bc) in zip(gaps, beat_counts)]
		tempo = sum(derived_tempos) / len(derived_tempos)
		error = sum((dt - tempo)**2 for dt in derived_tempos)

		# check if it's better
		if best_error is None or error < best_error:
			best_tempo = tempo
			best_error = error

		# give one extra beat to the gap with the largest derived tempo
		mi = index_of_max(derived_tempos)
		beat_counts[mi] += 1

		if beat_counts[mi] > max_beats:
			return (best_tempo, best_error)

print(tempo([0, 2, 4, 6, 8], 3))
print(tempo([0, 1, 4, 6, 8], 3))
print(tempo([0, 1.3, 3.7, 4.7, 7.2], 3))