NAG CL Interface
m01ndc (realvec_vec_search)
1
Purpose
m01ndc searches a strictly ordered vector of double numbers and returns the indices of the largest numbers in the vector which are smaller than or equal to the sought-after items.
2
Specification
void |
m01ndc (Nag_Boolean validate,
Integer mode,
const double rv[],
Integer n,
Integer m1,
Integer m2,
const double item[],
Integer m,
Integer idx[],
double *h,
Integer k[],
Integer *lk,
NagError *fail) |
|
The function may be called by the names: m01ndc or nag_sort_realvec_vec_search.
3
Description
m01ndc searches an array, , of strictly-increasing double numbers, , , for the elements of an unordered array of double numbers, . If a value equal to a sought-after item is not found in , the index of the immediate lower value is returned. If is less than , is returned.
The function implements the direct search algorithm presented as Algorithm 8 in
Cannizzo (2018). It precomputes a scalar,
, and a reference vector of indices,
, that it uses to speed up searches of
. The length of
is a function of the number of entries in
and their values, and the function provides a mechanism to compute what this length should be.
If the amount of memory required for
is infeasible,
m01ndc
implements offset-based binary search (Algorithm 5 in
Cannizzo (2018)) as an alternative that does not require
to be used.
See
Section 9 for more information on the relative time complexities of the two search algorithms.
4
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
5
Arguments
-
1:
– Nag_Boolean
Input
-
On entry: if
validate is set to Nag_TRUE argument checking will be performed. If
validate is set to Nag_FALSE
m01ndc will be called without argument checking (which includes checking that array
rv is sorted in strictly ascending order). See
Section 9 for further details.
-
2:
– Integer
Input
-
On entry: a code for selecting the operation to be performed by the function. The first call to
m01ndc must be made with
, and this must be followed by a second call with
. Thereafter repeated searches of
rv can be made through repeated calls with
.
- Compute h and lk. Following a call with , k must be allocated to hold lk elements and then the function must be called again with .
- Set up k (the reference vector) using the values of h and lk returned from a prior call to m01ndc with .
- Direct search using h and k set up in prior calls to m01ndc with or .
- Search using offset-based binary search, which does not require h or k to be used.
Constraint:
, , or .
-
3:
– const double
Input
-
On entry: , the double values to be searched.
Constraint:
elements of
rv must be sorted in strictly ascending order.
-
4:
– Integer
Input
-
On entry: , the number of double values to be searched.
Constraint:
.
-
5:
– Integer
Input
-
On entry: the index of the first element of
rv to be searched.
Constraint:
.
-
6:
– Integer
Input
-
On entry: the index of the last element of
rv to be searched.
Constraint:
.
-
7:
– const double
Input
-
On entry: , the sought-after items.
-
8:
– Integer
Input
-
On entry: , the number of items sought.
Constraint:
.
-
9:
– Integer
Output
-
On exit: if
,
contains the index of the largest entry in
rv which is smaller than or equal to
.
-
10:
– double *
Communication Structure
-
On entry:
, the reference scalar required by the direct search algorithm. If
,
m01ndc calculates the value of
h required by the direct search function for the given values in
rv. Otherwise, the value of
h as declared in the function from which
m01ndc is called. If
,
h is not referenced.
On exit: the value of
h required by the direct search function for the given values in
rv.
Constraint:
if
or
,
h must be unchanged from the previous call to
m01ndc.
-
11:
– Integer
Communication Array
-
On entry: if
,
k, the reference vector from the previous call to
m01ndc. If
or
,
k is not referenced and may be
NULL.
On exit: if or , the reference vector.
Constraint:
if
,
k must be unchanged from the previous call to
m01ndc.
-
12:
– Integer *
Input/Output
-
On entry: if
,
m01ndc calculates the dimension of
k required by the direct search function for the given values in
rv. Otherwise, the dimension of the array
k as declared in the function from which
m01ndc is called. If
,
lk is not referenced.
On exit: if
, the dimension of the array
k required by the direct search function for the given values in
rv. Otherwise, the dimension of the array
k as declared in the function from which
m01ndc is called.
Constraint:
if
or
,
lk must be unchanged from the previous call to
m01ndc.
-
13:
– NagError *
Input/Output
-
The NAG error argument (see
Section 7 in the Introduction to the NAG Library CL Interface).
6
Error Indicators and Warnings
- NE_ALLOC_FAIL
-
Dynamic memory allocation failed.
See
Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
- NE_BAD_PARAM
-
Either
m01ndc was not called with
or
,
or the values of
h,
k or
lk may have become corrupted.
On entry, argument had an illegal value.
- NE_INT
-
On entry, .
Constraint: .
On entry, .
Constraint: .
On entry, .
Constraint: , , or .
On entry, .
Constraint: .
- NE_INT_2
-
On entry, , , .
Constraint: .
- NE_INTERNAL_ERROR
-
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact
NAG for assistance.
See
Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
- NE_NO_LICENCE
-
Your licence key may have expired or may not have been installed correctly.
See
Section 8 in the Introduction to the NAG Library CL Interface for further information.
- NE_NOT_STRICTLY_INCREASING
-
On entry,
rv must be sorted in strictly ascending order:
.
- NE_OVERFLOW
-
On entry, the values in
rv are such that the required value of
lk would
overflow the current platform's largest positive integer value. This error
should only appear when
m01ndc is called with
(i.e., when the function is asked to calculate the required value of
lk for the given
rv).
7
Accuracy
Not applicable.
8
Parallelism and Performance
m01ndc is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
Please consult the
X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this function. Please also consult the
Users' Note for your implementation for any additional implementation-specific information.
The argument
validate should be used with caution. Set it to Nag_FALSE only if you are confident that the other arguments are correct, in particular that array
rv is in fact arranged in strictly ascending order. If you wish to search the same array
rv many times, you are recommended to set
validate to Nag_TRUE on the first call of
m01ndc and to Nag_FALSE on subsequent calls, in order to minimize the amount of time spent checking
rv, which may be significant if
rv is large.
The time taken by
m01ndc to construct the reference vector (i.e., when the function is called with
) is
. Note that the values stored in
k depend on all entries of
rv, and not just those in the interval
. Thereafter, searching for
m items using direct search (i.e., when the function is called with
) is
. In contrast offset-based binary search (i.e., when the function is called with
), does not require construction of the reference vector and has time complexity
. Although this is the same as classical binary search, offset-based binary search may be faster in practice because the implementation does not feature conditional branches. Direct search is preferable when the overhead of constructing the reference vector can be offset by conducting multiple searches on an unchanged
rv.
10
Example
This example reads a list of double numbers and a list of sought-after items and performs the search for these items. The example demonstrates how to use m01ndc for both direct search (i.e., ) and offset-based binary search ().
10.1
Program Text
10.2
Program Data
10.3
Program Results