org.apache.hadoop.hbase.master

Class RegionPlacementMaintainer.RandomizedMatrix

java.lang.Object

org.apache.hadoop.hbase.master.RegionPlacementMaintainer.RandomizedMatrix

Enclosing class:

RegionPlacementMaintainer

protected static class RegionPlacementMaintainer.RandomizedMatrix
extends Object

Some algorithms for solving the assignment problem may traverse workers or jobs in linear order which may result in skewing the assignments of the first jobs in the matrix toward the last workers in the matrix if the costs are uniform. To avoid this kind of clumping, we can randomize the rows and columns of the cost matrix in a reversible way, such that the solution to the assignment problem can be interpreted in terms of the original untransformed cost matrix. Rows and columns are transformed independently such that the elements contained in any row of the input matrix are the same as the elements in the corresponding output matrix, and each row has its elements transformed in the same way. Similarly for columns.

Field Summary

Fields

Modifier and Type	Field and Description
private int[]	colInverse
private int	cols
private int[]	colTransform
private int[]	rowInverse
private int	rows
private int[]	rowTransform

Constructor Summary

Constructors

Constructor and Description
RandomizedMatrix(int rows, int cols) Create a randomization scheme for a matrix of a given size.

Method Summary

Modifier and Type	Method and Description
float[][]	invert(float[][] matrix) Copy a given matrix into a new matrix, transforming each row index and each column index according to the inverse of the randomization scheme that was created at construction time.
int[]	invertIndices(int[] indices) Given an array where each element indices[i] represents the randomized column index corresponding to randomized row index i, create a new array with the corresponding inverted indices.
float[][]	transform(float[][] matrix) Copy a given matrix into a new matrix, transforming each row index and each column index according to the randomization scheme that was created at construction time.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

rows

private final int rows

cols

private final int cols

rowTransform

private final int[] rowTransform

rowInverse

private final int[] rowInverse

colTransform

private final int[] colTransform

colInverse

private final int[] colInverse

Constructor Detail

RandomizedMatrix

public RandomizedMatrix(int rows,
                        int cols)

Create a randomization scheme for a matrix of a given size.

Parameters:

rows - the number of rows in the matrix

cols - the number of columns in the matrix

Method Detail

transform

public float[][] transform(float[][] matrix)

Copy a given matrix into a new matrix, transforming each row index and each column index according to the randomization scheme that was created at construction time.

Parameters:

matrix - the cost matrix to transform

Returns:

a new matrix with row and column indices transformed

invert

public float[][] invert(float[][] matrix)

Copy a given matrix into a new matrix, transforming each row index and each column index according to the inverse of the randomization scheme that was created at construction time.

Parameters:

matrix - the cost matrix to be inverted

Returns:

a new matrix with row and column indices inverted

invertIndices

public int[] invertIndices(int[] indices)

Given an array where each element indices[i] represents the randomized column index corresponding to randomized row index i, create a new array with the corresponding inverted indices.

Parameters:

indices - an array of transformed indices to be inverted

Returns:

an array of inverted indices