All nearest smaller values
Encyclopedia
In computer science
, the all nearest smaller values problem involves computing, for each value in a sequence of numbers, the previous smaller value that has the closest position in the sequence to the given value. This problem was identified by as a versatile subroutine
for many other tasks in parallel computing
; they developed efficient parallel algorithms for the problem in the Parallel Random Access Machine
model, and later researchers have studied algorithms for it in other models of parallel computation. It may also be solved efficiently on a non-parallel computer, in linear time using a stack
-based algorithm.
The first element of the sequence (0) has no previous value.
The nearest (only) smaller value previous to 8 and to 4 is 0. All three values previous to 12 are smaller, but the nearest one is 4. Continuing in the same way, the nearest previous smaller values for this sequence (indicating the nonexistence of a previous smaller value by a dash) are
In most applications, the positions of the nearest smaller values, and not the values themselves, should be computed, and in many applications the same computation should be computed for the reversal of the sequence in order to find the following smaller value that is closest in the sequence.
Similar techniques may also be applied to problems of polygon triangulation
, convex hull
construction (parallelizing the sequential Graham scan
convex hull algorithm), and reconstruction of trees from two of the trees' traversal orderings.
: one processes the values in sequence order, using the stack to maintain a subsequence of the values that have been processed so far and are smaller than any later value that has already been processed. In pseudocode
, the algorithm is as follows.
Despite having a nested loop structure, the running time of this algorithm is linear, because every iteration of the inner loop removes an item that had been added in some previous iteration of the outer loop.
. For a sequence of n values, stored as an array, they show that the problem may be solved in time O(log log n) using a linear amount of total work. For sequences where all values are integers in the interval [1,s], improved this bound to O(log log log s); they also showed that, for sufficiently large values of s, the previous doubly logarithmic time bound is the best that can be achieved for the problem. Since this work, parallel algorithms for the all nearest smaller values problem have also been developed on other models of parallel computation, including parallel computers with a hypercube-structured communications network, and the bulk synchronous parallel
model.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the all nearest smaller values problem involves computing, for each value in a sequence of numbers, the previous smaller value that has the closest position in the sequence to the given value. This problem was identified by as a versatile subroutine
Subroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
for many other tasks in parallel computing
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
; they developed efficient parallel algorithms for the problem in the Parallel Random Access Machine
Parallel Random Access Machine
In computer science, Parallel Random Access Machine is a shared memory abstract machine. As its name indicates, the PRAM was intended as the parallel computing analogy to the random access machine...
model, and later researchers have studied algorithms for it in other models of parallel computation. It may also be solved efficiently on a non-parallel computer, in linear time using a stack
Stack (data structure)
In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...
-based algorithm.
Example
Suppose that the input is the binary van der Corput sequenceVan der Corput sequence
A van der Corput sequence is a low-discrepancy sequence over the unit interval first published in 1935 by the Dutch mathematician J. G. van der Corput. It is constructed by reversing the base n representation of the sequence of natural numbers...
- 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.
The first element of the sequence (0) has no previous value.
The nearest (only) smaller value previous to 8 and to 4 is 0. All three values previous to 12 are smaller, but the nearest one is 4. Continuing in the same way, the nearest previous smaller values for this sequence (indicating the nonexistence of a previous smaller value by a dash) are
- —, 0, 0, 4, 0, 2, 2, 6, 0, 1, 1, 5, 1, 3, 3, 7.
In most applications, the positions of the nearest smaller values, and not the values themselves, should be computed, and in many applications the same computation should be computed for the reversal of the sequence in order to find the following smaller value that is closest in the sequence.
Applications
mention many other problems that may be solved efficiently in parallel using a nearest smaller values computation. Among them, they include the following:- Merge algorithmMerge algorithmMerge algorithms are a family of algorithms that run sequentially over multiple sorted lists, typically producing more sorted lists as output. This is well-suited for machines with tape drives...
s, computing the merge step of a merge sortMerge sortMerge sort is an O comparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output. It is a divide and conquer algorithm...
. The input to these algorithms consists of two sorted arrays of numbers; the desired output is the same set of numbers in a single sorted array. If one concatenates the two sorted arrays, the first in ascending order and the second in descending order, then the predecessor of each value in the output is either its closest previous smaller value or its closest following smaller value (whichever of the two is larger), and the position of each value in the sorted output array may easily be calculated from the positions of these two nearest smaller values. - Construction of Cartesian treeCartesian treeIn computer science, a Cartesian tree is a binary tree derived from a sequence of numbers; it can be uniquely defined from the properties that it is heap-ordered and that a symmetric traversal of the tree returns the original sequence...
s. A Cartesian tree is a data structureData structureIn computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
introduced by and further studied by for range searchingRange searchingIn its most general form, the range searching problem consists of preprocessing a set S of objects, in order to determine which objects from S a query object, called a range, intersects...
applications. Cartesian trees also arise in the definition of the treapTreapIn computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys...
and randomized binary search tree data structures for binary searching. The Cartesian tree of a sequence of values has a node for each value. The root of the tree is the minimum value of the sequence; for every other node, the parent of the node is either its closest previous smaller value or its closest following smaller value (whichever of the two exists and is larger). Thus, Cartesian trees may be constructed in linear time based on an all nearest smaller values algorithm. - Matching parentheses. If a sequence of open and close parenthesis characters is given as input, together with the nesting depth of each parenthesis, then the match to each open parenthesis is the next close parenthesis with no larger nesting depth, so it can be found by an all nearest smaller values computation that breaks ties in favor of close parentheses. If the nesting depths are not given, they can be calculated using a prefix sumPrefix sumIn computer science, the prefix sum, or scan, of a sequence of numbers is a second sequence of numbers , the sums of prefixes of the input sequence:-Parallel algorithm:A prefix sum can be calculated in parallel by the following steps....
computation.
Similar techniques may also be applied to problems of polygon triangulation
Polygon triangulation
In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P....
, convex hull
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
construction (parallelizing the sequential Graham scan
Graham scan
The Graham scan is a method of computing the convex hull of a finite set of points in the plane with time complexity O. It is named after Ronald Graham, who published the original algorithm in 1972...
convex hull algorithm), and reconstruction of trees from two of the trees' traversal orderings.
Sequential algorithm
On a sequential computer, it is straightforward to compute all nearest smaller values using a stack data structureStack (data structure)
In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...
: one processes the values in sequence order, using the stack to maintain a subsequence of the values that have been processed so far and are smaller than any later value that has already been processed. In pseudocode
Pseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
, the algorithm is as follows.
S = new empty stack data structure
for x in the input sequence:
while S is nonempty and the top element of S is greater than or equal to x:
pop S
if S is empty:
x has no preceding smaller value
else:
the nearest smaller value to x is the top element of S
push x onto S
Despite having a nested loop structure, the running time of this algorithm is linear, because every iteration of the inner loop removes an item that had been added in some previous iteration of the outer loop.
Parallel algorithms
showed how to solve the all nearest smaller values problem efficiently on a concurrent-read concurrent-write Parallel Random Access MachineParallel Random Access Machine
In computer science, Parallel Random Access Machine is a shared memory abstract machine. As its name indicates, the PRAM was intended as the parallel computing analogy to the random access machine...
. For a sequence of n values, stored as an array, they show that the problem may be solved in time O(log log n) using a linear amount of total work. For sequences where all values are integers in the interval [1,s], improved this bound to O(log log log s); they also showed that, for sufficiently large values of s, the previous doubly logarithmic time bound is the best that can be achieved for the problem. Since this work, parallel algorithms for the all nearest smaller values problem have also been developed on other models of parallel computation, including parallel computers with a hypercube-structured communications network, and the bulk synchronous parallel
Bulk synchronous parallel
The Bulk Synchronous Parallel abstract computer is a bridging model for designing parallel algorithms. A bridging model "is intended neither as a hardware nor a programming model but something in between" . It serves a purpose similar to the Parallel Random Access Machine model. BSP differs from...
model.