Package 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
    Description
    private final int[]
    colInverse
     
    private final int
    cols
     
    private final int[]
    colTransform
     
    private final int[]
    rowInverse
     
    private final int
    rows
     
    private final int[]
    rowTransform
     

  • Constructor Summary

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

  • Method Summary

    Modifier and Type
    Method
    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 Details

  • Constructor Details

    • 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 Details

    • 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