Package net.algart.arrays

Class GeneralizedBitProcessing

java.lang.Object
net.algart.arrays.AbstractArrayProcessorWithContextSwitching
net.algart.arrays.GeneralizedBitProcessing
All Implemented Interfaces:
Cloneable, ArrayProcessor, ArrayProcessorWithContextSwitching
public class GeneralizedBitProcessing extends AbstractArrayProcessorWithContextSwitching

Universal converter of bitwise operation (an algorithm processing BitArray) to operation over any primitive type (an algorithm processing PArray).

This class implements the following common idea. Let we have some algorithm, that transforms the source bit array (BitArray) b to another bit array ƒ(b). (Here is an interface GeneralizedBitProcessing.SliceOperation representing such algorithm.) Let we want to generalize this algorithm for a case of any element types — byte, int, double, etc.; in other words, for the common case of PArray. This class allows to do this.

Namely, let we have the source array (PArray) a, and let amin..amax be some numeric range, amin≤amax usually (but not necessarily) from the minimal to the maximal value, stored in the source array (Arrays.rangeOf(a)). This class can work in two modes, called rounding modes (and represented by GeneralizedBitProcessing.RoundingMode enum): the first mode is called round-down mode, and the second is called round-up mode. Below is the specification of the behaviour in both modes.

Round-down mode Round-up mode

In both modes, we consider n+1 (n≥0) numeric thresholds t0, t1, ..., tn in amin..amax range:

t0 = amin,
t1 = amin + (amax−amin)/n,
. . .
ti = amin + i * (amax−amin)/n,
. . .
tn = amax
(In the degenerated case n=0, we consider t0 = tn = amin.) (In the degenerated case n=0, we consider t0 = tn = amax.)

Then we define the bit slice bi, i=0,1,...,n, as a bit array a≥ti, i.e. BitArray with the same length as a, where each element

bi[k] = a[k]≥ti ? 1 : 0

Then we define the bit slice bi, i=0,1,...,n, as a bit array a>ti, i.e. BitArray with the same length as a, where each element

bi[k] = a[k]>ti ? 1 : 0
The described transformation of the numeric array a to a set of n+1 "slices" (bit arrays) bi is called splitting to slices. Then we consider the backward conversion of the set of bit slices bi to a numeric array a', called joining the slices:
a'[k] = tmax i: bi[k] = 1, or a'[k] = amin if all bi[k] = 0
a'[k] = tmin i: bi[k] = 0, or a'[k] = amax if all bi[k] = 1

It's obvious that if all a elements are inside amin..amax range and if n is large enough, then a' is almost equal to a. In particular, if a is a byte array (ByteArray), amin=0, amax=255 and n=255, then a' is strictly equal to a (in both rounding modes).

The main task, solved by this class, is converting any bitwise operation ƒ(b) to a new operation g(a), defining for any primitive-type array a, according to the following rule:

Round-down mode Round-up mode
g(a)[k] = tmax i: ƒ(bi)[k] = 1, or g(a)[k] = amin if all ƒ(bi)[k] = 0
g(a)[k] = tmin i: ƒ(bi)[k] = 0, or g(a)[k] = amax if all ƒ(bi)[k] = 0
In other words, the source array is split into bit slices, the bitwise operation is applied to all slices, and then we perform the backward conversion (joining) of slices set to a numeric array g(a).

The conversion of the source array a to the target array c=g(a) is performed by the main method of this class: process(UpdatablePArray c, PArray a, Range range, long numberOfSlices). The amin..amax range and the number of slices numberOfSlices=n+1 are specified as arguments of this method. The original bitwise algorithm should be specified while creating an instance of this class by getInstance method.

Note that the described operation does not require to calculate ƒ(b0) in the round-down mode or ƒ(bn) in the round-up mode: the result does not depend on it. Also note that the case n=0 is degenerated: in this case always g(a)[k] = amin (round-down mode) or amax (round-up mode).

