naginterfaces.library.sort.realvec_​vec_​search

naginterfaces.library.sort.realvec_vec_search(valid, rv, m1, m2, item, comm=None)

realvec_vec_search searches a strictly ordered vector of float numbers and returns the indices of the largest numbers in the vector which are smaller than or equal to the sought-after items.

For full information please refer to the NAG Library document for m01nd

https://www.nag.com/numeric/nl/nagdoc_29.2/flhtml/m01/m01ndf.html

Parameters

validbool

If $valid$ is set to $True$ argument checking will be performed. If $valid$ is set to $False$ realvec_vec_search will be called without argument checking (which includes checking that array $rv$ is sorted in strictly ascending order). See Further Comments for further details.

rvfloat, array-like, shape $\left(n\right)$

$X$, the float values to be searched.

m1int

Note: this argument represents an array index; the value you supply must be base-1 for compatibility with the NAG Engine.

The index of the first element of $rv$ to be searched.

m2int

Note: this argument represents an array index; the value you supply must be base-1 for compatibility with the NAG Engine.

The index of the last element of $rv$ to be searched.

itemfloat, array-like, shape $\left(m\right)$

$Z$, the sought-after items.

commNone or dict, communication object, optional, modified in place

Communication structure.

If $comm$ is None then searching is performed using an offset-based binary search.

Otherwise, $comm$ may be supplied uninitialized.

It will then be populated and the routine will perform a direct search of $rv$.

The populated $comm$ can then be supplied again to subsequent calls for repeated searching of $rv$.

Returns

idxint, ndarray, shape $\left(m\right)$

Note: this argument represents array indices; the values returned will be base-1.

$idx[i-1]$ contains the index of the largest entry in $rv$ which is smaller than or equal to $item[i-1]$.

Raises

NagValueError

(errno $2$)

On entry, $rv$ must be sorted in strictly ascending order: $rv\text{element}⟨value⟩>\text{element}⟨value⟩$.

(errno $3$)

On entry, $m1=⟨value⟩$.

Constraint: $m1\ge 0$.

(errno $4$)

On entry, $m1=⟨value⟩$, $m2=⟨value⟩$, $n=⟨value⟩$.

Constraint: $m1\le m2\le n$.

(errno $5$)

On entry, $n=⟨value⟩$.

Constraint: $n\ge 2$.

(errno $6$)

On entry, $m=⟨value⟩$.

Constraint: $m\ge 1$.

(errno $7$)

On entry, the values in $rv$ are such that the required value of $\text{lk}$ would overflow the current platform’s largest positive integer value.

(errno $8$)

$comm$ may have become corrupted.

Notes

realvec_vec_search searches an array, $X$, of $n$ strictly-increasing float numbers, $X_i<X_{i+1}$, $i=1\dots (n-1)$, for the elements of an unordered array of $m$ float numbers, $Z$. If a value equal to a sought-after item $Z_i$ is not found in $X$, the index of the immediate lower value is returned. If $Z_i$ is less than $X_1$, $-1$ is returned.

The function implements the direct search algorithm presented as Algorithm 8 in Cannizzo (2018). It precomputes a scalar, $H$, and a reference vector of indices, $K$, that it uses to speed up searches of $X$. The length of $K$ is a function of the number of entries in $X$ and their values, and the function provides a mechanism to compute what this length should be.

If the amount of memory required for $K$ is infeasible, realvec_vec_search implements offset-based binary search (Algorithm 5 in Cannizzo (2018)) as an alternative that does not require $K$ to be used.

See Further Comments for more information on the relative time complexities of the two search algorithms.

References

Cannizzo, F, 2018, A fast and vectorizable alternative to binary search in O(1) with wide applicability to arrays of floating point numbers, Journal of Parallel and Distributed Computing (113), 37–54