|
SSJ
3.3.1
Stochastic Simulation in Java
|
This class implements a MultiDimSort01<T extends MultiDim01> that can sort an array of points in the \(d\)-dimensional unit hypercube \([0,1)^d\), by following a Hilbert curve, and using (at most) the first \(m\) bits of each point. More...
Classes | |
| class | LongIndexComparator2 |
| The comparator class used by sortIndexOfLong2. More... | |
Public Member Functions | |
| HilbertCurveSort (int d, int m) | |
Constructs a HilbertCurveSort object that will use the first \(m\) bits of each of the first d coordinates to sort the points. More... | |
| HilbertCurveSort (HilbertCurveMap map) | |
| Constructs a HilbertCurveSort object with a given mapping of the Hilbert curve in the unit hypercube. More... | |
| void | sort (MultiDim01[] a, int iMin, int iMax) |
Sorts the subarray a[iMin..iMax-1] with this Hilbert curve sort. More... | |
| void | sort (MultiDim01[] a) |
Sorts the entire array: same as sort (a, 0, a.length). | |
| void | sort (double[][] a, int iMin, int iMax) |
| Sort the array with Hilbert sort. | |
| void | sort (double[][] a) |
| long [][] | getIndexAfterSort () |
| Returns the index computed by the last sort, which is sorted by the second coordinate. More... | |
| int | dimension () |
| Returns the dimension of the unit hypercube. | |
| HilbertCurveMap | getHilbertCurveMap () |
| Returns the HilbertCurveMap used for the mapping. | |
Static Public Member Functions | |
| static void | sortIndexOfLong2 (long[][] index, int iMin, int iMax) |
Sorts the index table by its second coordinate. | |
Package Attributes | |
| int | dimension |
| long [][] | indexForSort |
| HilbertCurveMap | hcMap |
This class implements a MultiDimSort01<T extends MultiDim01> that can sort an array of points in the \(d\)-dimensional unit hypercube \([0,1)^d\), by following a Hilbert curve, and using (at most) the first \(m\) bits of each point.
See [77] . The objects sorted by this class can only be points in \([0,1)^d\), represented as arrays of double. This sort does not apply directly to more general MultiDimComparable<T> objects. For that, see the class HilbertCurveBatchSort instead. However, this sort can be applied to points in another space if we first define a mapping between this space and the unit hypercube. For example, to sort points in the real space, it suffices to map each coordinate to \([0,1)\).
This sort (conceptually) divides the unit hypercube \([0,1)^d\) in \(2^{dm}\) subcubes of equal sizes, by dividing each axis in \(2^m\) equal parts, and uses the first \(m\) bits of each of the \(d\) coordinates to place each point in one of the subcubes. It then enumerates the subcubes in the same order as a Hilbert curve in \([0,1)^d\) would visit them, and orders the points accordingly. Each cube has an (integer) Hilbert index \(r\) from 0 to \(2^{dm}-1\) and the cubes (and points) are ordered according to this index. Two points that fall in the same subcube can be placed in an unspecified (arbitrary) order.
It may happen that some of the subcubes contain more than one point at the end. To get a sense of the probability that this happens, in the case where there are \(n\) points and these points are independent and uniformly distributed over \([0,1)^d\), it is known that the number \(C\) of collisions (the number of times that a point falls in a box already occupied by another point when the points are generated one after the other) has approximately a Poisson distribution with mean \(\lambda_c = n^2/(2k)\), where \(k = 2^{md}\). See [138] , for example. By taking \(m\) such that \(2^{md} \geq n^2\), the expected number of collisions is less than 1/2 and then one can often neglect them. Otherwise, one should increase \(m\). Note however that the assumption of uniformity and independence does not always hold in practice.
For the implementation of sorts based on the Hilbert curve (or Hilbert index), we identify and sort the subcubes by their Hilbert index, but it is also convenient to identify them (alternatively) with \(m\)-bit integer coordinates: The subcube with coordinates \((i_1,…,i_d)\) is defined as \(\prod_{j=0}^{d-1} [i_j 2^{-m}, (i_j+1) 2^{-m})\). Note that each interval is open on the right. That is, if we multiply the coordinates of a point in the subcube by \(2^m\) and truncate them to integers, we obtain the integer coordinates of the subcube. For example, if \(d=2\) and \(m=4\), we have \(2^8 = 256\) subcubes, whose integer coordinates go from 0 to 15, and the point \((0.1, 0.51)\) belongs to the subcube with integer coordinates \((1, 8)\).
For given \(d\) and \(m\), this class offers methods to compute the integer coordinates of the corresponding subcube from the real-valued coordinates of a point in \([0,1)^d\), as well as the Hilbert index of a subcube from its integer coordinates, and vice versa. The code that computes the latter correspondences is taken (with slight adaptations) from the hilbert.c program of Spencer W. Thomas, University of Michigan, 1991.
To sort a set of \(n\) points in \([0,1)^d\), we first compute the integer coordinates and then the Hilbert index of the subcube for each point, then sort the points by order of Hilbert index. For the latter, we construct an index of type long[n][2] whose first coordinate is the point number and the second is its Hilbert index. The method sortIndexOfLong2 is provided to sort such an index by its second coordinate. Points having the same Hilbert index are ordered arbitrarily. After this sort, the first coordinate at position \(i\) in the index is the (original) number of the point that comes in position \(i\) when the points are sorted by Hilbert index. This index is used to reorder the original points. It can be accessed (after each sort) via the method getIndexAfterSort(). This access can be convenient for example in case we sort a double[][] array with the Hilbert sort and want to apply the corresponding permutation afterward to another array of objects. Certain subclasses of HilbertCurveSort use this.
| HilbertCurveSort | ( | int | d, |
| int | m | ||
| ) |
Constructs a HilbertCurveSort object that will use the first \(m\) bits of each of the first d coordinates to sort the points.
The constructor will initialize a HilbertCurveMap with arguments d and \(m\). This map can be accessed with getHilbertCurveMap.
| d | maximum dimension |
| m | number of bits used for each coordinate |
| HilbertCurveSort | ( | HilbertCurveMap | map | ) |
Constructs a HilbertCurveSort object with a given mapping of the Hilbert curve in the unit hypercube.
| map | the mapping of the Hilbert curve |
| long [][] getIndexAfterSort | ( | ) |
Returns the index computed by the last sort, which is sorted by the second coordinate.
It contains (in the first coordinates of its entries) the permutation made by that sort.
| void sort | ( | MultiDim01 [] | a, |
| int | iMin, | ||
| int | iMax | ||
| ) |
Sorts the subarray a[iMin..iMax-1] with this Hilbert curve sort.
The type T must actually be MultiDimComparable01. This is verified in the method.
1.8.14