Additional useful note: for some kinds of bitwise algorithms, you can improve the precision of the results by replacing (after calling process method) the resulting array c=g(a) with elementwise maximum, in case of round-down mode, or elementwise minimum, in case of round-up mode, of c and the source array a: c=max(c,a) or c=min(c,a) correspondingly. You can do it easily by Arrays.applyFunc(ArrayContext, net.algart.math.functions.Func, UpdatablePArray, PArray...) method with Func.MAX or Func.MIN argument.

This class allocates, in process method, some temporary bit arrays. Arrays are allocated with help of the memory model, returned by context.getMemoryModel() method of the context, specified while creating an instance of this class. If the context is null, or if necessary amount of memory is less than Arrays.SystemSettings.maxTempJavaMemory(), then SimpleMemoryModel is used for allocating temporary arrays. There is a special case when process method is called for bit arrays (element type is boolean); in this case, no AlgART arrays are allocated.

When this class allocates temporary AlgART arrays, it also checks whether the passed (source and destination) arrays are tiled, i.e. they are underlying arrays of some matrices, created by Matrix.tile(long...) or Matrix.tile() method. Only the case, when these methods are implemented in this package, is recognized. In this case, if the src array, passed to process method, is tiled, then the temporary AlgART arrays are tiled with the same tile structure.

This class uses multithreading (alike Arrays.copy(ArrayContext, UpdatableArray, Array) and similar methods) to optimize calculations on multiprocessor or multi-core computers. Namely, the process method processes different bit slices in several parallel threads. However, it is not useful if the bitwise processing method GeneralizedBitProcessing.SliceOperation.processBits(ArrayContext, UpdatableBitArray, BitArray, long, int, int) already use multithreading optimization. In this case, please create an instance of this class via getSingleThreadInstance method.

This class is not thread-safe, but is thread-compatible and can be synchronized manually, if multithread access is necessary. However, usually there are no reasons to use the same instance of this class in different threads: usually there is much better idea to create a separate instance for every thread.

