Logo

NAG and Python

Return to Front

Contents:

  • Welcome
  • Changelog
  • Package Documentation
    • Package Summary
    • Subpackage Summary
    • Attributes
    • Algorithmic Contents
    • Interface Features
    • Documentation Structure
    • Performance Tips
    • Thread Safety Considerations
    • Porting to other NAG Libraries
    • Migrating from Earlier Releases of the NAG Library for Python
    • Numbering Scheme
    • Subpackages
      • library Subpackage
        • Package Summary
        • Subpackage Summary
        • Submodule Summary
        • Functionality Notes
        • Raises
        • Submodules
          • library.anova Submodule
          • library.blas Submodule
          • library.blast Submodule
          • library.blgm Submodule
          • library.complex Submodule
          • library.contab Submodule
          • library.correg Submodule
          • library.det Submodule
          • library.dot Submodule
          • library.eigen Submodule
          • library.fit Submodule
          • library.glopt Submodule
          • library.ieee Submodule
          • library.info Submodule
          • library.inteq Submodule
          • library.interp Submodule
          • library.lapackeig Submodule
          • library.lapacklin Submodule
          • library.linsys Submodule
          • library.machine Submodule
          • library.math Submodule
          • library.matop Submodule
          • library.mesh Submodule
          • library.mip Submodule
          • library.mv Submodule
          • library.nonpar Submodule
          • library.numdiff Submodule
          • library.ode Submodule
          • library.omp Submodule
          • library.opt Submodule
          • library.orthog Submodule
          • library.pde Submodule
          • library.quad Submodule
          • library.rand Submodule
          • library.rnla Submodule
          • library.roots Submodule
          • library.smooth Submodule
          • library.sort Submodule
          • library.sparseig Submodule
          • library.sparse Submodule
          • library.specfun Submodule
          • library.stat Submodule
          • library.sum Submodule
          • library.surviv Submodule
          • library.tsa Submodule
          • library.univar Submodule
          • library.wav Submodule
          • library.zeros Submodule
        • Subpackages
      • kusari Submodule
      • base Subpackage
  • Known Issues
  • Supplementary Info
  • Technical Support
  • Copyright
  • Terms and Conditions

Quick search

naginterfaces.library.sort.realvec_​vec_​search¶

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

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 (n)

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 (m)

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 (m)

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 element ⟨value⟩> element ⟨value⟩.

(errno 3)

On entry, m1=⟨value⟩.

Constraint: m1≥0.

(errno 4)

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

Constraint: m1≤m2≤n.

(errno 5)

On entry, n=⟨value⟩.

Constraint: n≥2.

(errno 6)

On entry, m=⟨value⟩.

Constraint: m≥1.

(errno 7)

On entry, the values in rv are such that the required value of 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, Xi<Xi+1, i=1…(n−1), for the elements of an unordered array of m float numbers, Z. If a value equal to a sought-after item Zi is not found in X, the index of the immediate lower value is returned. If Zi is less than X1, −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

© The Numerical Algorithms Group Limited, 2017-2023. | Powered by Sphinx 4.4.0 & Alabaster 0.7.12 | Page source