Class Partitioning
Performance
Partitioning into two intervals is O( N ). Partitioning into k intervals is O( N * log(k)). Constants factors are minimized.
- Version:
- 1.0, 09/24/99
- See Also:
-
Constructor Summary
ConstructorsModifierConstructorDescriptionprotected
Makes this class non instantiable, but still let's others inherit from it. -
Method Summary
Modifier and TypeMethodDescriptionstatic void
partition
(DoubleMatrix2D matrix, int[] rowIndexes, int rowFrom, int rowTo, int column, double[] splitters, int splitFrom, int splitTo, int[] splitIndexes) Same asPartitioning.partition(int[],int,int,int[],int,int,int[])
except that it synchronously partitions the rows of the given matrix by the values of the given matrix column; This is essentially the same as partitioning a list of composite objects by some instance variable; In other words, two entire rows of the matrix are swapped, whenever two column values indicate so.static DoubleMatrix2D
partition
(DoubleMatrix2D matrix, int column, double[] splitters, int[] splitIndexes) Same asPartitioning.partition(int[],int,int,int[],int,int,int[])
except that it synchronously partitions the rows of the given matrix by the values of the given matrix column; This is essentially the same as partitioning a list of composite objects by some instance variable; In other words, two entire rows of the matrix are swapped, whenever two column values indicate so.private static int
xPartitionOld
(DoubleMatrix2D matrix, DoubleMatrix1D column, int from, int to, double splitter) Same asinvalid reference
#partition(int[],int,int,int)
private static void
xPartitionOld
(DoubleMatrix2D matrix, DoubleMatrix1D column, int from, int to, double[] splitters, int splitFrom, int splitTo, int[] splitIndexes) Same asinvalid reference
#partition(int[],int,int,int[],int,int,int[])
-
Constructor Details
-
Partitioning
protected Partitioning()Makes this class non instantiable, but still let's others inherit from it.
-
-
Method Details
-
partition
public static void partition(DoubleMatrix2D matrix, int[] rowIndexes, int rowFrom, int rowTo, int column, double[] splitters, int splitFrom, int splitTo, int[] splitIndexes) Same asPartitioning.partition(int[],int,int,int[],int,int,int[])
except that it synchronously partitions the rows of the given matrix by the values of the given matrix column; This is essentially the same as partitioning a list of composite objects by some instance variable; In other words, two entire rows of the matrix are swapped, whenever two column values indicate so.Let's say, a "row" is an "object" (tuple, d-dimensional point). A "column" is the list of "object" values of a given variable (field, dimension). A "matrix" is a list of "objects" (tuples, points).
Now, rows (objects, tuples) are partially sorted according to their values in one given variable (dimension). Two entire rows of the matrix are swapped, whenever two column values indicate so.
Note that arguments are not checked for validity.
Example:
8 x 3 matrix:
23, 22, 21
20, 19, 18
17, 16, 15
14, 13, 12
11, 10, 9
8, 7, 6
5, 4, 3
2, 1, 0column = 0;
rowIndexes = {0,1,2,..,matrix.rows()-1}; rowFrom = 0;
rowTo = matrix.rows()-1;
splitters = {5,10,12}
c = 0;
d = splitters.length-1;
partition(matrix,rowIndexes,rowFrom,rowTo,column,splitters,c,d,splitIndexes);
==>
splitIndexes == {0, 2, 3}
rowIndexes == {7, 6, 5, 4, 0, 1, 2, 3}The matrix IS NOT REORDERED.
Here is how it would look
like, if it would be reordered
accoring to rowIndexes.
8 x 3 matrix:
2, 1, 0
5, 4, 3
8, 7, 6
11, 10, 9
23, 22, 21
20, 19, 18
17, 16, 15
14, 13, 12- Parameters:
matrix
- the matrix to be partitioned.rowIndexes
- the index of the i-th row; is modified by this method to reflect partitioned indexes.rowFrom
- the index of the first row (inclusive).rowTo
- the index of the last row (inclusive).column
- the index of the column to partition on.splitters
- the values at which the rows shall be split into intervals. Must be sorted ascending and must not contain multiple identical values. These preconditions are not checked; be sure that they are met.splitFrom
- the index of the first splitter element to be considered.splitTo
- the index of the last splitter element to be considered. The method considers the splitter elements splitters[splitFrom] .. splitters[splitTo].splitIndexes
- a list into which this method fills the indexes of rows delimiting intervals. Upon return splitIndexes[splitFrom..splitTo] will be set accordingly. Therefore, must satisfy splitIndexes.length >= splitters.length.
-
partition
public static DoubleMatrix2D partition(DoubleMatrix2D matrix, int column, double[] splitters, int[] splitIndexes) Same asPartitioning.partition(int[],int,int,int[],int,int,int[])
except that it synchronously partitions the rows of the given matrix by the values of the given matrix column; This is essentially the same as partitioning a list of composite objects by some instance variable; In other words, two entire rows of the matrix are swapped, whenever two column values indicate so.Let's say, a "row" is an "object" (tuple, d-dimensional point). A "column" is the list of "object" values of a given variable (field, dimension). A "matrix" is a list of "objects" (tuples, points).
Now, rows (objects, tuples) are partially sorted according to their values in one given variable (dimension). Two entire rows of the matrix are swapped, whenever two column values indicate so.
Note that arguments are not checked for validity.
Example:
8 x 3 matrix:
23, 22, 21
20, 19, 18
17, 16, 15
14, 13, 12
11, 10, 9
8, 7, 6
5, 4, 3
2, 1, 0column = 0;
splitters = {5,10,12}
partition(matrix,column,splitters,splitIndexes);
==>
splitIndexes == {0, 2, 3}The matrix IS NOT REORDERED.
The new VIEW IS REORDERED:
8 x 3 matrix:
2, 1, 0
5, 4, 3
8, 7, 6
11, 10, 9
23, 22, 21
20, 19, 18
17, 16, 15
14, 13, 12- Parameters:
matrix
- the matrix to be partitioned.column
- the index of the column to partition on.splitters
- the values at which the rows shall be split into intervals. Must be sorted ascending and must not contain multiple identical values. These preconditions are not checked; be sure that they are met.splitIndexes
- a list into which this method fills the indexes of rows delimiting intervals. Therefore, must satisfy splitIndexes.length >= splitters.length.- Returns:
- a new matrix view having rows partitioned by the given column and splitters.
-
xPartitionOld
private static void xPartitionOld(DoubleMatrix2D matrix, DoubleMatrix1D column, int from, int to, double[] splitters, int splitFrom, int splitTo, int[] splitIndexes) Same asinvalid reference
#partition(int[],int,int,int[],int,int,int[])
Let's say, a "row" is an "object" (tuple, d-dimensional point). A "column" is the list of "object" values of a given variable (field, dimension). A "matrix" is a list of "objects" (tuples, points).
Now, rows (objects, tuples) are partially sorted according to their values in one given variable (dimension). Two entire rows of the matrix are swapped, whenever two column values indicate so.
Of course, the column must not be a column of a different matrix. More formally, there must hold:
There exists an i such that matrix.viewColumn(i)==column.Note that arguments are not checked for validity.
Example:
8 x 3 matrix:
23, 22, 21
20, 19, 18
17, 16, 15
14, 13, 12
11, 10, 9
8, 7, 6
5, 4, 3
2, 1, 0column = matrix.viewColumn(0);
a = 0;
b = column.size()-1;
splitters={5,10,12}
c=0;
d=splitters.length-1;
partition(matrix,column,a,b,splitters,c,d,splitIndexes);
==>
splitIndexes == {0, 2, 3}8 x 3 matrix:
2, 1, 0
5, 4, 3
8, 7, 6
11, 10, 9
23, 22, 21
20, 19, 18
17, 16, 15
14, 13, 12 -
xPartitionOld
private static int xPartitionOld(DoubleMatrix2D matrix, DoubleMatrix1D column, int from, int to, double splitter) Same asinvalid reference
#partition(int[],int,int,int)
Let's say, a "row" is an "object" (tuple, d-dimensional point). A "column" is the list of "object" values of a given variable (field, dimension). A "matrix" is a list of "objects" (tuples, points).
Now, rows (objects, tuples) are partially sorted according to their values in one given variable (dimension). Two entire rows of the matrix are swapped, whenever two column values indicate so.
Of course, the column must not be a column of a different matrix. More formally, there must hold:
There exists an i such that matrix.viewColumn(i)==column. Note that arguments are not checked for validity.
-