jsr166y.forkjoin
public class ParallelArray<T> extends java.lang.Object implements java.lang.Iterable<T>
A ParallelArray maintains a ForkJoinExecutor
and an
array in order to provide parallel aggregate operations. The main
operations are to apply some procedure to each element, to
map each element to a new element, to replace
each element, to select a subset of elements based on
matching a predicate or ranges of indices, and to reduce
all elements into a single value such as a sum.
A ParallelArray is constructed by allocating, using, or copying
an array, using one of the static factory methods create(int, java.lang.Class super T>, jsr166y.forkjoin.ForkJoinExecutor)
,
createEmpty(int, java.lang.Class super T>, jsr166y.forkjoin.ForkJoinExecutor)
, createUsingHandoff(T[], jsr166y.forkjoin.ForkJoinExecutor)
and createFromCopy(T[], jsr166y.forkjoin.ForkJoinExecutor)
. Upon construction, the encapsulated array managed
by the ParallelArray must not be shared between threads without
external synchronization. In particular, as is the case with any
array, access by another thread of an element of a ParallelArray
while another operation is in progress has undefined effects.
The ForkJoinExecutor used to construct a ParallelArray can be
shared safely by other threads (and used in other
ParallelArrays). To avoid the overhead associated with creating
multiple executors, it is often a good idea to use the defaultExecutor()
across all ParallelArrays. However, you might
choose to use different ones for the sake of controlling processor
usage, isolating faults, and/or ensuring progress.
A ParallelArray is not a List. It relies on random access across
array elements to support efficient parallel operations. However,
a ParallelArray can be viewed and manipulated as a List, via method
asList()
. The asList view allows
incremental insertion and modification of elements while setting up
a ParallelArray, generally before using it for parallel
operations. Similarly, the list view may be useful when accessing
the results of computations in sequential contexts. A
ParallelArray may also be created using the elements of any other
Collection, by constructing from the array returned by the
Collection's toArray method. The effects of mutative
asList operations may also be achieved directly using
method setLimit(int)
along with element-by-element access
methods get(int)
and set(int, T)
.
Most operations can be prefixed with range bounds, filters, and mappings using withBounds, withFilter, and withMapping, respectively. For example, aParallelArray.withFilter(aPredicate).all() creates a new ParallelArray containing only those elements matching the predicate. As illustrated below, a mapping often represents accessing some field or invoking some method of an element. These versions are typically more efficient than performing selections, then mappings, then other operations in multiple (parallel) steps. The basic ideas and usages of filtering and mapping are similar to those in database query systems such as SQL, but take a more restrictive form. Series of filter and mapping prefixes may each be cascaded, but all filter prefixes must precede all mapping prefixes, to ensure efficient execution in s single parallel step. Instances of WithFilter etc are useful only as operation prefixes, and should not normally be stored in variables for future use.
This class includes some reductions, such as min, that are commonly useful for most element types, as well as a combined version, summary, that computes all of them in a single parallel step, which is normally more efficient that computing each in turn.
While ParallelArrays can be based on any kind of an object
array, including "boxed" types such as Long, parallel operations on
scalar "unboxed" type are likely to be substantially more
efficient. For this reason, classes ParallelLongArray
, and
ParallelDoubleArray
are also supplied, and designed to
smoothly interoperate with ParallelArrays. You should also use a
ParallelLongArray for processing other integral scalar data
(int, short, etc). And similarly use a
ParallelDoubleArray for float data. (Further
specializations for these other types would add clutter without
significantly improving performance beyond that of the Long and
Double versions.)
The methods in this class are designed to perform efficiently with both large and small pools, even with single-thread pools on uniprocessors. However, there is some overhead in parallelizing operations, so short computations on small arrays might not execute faster than sequential versions, and might even be slower.
Sample usages. The main difference between programming with plain arrays and programming with aggregates is that you must separately define each of the component functions on elements. For example, the following returns the maximum Grade Point Average across all senior students, given a (fictional) Student class:
import static Ops.*; class StudentStatistics { ParallelArray<Student> students = ... // ... public double getMaxSeniorGpa() { return students.withFilter(isSenior).withMapping(gpaField).max(); } // helpers: static final class IsSenior implements Predicate<Student> { public boolean evaluate(Student s) { return s.credits > 90; } } static final IsSenior isSenior = new IsSenior(); static final class GpaField implements MapperToDouble<Student> { public double map(Student s) { return s.gpa; } } static final GpaField gpaField = new GpaField(); }
Modifier and Type | Class and Description |
---|---|
static interface |
ParallelArray.SummaryStatistics<T>
Summary statistics for a possibly bounded, filtered, and/or
mapped ParallelArray.
|
static class |
ParallelArray.WithBounds<T>
A restriction of parallel array operations to apply only within
a given range of indices.
|
static class |
ParallelArray.WithDoubleMapping<T>
A modifier for parallel array operations to apply to mappings
of elements to doubles, not to the elements themselves
|
static class |
ParallelArray.WithFilter<T>
A restriction of parallel array operations to apply only to
elements for which a selector returns true
|
static class |
ParallelArray.WithLongMapping<T>
A modifier for parallel array operations to apply to mappings
of elements to longs, not to the elements themselves
|
static class |
ParallelArray.WithMapping<T,U>
A modifier for parallel array operations to apply to mappings
of elements, not to the elements themselves
|
Modifier | Constructor and Description |
---|---|
protected |
ParallelArray(ForkJoinExecutor executor,
T[] array,
int limit)
Constructor for use by subclasses to create a new ParallelArray
using the given executor, and initially using the supplied
array, with effective size bound by the given limit.
|
Modifier and Type | Method and Description |
---|---|
void |
addAll(ParallelArray.WithBounds<T> other)
Equivalent to AsList.addAll but specialized for
ParallelArray arguments and likely to be more efficient.
|
void |
addAll(ParallelArray<T> other)
Equivalent to AsList.addAll but specialized for
ParallelArray arguments and likely to be more efficient.
|
void |
addAll(T[] other)
Equivalent to AsList.addAll but specialized for array
arguments and likely to be more efficient.
|
ParallelArray<T> |
all()
Returns a new ParallelArray holding all elements
|
ParallelArray<T> |
all(java.lang.Class<? super T> elementType)
Returns a new ParallelArray with the given element type holding
all elements
|
ParallelArray<T> |
allNonidenticalElements()
Returns a new ParallelArray containing only the non-null unique
elements of this array (that is, without any duplicates).
|
ParallelArray<T> |
allUniqueElements()
Returns a new ParallelArray containing only the non-null unique
elements of this array (that is, without any duplicates).
|
void |
apply(Ops.Procedure<? super T> procedure)
Applies the given procedure to elements
|
java.util.List<T> |
asList()
Returns a view of this ParallelArray as a List.
|
int |
binarySearch(T target)
Assuming this array is sorted, returns the index of an element
equal to given target, or -1 if not present.
|
int |
binarySearch(T target,
java.util.Comparator<? super T> comparator)
Assuming this array is sorted with respect to the given
comparator, returns the index of an element equal to given
target, or -1 if not present.
|
<U,V> ParallelArray<V> |
combine(ParallelArray.WithBounds<? extends U> other,
Ops.Combiner<? super T,? super U,? extends V> combiner)
Returns a ParallelArray containing results of
applying combine(thisElement, otherElement)
for each element.
|
<U,V> ParallelArray<V> |
combine(ParallelArray.WithBounds<? extends U> other,
Ops.Combiner<? super T,? super U,? extends V> combiner,
java.lang.Class<? super V> elementType)
Returns a ParallelArray containing results of
applying combine(thisElement, otherElement)
for each element.
|
<U,V> ParallelArray<V> |
combine(ParallelArray<? extends U> other,
Ops.Combiner<? super T,? super U,? extends V> combiner)
Returns a ParallelArray containing results of
applying combine(thisElement, otherElement)
for each element.
|
<U,V> ParallelArray<V> |
combine(ParallelArray<? extends U> other,
Ops.Combiner<? super T,? super U,? extends V> combiner,
java.lang.Class<? super V> elementType)
Returns a ParallelArray containing results of
applying combine(thisElement, otherElement)
for each element.
|
<U,V> ParallelArray<V> |
combine(U[] other,
Ops.Combiner<? super T,? super U,? extends V> combiner)
Returns a ParallelArray containing results of
applying combine(thisElement, otherElement)
for each element.
|
<U,V> ParallelArray<V> |
combine(U[] other,
Ops.Combiner<? super T,? super U,? extends V> combiner,
java.lang.Class<? super V> elementType)
Returns a ParallelArray containing results of
applying combine(thisElement, otherElement)
for each element.
|
static <T> ParallelArray<T> |
create(int size,
java.lang.Class<? super T> elementType,
ForkJoinExecutor executor)
Creates a new ParallelArray using the given executor and
an array of the given size constructed using the
indicated base element type.
|
static <T> ParallelArray<T> |
createEmpty(int size,
java.lang.Class<? super T> elementType,
ForkJoinExecutor executor)
Creates a new ParallelArray using the given executor and an
array of the given size constructed using the indicated base
element type, but with an initial effective size of zero,
enabling incremental insertion via
asList()
operations. |
static <T> ParallelArray<T> |
createFromCopy(int size,
T[] source,
ForkJoinExecutor executor)
Creates a new ParallelArray using an array of the given size,
initially holding copies of the given source truncated or
padded with nulls to obtain the specified length.
|
static <T> ParallelArray<T> |
createFromCopy(T[] source,
ForkJoinExecutor executor)
Creates a new ParallelArray using the given executor and
initially holding copies of the given
source elements.
|
static <T> ParallelArray<T> |
createUsingHandoff(T[] handoff,
ForkJoinExecutor executor)
Creates a new ParallelArray initially using the given array and
executor.
|
void |
cumulate(Ops.Reducer<T> reducer,
T base)
Replaces each element with the running cumulation of applying
the given reducer.
|
static ForkJoinExecutor |
defaultExecutor()
Returns a common default executor for use in ParallelArrays.
|
T |
get(int i)
Returns the element of the array at the given index
|
T[] |
getArray()
Returns the underlying array used for computations
|
ForkJoinExecutor |
getExecutor()
Returns the executor used for computations
|
int |
indexOf(T target)
Returns the index of some element equal to given target,
or -1 if not present
|
java.util.Iterator<T> |
iterator()
Returns an iterator stepping through each element of the array
up to the current limit.
|
T |
max()
Returns the maximum element, or null if empty
assuming that all elements are Comparables
|
T |
max(java.util.Comparator<? super T> comparator)
Returns the maximum element, or null if empty
|
T |
min()
Returns the minimum element, or null if empty,
assuming that all elements are Comparables
|
T |
min(java.util.Comparator<? super T> comparator)
Returns the minimum element, or null if empty
|
T |
precumulate(Ops.Reducer<T> reducer,
T base)
Replaces each element with the cumulation of applying the given
reducer to all previous values, and returns the total
reduction.
|
T |
reduce(Ops.Reducer<T> reducer,
T base)
Returns reduction of elements
|
void |
removeConsecutiveDuplicates()
Removes consecutive elements that are equal (or null), shifting
others leftward, and possibly decreasing size.
|
void |
removeNulls()
Removes null elements, shifting others leftward, and possibly
decreasing size.
|
void |
replaceWithCombination(ParallelArray.WithBounds<? extends T> other,
Ops.Reducer<T> combiner)
Replaces elements with results of applying
combine(thisElement, otherElement)
|
void |
replaceWithCombination(ParallelArray<? extends T> other,
Ops.Reducer<T> combiner)
Replaces elements with results of applying
combine(thisElement, otherElement)
|
void |
replaceWithCombination(T[] other,
Ops.Reducer<T> combiner)
Replaces elements with results of applying
combine(thisElement, otherElement)
|
void |
replaceWithGeneratedValue(Ops.Generator<? extends T> generator)
Replaces elements with the results of applying the given
generator.
|
void |
replaceWithMappedIndex(Ops.MapperFromInt<? extends T> mapper)
Replaces elements with the results of applying the given
mapper to their indices.
|
void |
replaceWithTransform(Ops.Mapper<? super T,? extends T> mapper)
Replaces elements with the results of applying the given mapper
to their current values.
|
void |
replaceWithValue(T value)
Replaces elements with the given value.
|
void |
set(int i,
T x)
Sets the element of the array at the given index to the given value
|
void |
setLimit(int newLimit)
Ensures that the underlying array can be accessed up to the
given upper bound, reallocating and copying the underlying
array to expand if necessary.
|
int |
size()
Returns the effective size of the underlying array.
|
void |
sort()
Sorts the array, assuming all elements are Comparable.
|
void |
sort(java.util.Comparator<? super T> comparator)
Sorts the array.
|
ParallelArray.SummaryStatistics<T> |
summary()
Returns summary statistics, assuming that all elements are
Comparables
|
ParallelArray.SummaryStatistics<T> |
summary(java.util.Comparator<? super T> comparator)
Returns summary statistics, using the given comparator
to locate minimum and maximum elements.
|
java.lang.String |
toString()
Equivalent to asList().toString()
|
ParallelArray.WithBounds<T> |
withBounds(int firstIndex,
int upperBound)
Returns an operation prefix that causes a method to
operate only on the elements of the array between
firstIndex (inclusive) and upperBound (exclusive).
|
ParallelArray.WithFilter<T> |
withFilter(Ops.Predicate<? super T> selector)
Returns an operation prefix that causes a method to operate
only on the elements of the array for which the given selector
returns true
|
<U> ParallelArray.WithMapping<T,U> |
withMapping(Ops.Mapper<? super T,? extends U> mapper)
Returns an operation prefix that causes a method to operate
on mapped elements of the array using the given mapper.
|
ParallelArray.WithDoubleMapping<T> |
withMapping(Ops.MapperToDouble<? super T> mapper)
Returns an operation prefix that causes a method to operate
on mapped elements of the array using the given mapper.
|
ParallelArray.WithLongMapping<T> |
withMapping(Ops.MapperToLong<? super T> mapper)
Returns an operation prefix that causes a method to operate
on mapped elements of the array using the given mapper.
|
protected ParallelArray(ForkJoinExecutor executor, T[] array, int limit)
create(int, java.lang.Class super T>, jsr166y.forkjoin.ForkJoinExecutor)
,
createEmpty(int, java.lang.Class super T>, jsr166y.forkjoin.ForkJoinExecutor)
, createUsingHandoff(T[], jsr166y.forkjoin.ForkJoinExecutor)
or createFromCopy(T[], jsr166y.forkjoin.ForkJoinExecutor)
.executor
- the executorarray
- the arraylimit
- the upper bound limitpublic static ForkJoinExecutor defaultExecutor()
public static <T> ParallelArray<T> create(int size, java.lang.Class<? super T> elementType, ForkJoinExecutor executor)
size
- the array sizeelementType
- the type of the elementsexecutor
- the executorpublic static <T> ParallelArray<T> createUsingHandoff(T[] handoff, ForkJoinExecutor executor)
handoff
- the arrayexecutor
- the executorpublic static <T> ParallelArray<T> createFromCopy(T[] source, ForkJoinExecutor executor)
source
- the source of initial elementsexecutor
- the executorpublic static <T> ParallelArray<T> createFromCopy(int size, T[] source, ForkJoinExecutor executor)
source
- the source of initial elementssize
- the array sizeexecutor
- the executorpublic static <T> ParallelArray<T> createEmpty(int size, java.lang.Class<? super T> elementType, ForkJoinExecutor executor)
asList()
operations.size
- the array sizeelementType
- the type of the elementsexecutor
- the executorpublic ForkJoinExecutor getExecutor()
public void apply(Ops.Procedure<? super T> procedure)
procedure
- the procedurepublic T reduce(Ops.Reducer<T> reducer, T base)
reducer
- the reducerbase
- the result for an empty arraypublic ParallelArray<T> all()
public ParallelArray<T> all(java.lang.Class<? super T> elementType)
elementType
- the type of the elementspublic <U,V> ParallelArray<V> combine(U[] other, Ops.Combiner<? super T,? super U,? extends V> combiner)
other
- the other arraycombiner
- the combinerjava.lang.ArrayIndexOutOfBoundsException
- if other array is
shorter than this array.public <U,V> ParallelArray<V> combine(ParallelArray<? extends U> other, Ops.Combiner<? super T,? super U,? extends V> combiner)
other
- the other arraycombiner
- the combinerjava.lang.ArrayIndexOutOfBoundsException
- if other array is not
the same length as this array.public <U,V> ParallelArray<V> combine(U[] other, Ops.Combiner<? super T,? super U,? extends V> combiner, java.lang.Class<? super V> elementType)
other
- the other arraycombiner
- the combinerelementType
- the type of elements of returned arrayjava.lang.ArrayIndexOutOfBoundsException
- if other array is
shorter than this array.public <U,V> ParallelArray<V> combine(ParallelArray.WithBounds<? extends U> other, Ops.Combiner<? super T,? super U,? extends V> combiner)
other
- the other array segmentcombiner
- the combinerjava.lang.ArrayIndexOutOfBoundsException
- if other segment is
shorter than this array.public <U,V> ParallelArray<V> combine(ParallelArray.WithBounds<? extends U> other, Ops.Combiner<? super T,? super U,? extends V> combiner, java.lang.Class<? super V> elementType)
other
- the other array segmentcombiner
- the combinerelementType
- the type of elements of returned arrayjava.lang.ArrayIndexOutOfBoundsException
- if other array is
shorter than this array.public <U,V> ParallelArray<V> combine(ParallelArray<? extends U> other, Ops.Combiner<? super T,? super U,? extends V> combiner, java.lang.Class<? super V> elementType)
other
- the other arraycombiner
- the combinerelementType
- the type of elements of returned arrayjava.lang.ArrayIndexOutOfBoundsException
- if other array is not
the same length as this array.public void replaceWithTransform(Ops.Mapper<? super T,? extends T> mapper)
mapper
- the mapperpublic void replaceWithMappedIndex(Ops.MapperFromInt<? extends T> mapper)
mapper
- the mapperpublic void replaceWithGeneratedValue(Ops.Generator<? extends T> generator)
generator
- the generatorpublic void replaceWithValue(T value)
value
- the valuepublic void replaceWithCombination(ParallelArray<? extends T> other, Ops.Reducer<T> combiner)
other
- the other arraycombiner
- the combinerjava.lang.ArrayIndexOutOfBoundsException
- if other array has
fewer elements than this array.public void replaceWithCombination(T[] other, Ops.Reducer<T> combiner)
other
- the other arraycombiner
- the combinerjava.lang.ArrayIndexOutOfBoundsException
- if other array has
fewer elements than this array.public void replaceWithCombination(ParallelArray.WithBounds<? extends T> other, Ops.Reducer<T> combiner)
other
- the other array segmentcombiner
- the combinerjava.lang.ArrayIndexOutOfBoundsException
- if other segment has
fewer elements.than this array,public int indexOf(T target)
target
- the element to search forpublic int binarySearch(T target)
target
- the element to search forpublic int binarySearch(T target, java.util.Comparator<? super T> comparator)
target
- the element to search forcomparator
- the comparatorpublic ParallelArray.SummaryStatistics<T> summary(java.util.Comparator<? super T> comparator)
comparator
- the comparator to use for
locating minimum and maximum elementspublic ParallelArray.SummaryStatistics<T> summary()
public T min(java.util.Comparator<? super T> comparator)
comparator
- the comparatorpublic T min()
java.lang.ClassCastException
- if any element is not Comparable.public T max(java.util.Comparator<? super T> comparator)
comparator
- the comparatorpublic T max()
java.lang.ClassCastException
- if any element is not Comparable.public void cumulate(Ops.Reducer<T> reducer, T base)
reducer
- the reducerbase
- the result for an empty arraypublic T precumulate(Ops.Reducer<T> reducer, T base)
reducer
- the reducerbase
- the result for an empty arraypublic void sort(java.util.Comparator<? super T> comparator)
comparator
- the comparator to usepublic void sort()
java.lang.ClassCastException
- if any element is not Comparable.public void removeConsecutiveDuplicates()
public void removeNulls()
public ParallelArray<T> allUniqueElements()
public ParallelArray<T> allNonidenticalElements()
public ParallelArray.WithBounds<T> withBounds(int firstIndex, int upperBound)
firstIndex
- the lower bound (inclusive)upperBound
- the upper bound (exclusive)public ParallelArray.WithFilter<T> withFilter(Ops.Predicate<? super T> selector)
selector
- the selectorpublic <U> ParallelArray.WithMapping<T,U> withMapping(Ops.Mapper<? super T,? extends U> mapper)
mapper
- the mapperpublic ParallelArray.WithDoubleMapping<T> withMapping(Ops.MapperToDouble<? super T> mapper)
mapper
- the mapperpublic ParallelArray.WithLongMapping<T> withMapping(Ops.MapperToLong<? super T> mapper)
mapper
- the mapperpublic java.util.Iterator<T> iterator()
asList()
.iterator
in interface java.lang.Iterable<T>
public java.util.List<T> asList()
ArrayList
, and may be used to modify, replace or extend the
bounds of the array underlying this ParallelArray. The methods
supported by this list view are not in general
implemented as parallel operations. This list is also not
itself thread-safe. In particular, performing list updates
while other parallel operations are in progress has undefined
(and surely undesired) effects.public int size()
setLimit(int)
), or the length of the array otherwise.public T get(int i)
i
- the indexpublic void set(int i, T x)
i
- the indexx
- the valuepublic T[] getArray()
public java.lang.String toString()
toString
in class java.lang.Object
public void addAll(T[] other)
other
- the elements to addpublic void addAll(ParallelArray<T> other)
other
- the elements to addpublic void addAll(ParallelArray.WithBounds<T> other)
other
- the elements to addpublic final void setLimit(int newLimit)
newLimit
- the new upper boundjava.lang.IllegalArgumentException
- if newLimit less than zero.