Documentation: x2r.io
Python and standalone C++ sources are published in the py and cpp branches
of fastcpd.
Installation: R, Python, and C++
R package:
install.packages("fastcpd")Python package:
python -m pip install fastcpdC++ library (requires Armadillo and Abseil 20260526 or newer):
git clone --branch cpp https://github.com/doccstat/fastcpd.git fastcpd-cpp
cmake -S fastcpd-cpp -B fastcpd-cpp/build -DFASTCPD_BUILD_EXAMPLES=OFF
cmake --build fastcpd-cpp/build --parallel
cmake --install fastcpd-cpp/build --prefix fastcpd-installset.seed(1)
n <- 10^7
mean_data <- c(rnorm(n / 2, 0, 1), rnorm(n / 2, 50, 1))
print(run_isolated(fastcpd::detect_mean(mean_data, cp_only = TRUE, variance_estimation = 1)))
#> user system elapsed
#> 0.733 0.196 0.932
print(run_isolated(mosum::mosum(c(mean_data), G = 40)))
#> user system elapsed
#> 1.217 0.711 1.947
print(run_isolated(changepoint::cpt.mean(mean_data, method = "PELT")))
#> user system elapsed
#> 3.351 0.635 3.987
print(run_isolated(fpop::Fpop(mean_data, 2 * log(n))))
#> user system elapsed
#> 3.977 0.280 4.265
import time
import fastcpd
import numpy as np
import ruptures
import sdt
import sdt.changepoint
import skchange
import skchange.detectors
import skchange.interval_scorers
rng = np.random.default_rng(1)
n = int(1e4)
x = np.r_[rng.normal(0, 1, n // 2), rng.normal(50, 1, n // 2)]
start = time.perf_counter()
fastcpd.detect_mean(x, variance_estimation=1, cp_only=True)
print(f"fastcpd: {time.perf_counter() - start:.3f} s")
start = time.perf_counter()
skchange.detectors.PELT(
cost=skchange.interval_scorers.L2Cost(), penalty=2 * np.log(n), step_size=1
).fit_predict(x.reshape(-1, 1))
print(f"skchange: {time.perf_counter() - start:.3f} s")
start = time.perf_counter()
sdt.changepoint.Pelt(cost="l2", min_size=1, jump=1).find_changepoints(
x, penalty=2 * np.log(n)
)
print(f"sdt-python: {time.perf_counter() - start:.3f} s")
start = time.perf_counter()
ruptures.Pelt(model="l2", min_size=1, jump=1).fit(x).predict(
pen=2 * np.log(n)
)
print(f"ruptures: {time.perf_counter() - start:.3f} s")#> fastcpd: 0.001 s
#> skchange: 1.125 s
#> sdt-python: 50.173 s
#> ruptures: 442.609 s
Native fastcpd and fpop on Linux ARM64, with 1,000,000 observations. Source and build instructions.
