bag.util.search

This module provides search related utilities.

Module Contents

Classes

BinaryIterator	A class that performs binary search over integers.
BinaryIteratorInterval	A class that performs binary search over integers, and respects intervals
FloatBinaryIterator	A class that performs binary search over floating point numbers.
FloatIntervalSearchHelper
FloatIntervalSearch

Functions

_contains(→ bool)	Returns true if test_name is in any container.
get_new_name(→ str)	Generate a new unique name.
minimize_cost_binary(→ MinCostResult)	Minimize cost given minimum output constraint using binary search.
minimize_cost_golden(→ MinCostResult)	Minimize cost given minimum output constraint using golden section/binary search.
minimize_cost_binary_float(→ MinCostResult)	Minimize cost given minimum output constraint using binary search.
minimize_cost_golden_float(→ MinCostResult)	Minimize cost given minimum output constraint using golden section/binary search.
_non_increasing(slist)
_non_decreasing(slist)
_check_monotonicity(...)

Attributes

MinCostResult

bag.util.search.MinCostResult

class bag.util.search.BinaryIterator(low: int, high: Optional[int] = None, step: int = 1, search_step: int = 1)

A class that performs binary search over integers.

This class supports both bounded or unbounded binary search, and you can also specify a step size.

Parameters:

• low (int) – the lower bound (inclusive).

• high (Optional[int]) – the upper bound (exclusive). None for unbounded binary search.

• step (int) – the step size. All return values will be low + N * step

• search_step (int) – the unbounded binary search step size, in units of step. This is only used when trying to find the upper bound.

set_current(val: int) → None

Set the value of the current marker.

has_next() → bool

returns True if this iterator is not finished yet.

get_next() → int

Returns the next value to look at.

get_current() → int

Returns the current value

up(val: Optional[float] = None) → None

Increment this iterator.

down(val: Optional[float] = None) → None

Decrement this iterator.

save() → None

Save the current index.

save_info(info: Any) → None

Save current information.

get_last_save() → Optional[int]

Returns the last saved index.

get_last_save_info() → Any

Return last save information.

class bag.util.search.BinaryIteratorInterval(interval_list, low: int, high: Optional[int] = None, step: int = 1, search_step: int = 1, even: bool = False)

A class that performs binary search over integers, and respects intervals

This class supports both bounded or unbounded binary search, and you can also specify a step size.

Parameters:

• low (int) – the lower bound (inclusive).

• high (Optional[int]) – the upper bound (exclusive). None for unbounded binary search.

• step (int) – the step size. All return values will be low + N * step

• search_step (int) – the unbounded binary search step size, in units of step. This is only used when trying to find the upper bound.

set_current(val: int) → None

Set the value of the current marker.

has_next() → bool

returns True if this iterator is not finished yet.

get_next() → int

Returns the next value to look at.

up(val: Optional[float] = None) → None

Increment this iterator.

down(val: Optional[float] = None) → None

Decrement this iterator.

save() → None

Save the current index.

save_info(info: Any) → None

Save current information.

get_last_save() → Optional[int]

Returns the last saved index.

get_last_save_info() → Any

Return last save information.

class bag.util.search.FloatBinaryIterator(low: float, high: Optional[float] = None, tol: float = 1.0, search_step: float = 1.0, max_err: float = float('inf'))

A class that performs binary search over floating point numbers.

This class supports both bounded or unbounded binary search, and terminates when we can guarantee the given error tolerance.

Parameters:

• low (float) – the lower bound.

• high (Optional[float]) – the upper bound. None for unbounded binary search.

• tol (float) – we will guarantee that the final solution will be within this tolerance.

• search_step (float) – for unbounded binary search, this is the initial step size when searching for upper bound.

• max_err (float) – If unbounded binary search reached this value before finding an upper bound, raise an error.

property low: float

property high: float

has_next() → bool

returns True if this iterator is not finished yet.

get_next() → float

Returns the next value to look at.

up(val: Optional[float] = None) → None

Increment this iterator.

down(val: Optional[float] = None) → None

Decrement this iterator.

save() → None

Save the current index

save_info(info: Any) → None

Save current information.

get_last_save() → Optional[float]

Returns the last saved index.

get_last_save_info() → Any

Return last save information.

class bag.util.search.FloatIntervalSearchHelper(overhead_factor: float)

property num_unbound: int

get_num_points(size: float) → int

_find_soln(size: int) → Tuple[float, int]

class bag.util.search.FloatIntervalSearch(low: float, high: Optional[float] = None, overhead_factor: float = 1, tol: float = 1.0, search_step: float = 1.0, max_err: float = float('inf'), guess: Optional[Union[float, Tuple[float, float]]] = None)

property low: float

property high: float

_helper_table: Dict[float, FloatIntervalSearchHelper]

has_next() → bool

returns True if this iterator is not finished yet.

get_sweep_specs() → Dict[str, Any]

get_value() → float

set_interval(low: float, high: Optional[float] = float('inf'), xy_vals: Optional[Iterable[Tuple[float, float]]] = None) → None

bag.util.search._contains(test_name: str, container_list: Iterable[Container[str]]) → bool

Returns true if test_name is in any container.

bag.util.search.get_new_name(base_name: str, *args: Container[str]) → str

Generate a new unique name.

This method appends an index to the given basename. Binary search is used to achieve logarithmic run time.

