Function estimateListDistinct

ext/lists.go:759–781

Compute an O(n^2) with a cost factor of 2, equivalent to sets.contains with a result list which can vary in size from 1 element to the original list size.

(estimator checker.CostEstimator, target *checker.AstNode, args []checker.AstNode)

// Compute an O(n^2) with a cost factor of 2, equivalent to sets.contains with a result list
// which can vary in size from 1 element to the original list size.
func estimateListDistinct(estimator checker.CostEstimator, target *checker.AstNode, args []checker.AstNode) *checker.CallEstimate {
	if target == nil || len(args) != 0 {
		return nil
	}
	sz := estimateSize(estimator, *target)
	elemType := types.DynType
	tType := (*target).Type()
	if tType.Kind() == types.ListKind && len(tType.Parameters()) > 0 {
		elemType = tType.Parameters()[0]
	}
	itemSize := estimateItemSize(estimator, *target)
	elemCost := estimateElementEqualityCost(estimator, elemType, itemSize)

	costSize := sz.Multiply(sz)
	cost := costSize.MultiplyByCost(elemCost).MultiplyByCostFactor(2.0)

	minSize := uint64(0)
	if sz.Min > 0 {
		minSize = 1
	}
	resultSize := checker.SizeEstimate{Min: minSize, Max: sz.Max}
	return estimateListCallWithDirectCost(cost, resultSize, true)
}

// estimateListSort computes an O(n^2) sort operation with a cost factor of 2 for the equality
// operations against the elements in the list against themselves which occur during the sort computation.