cockroach: github.com/cockroachdb/cockroach/pkg/util/search Index | Files

package search

import "github.com/cockroachdb/cockroach/pkg/util/search"

Index

Package Files

search.go

type Predicate Uses

type Predicate func(int) (bool, error)

A Predicate is a funcation that returns whether a given search value "passes" or not. It assumes that that within the search domain of [min, max) provided to a Searcher, f(i) == true implies f(i-1) == true and f(i) == false implies f(i+1) == false. A Predicate can be called multiple times, so it should be a pure function.

type Searcher Uses

type Searcher interface {
    // Search runs the predicate function multiple times while searching for the
    // largest value that passes the provided predicate function. It is only
    // valid to call Search once for a given Searcher instance.
    Search(pred Predicate) (res int, err error)
    // contains filtered or unexported methods
}

A Searcher searches to find the largest value that passes a given predicate function.

func NewBinarySearcher Uses

func NewBinarySearcher(min, max, prec int) Searcher

NewBinarySearcher returns a Searcher implementing a binary search strategy. Running the search predicate at min is assumed to pass and running the predicate at max is assumed to fail.

While searching, it will result in a worst case and average case of O(log n) calls to the predicate function.

func NewLineSearcher Uses

func NewLineSearcher(min, max, start, stepSize, prec int) Searcher

NewLineSearcher returns a Searcher implementing a line search strategy with an adaptive step size. Running the search predicate at min is assumed to pass and running the predicate at max is assumed to fail. The strategy will begin searching at the provided start index and with the specified step size.

While searching, it will result in a worst case of O(log n) calls to the predicate function. However, the average efficiency is dependent on the distance between the starting value and the desired value. If the initial guess is fairly accurate, the search strategy is expected to perform better (i.e. result in fewer steps) than performing a binary search with no a priori knowledge.

Package search imports 1 packages (graph) and is imported by 1 packages. Updated 2019-07-21. Refresh now. Tools for package owners.