Parameters:

• base_name (str) – the base name.

• *args (Container[str]) – a list of containers of used names.

Returns:

new_name – the unique name.

Return type:

str

bag.util.search.minimize_cost_binary(f: Callable[[int], float], vmin: float, start: int = 0, stop: Optional[int] = None, step: int = 1, save: Optional[int] = None, nfev: int = 0) → MinCostResult

Minimize cost given minimum output constraint using binary search.

Given discrete function f, find the minimum integer x such that f(x) >= vmin using binary search.

This algorithm only works if f is monotonically increasing, or if f monontonically increases then monontonically decreases, but stop is given and f(stop) >= vmin.

Parameters:

• f (Callable[[int], float]) – a function that takes a single integer and output a scalar value. Must monotonically increase then monotonically decrease.

• vmin (float) – the minimum output value.

• start (int) – the input lower bound.

• stop (Optional[int]) – the input upper bound. Use None for unbounded binary search.

• step (int) – the input step. function will only be evaulated at the points start + step * N

• save (Optional[int]) – If not none, this value will be returned if no solution is found.

• nfev (int) – number of function calls already made.

Returns:

result – the MinCostResult named tuple, with attributes:

xOptional[int]

the minimum integer such that f(x) >= vmin. If no such x exists, this will be None.

nfevint

total number of function calls made.

Return type:

MinCostResult

bag.util.search.minimize_cost_golden(f: Callable[[int], float], vmin: float, offset: int = 0, step: int = 1, maxiter: Optional[int] = 1000) → MinCostResult

Minimize cost given minimum output constraint using golden section/binary search.

Given discrete function f that monotonically increases then monotonically decreases, find the minimum integer x such that f(x) >= vmin.

This method uses Fibonacci search to find the upper bound of x. If the upper bound is found, a binary search is performed in the interval to find the solution. If vmin is close to the maximum of f, a golden section search is performed to attempt to find x.

Parameters:

• f (Callable[[int], float]) – a function that takes a single integer and output a scalar value. Must monotonically increase then monotonically decrease.

• vmin (float) – the minimum output value.

• offset (int) – the input lower bound. We will for x in the range [offset, infinity).

• step (int) – the input step. function will only be evaulated at the points offset + step * N

• maxiter (Optional[int]) – maximum number of iterations to perform. If None, will run indefinitely.

Returns:

result – the MinCostResult named tuple, with attributes:

xOptional[int]

the minimum integer such that f(x) >= vmin. If no such x exists, this will be None.

xmaxOptional[int]

the value at which f achieves its maximum. This is set only if x is None

vmaxOptional[float]

the maximum value of f. This is set only if x is None.

nfevint

total number of function calls made.

Return type:

MinCostResult

bag.util.search.minimize_cost_binary_float(f: Callable[[float], float], vmin: float, start: float, stop: float, tol: float = 1e-08, save: Optional[float] = None, nfev: int = 0) → MinCostResult

Minimize cost given minimum output constraint using binary search.

Given discrete function f and an interval, find minimum input x such that f(x) >= vmin using binary search.

This algorithm only works if f is monotonically increasing, or if f monontonically increases then monontonically decreases, and f(stop) >= vmin.

Parameters:

• f (Callable[[int], float]) – a function that takes a single integer and output a scalar value. Must monotonically increase then monotonically decrease.

• vmin (float) – the minimum output value.

• start (float) – the input lower bound.

• stop (float) – the input upper bound.

• tol (float) – output tolerance.

• save (Optional[float]) – If not none, this value will be returned if no solution is found.

• nfev (int) – number of function calls already made.

Returns:

result – the MinCostResult named tuple, with attributes:

xOptional[float]

the minimum x such that f(x) >= vmin. If no such x exists, this will be None.

nfevint

total number of function calls made.

Return type:

MinCostResult

bag.util.search.minimize_cost_golden_float(f: Callable[[float], float], vmin: float, start: float, stop: float, tol: float = 1e-08, maxiter: int = 1000) → MinCostResult

Minimize cost given minimum output constraint using golden section/binary search.

Given discrete function f that monotonically increases then monotonically decreases, find the minimum integer x such that f(x) >= vmin.

This method uses Fibonacci search to find the upper bound of x. If the upper bound is found, a binary search is performed in the interval to find the solution. If vmin is close to the maximum of f, a golden section search is performed to attempt to find x.

Parameters:

• f (Callable[[int], float]) – a function that takes a single integer and output a scalar value. Must monotonically increase then monotonically decrease.

• vmin (float) – the minimum output value.

• start (float) – the input lower bound.

• stop (float) – the input upper bound.

• tol (float) – the solution tolerance.

• maxiter (int) – maximum number of iterations to perform.

Returns:

result – the MinCostResult named tuple, with attributes:

xOptional[int]

the minimum integer such that f(x) >= vmin. If no such x exists, this will be None.

xmaxOptional[int]

the value at which f achieves its maximum. This is set only if x is None

vmaxOptional[float]

the maximum value of f. This is set only if x is None.

nfevint

total number of function calls made.

Return type:

MinCostResult

bag.util.search._non_increasing(slist)

bag.util.search._non_decreasing(slist)

bag.util.search._check_monotonicity(slist: sortedcontainers.SortedList, sort_dir: str, x: Union[float, int], y: float) → Tuple[sortedcontainers.SortedList, str]