func GetChangePointIndexes()

in pkg/degradation-detector/statistic/changeDetector.go [8:61]
48 lines of code
9 McCabe index (conditional complexity)

func GetChangePointIndexes(data []int, minDistance int) []int {
	n := len(data)
	if n <= 2 {
		return []int{}
	}
	if minDistance < 1 || minDistance > n {
		panic("minDistance should be in range from 1 to len(data)")
	}

	penalty := 3 * math.Log(float64(n))
	k := int(math.Min(float64(n), math.Ceil(4*math.Log(float64(n)))))
	partialSums := getPartialSums(data, k)

	cost := func(tau1, tau2 int) float64 {
		return getSegmentCost(partialSums, tau1, tau2, k, n)
	}

	bestCost := make([]float64, n+1)
	bestCost[0] = -penalty
	for currentTau := minDistance; currentTau < 2*minDistance; currentTau++ {
		bestCost[currentTau] = cost(0, currentTau)
	}

	previousChangePointIndex := make([]int, n+1)
	previousTaus := []int{0, minDistance}
	var costForPreviousTau []float64

	for currentTau := 2 * minDistance; currentTau < n+1; currentTau++ {
		costForPreviousTau = costForPreviousTau[:0]
		for _, previousTau := range previousTaus {
			costForPreviousTau = append(costForPreviousTau, bestCost[previousTau]+cost(previousTau, currentTau)+penalty)
		}
		bestPreviousTauIndex := whichMin(costForPreviousTau)
		bestCost[currentTau] = costForPreviousTau[bestPreviousTauIndex]
		previousChangePointIndex[currentTau] = previousTaus[bestPreviousTauIndex]
		newPreviousTaus := make([]int, 0, len(previousTaus))
		for i, cost2 := range costForPreviousTau {
			if cost2 < bestCost[currentTau]+penalty {
				newPreviousTaus = append(newPreviousTaus, previousTaus[i])
			}
		}
		previousTaus = newPreviousTaus
		previousTaus = append(previousTaus, currentTau-(minDistance-1))
	}

	var changePointIndexes []int
	currentIndex := previousChangePointIndex[n]
	for currentIndex != 0 {
		changePointIndexes = append(changePointIndexes, currentIndex)
		currentIndex = previousChangePointIndex[currentIndex]
	}
	slices.Reverse(changePointIndexes)
	return changePointIndexes
}