Author:
Daniel Alievsky

  • Method Details

    • getInstance

      public static GeneralizedBitProcessing getInstance(ArrayContext context, GeneralizedBitProcessing.SliceOperation sliceOperation, GeneralizedBitProcessing.RoundingMode roundingMode)
      Returns new instance of this class.
      Parameters:
      context - the context that will be used by this object; may be null, then it will be ignored, and all temporary arrays will be created by SimpleMemoryModel.
      sliceOperation - the bit processing operation that will be generalized by this instance.
      roundingMode - the rounding mode, used by the created instance.
      Returns:
      new instance of this class.
      Throws:
      NullPointerException - if sliceOperation or roundingMode argument is null.
      See Also:

    • getSingleThreadInstance

      public static GeneralizedBitProcessing getSingleThreadInstance(ArrayContext context, GeneralizedBitProcessing.SliceOperation sliceOperation, GeneralizedBitProcessing.RoundingMode roundingMode)
      Returns new instance of this class, that does not use multithreading optimization. Usually this class performs calculations in many threads (different slides in different threads), according to information from the passed context, but an instance, created by this method, does not perform this. It is the best choice if the operation, implemented by passed sliceOperation object, already uses multithreading.
      Parameters:
      context - the context that will be used by this object; may be null, then it will be ignored, and all temporary arrays will be created by SimpleMemoryModel.
      sliceOperation - the bit processing operation that will be generalized by this instance.
      roundingMode - the rounding mode, used by the created instance.
      Returns:
      new instance of this class.
      Throws:
      NullPointerException - if sliceOperation or roundingMode argument is null.
      See Also:

    • context

      public GeneralizedBitProcessing context(ArrayContext newContext)
      Switches the context: returns an instance, identical to this one excepting that it uses the specified newContext for all operations. The returned instance is a clone of this one, but there is no guarantees that it is a deep clone. Usually, the returned instance is used only for performing a subtask of the full task.
      Specified by:
      context in interface ArrayProcessorWithContextSwitching
      Overrides:
      context in class AbstractArrayProcessorWithContextSwitching
      Parameters:
      newContext - another context, used by the returned instance; may be null.
      Returns:
      new instance with another context.

    • sliceOperation

      public GeneralizedBitProcessing.SliceOperation sliceOperation()
      Returns the bit processing algorithm, used by this instance. More precisely, this method just returns a reference to the sliceOperation object, passed to getInstance or getSingleThreadInstance method.
      Returns:
      the bit processing algorithm, used by this instance.

    • roundingMode

      public GeneralizedBitProcessing.RoundingMode roundingMode()
      Returns the rounding mode, used by this instance. More precisely, this method just returns a reference to the roundingMode object, passed to getInstance or getSingleThreadInstance method.
      Returns:
      the roundingMode, used by this instance.

    • numberOfTasks

      public int numberOfTasks()
      Returns the number of threads, that this class uses for multithreading optimization. It is equal to:

      (As in Arrays.copy(ArrayContext, UpdatableArray, Array), if the context argument of getInstance method is null, then DefaultThreadPoolFactory is used.)

      Note that the real number of parallel threads will be a minimum from this value and n, where n+1 is the desired number of slices (the last argument of process(UpdatablePArray, PArray, Range, long) method).

      Returns:
      the number of threads, that this class uses for multithreading optimization.

    • process

      public void process(UpdatablePArray dest, PArray src, Range range, long numberOfSlices)
      Performs processing of the source array src, with saving results in dest array, on the base of the bit processing algorithm, specified for this instance. Namely, the source array src is splitted to bit slices, each slice is processed by GeneralizedBitProcessing.SliceOperation.processBits(ArrayContext, UpdatableBitArray, BitArray, long, int, int) method of the sliceOperation() object (representing the used bit processing algorithm), and the processed slices are joined to the resulting array dest. See the precise description of this generalization of a bit processing algorithm in the comments to this class.

      The src and dest arrays must not be the same array or views of the same array; in other case, the results will be incorrect. These arrays must have the same element types and the same lengths; in other case, an exception will occur.

      The range argument specifies the amin..amax range, used for splitting to bit slices. If you do not want to lose too little or too big values in the processed array, this range should contain all possible values of src array. The simplest way to provide this is using the result of Arrays.rangeOf(src).

      The numberOfSlices argument is the number of bit slices, used for splitting the src array, which is equal to n+1 in the comments to this class. Less values of this argument increases speed, larger values increases precision of the result (only numberOfSlices different values are possible for dest elements). If the element type is a fixed-point type (src and dest are PFixedArray instance), this argument is automatically truncated to min(numberOfSlices, (long)(range.size()+1.0)), because larger values cannot increase the precision.

      Please remember that numberOfSlices=1 (n=0) is a degenerated case: in this case, the dest array is just filled by range.min() (round-down mode) or range.min() (round-up mode), alike in UpdatablePArray.fill(double) method.

      If the element type is boolean (BitArray), then a generalization of the bitwise algorithm is not necessary. In this case, if numberOfSlices>1, this method just calls sliceOperation().processBits method for the passed dest and src arrays. (However, according to the specification of GeneralizedBitProcessing.SliceOperation, if its isInPlaceProcessingAllowed() method returns true, then src arrays is firstly copied into dest, and then the dest arrays is passed as both srcBits and destBits arguments.)

      Note: if the element type is boolean, then multithreading is never used: processBits method is called in the current thread, and its threadIndex and numberOfThreads arguments are 0 and 1 correspondingly.

      Parameters:
      dest - the result of processing.
      src - the source AlgART array.
      range - the amin..amax range, used for splitting to bit slices.
      numberOfSlices - the number of bit slices (i.e. n+1); must be positive.
      Throws:
      NullPointerException - if one of the arguments is null.
      IllegalArgumentException - if dest and src arrays have different lengths or element types, or if numberOfSlices<=0.