1 /* 2 * Copyright (C) 2016 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 package com.android.compatibility.common.tradefed.util; 17 18 import com.android.compatibility.common.tradefed.testtype.IModuleDef; 19 20 import java.util.ArrayList; 21 import java.util.List; 22 23 /** 24 * Helper for the shard splitting. Split linearly a list into N sublist with 25 * approximately the same weight. 26 * TODO: Can be generalized for any weighted objects. 27 */ 28 public class LinearPartition { 29 30 /** 31 * Split a list of {@link IModuleDef} into k sub list based on the runtime hint. 32 * 33 * @param seq the full list of {@link IModuleDef} to be splitted 34 * @param k the number of sub list we need. 35 * @return the List of sublist. 36 */ 37 public static List<List<IModuleDef>> split(List<IModuleDef> seq, int k) { 38 ArrayList<List<IModuleDef>> result = new ArrayList<>(); 39 40 if (k <= 0) { 41 ArrayList<IModuleDef> partition = new ArrayList<>(); 42 partition.addAll(seq); 43 result.add(partition); 44 return result; 45 } 46 47 int n = seq.size() - 1; 48 49 if (k > n) { 50 for (IModuleDef value : seq) { 51 ArrayList<IModuleDef> partition = new ArrayList<>(); 52 partition.add(value); 53 result.add(partition); 54 } 55 return result; 56 } 57 58 int[][] table = buildPartitionTable(seq, k); 59 k = k - 2; 60 61 while (k >= 0) { 62 ArrayList<IModuleDef> partition = new ArrayList<>(); 63 64 for (int i = table[n - 1][k] + 1; i < n + 1; i++) { 65 partition.add(seq.get(i)); 66 } 67 68 result.add(0, partition); 69 n = table[n - 1][k]; 70 k = k - 1; 71 } 72 73 ArrayList<IModuleDef> partition = new ArrayList<>(); 74 75 for (int i = 0; i < n + 1; i++) { 76 partition.add(seq.get(i)); 77 } 78 79 result.add(0, partition); 80 81 return result; 82 } 83 84 /** 85 * Internal helper to build the partition table of the linear distribution used for splitting. 86 */ 87 private static int[][] buildPartitionTable(List<IModuleDef> seq, int k) { 88 int n = seq.size(); 89 float[][] table = new float[n][k]; 90 int[][] solution = new int[n - 1][k - 1]; 91 92 for (int i = 0; i < n; i++) { 93 table[i][0] = seq.get(i).getRuntimeHint() + ((i > 0) ? (table[i - 1][0]) : 0); 94 } 95 96 for (int j = 0; j < k; j++) { 97 table[0][j] = seq.get(0).getRuntimeHint(); 98 } 99 100 for (int i = 1; i < n; i++) { 101 for (int j = 1; j < k; j++) { 102 table[i][j] = Integer.MAX_VALUE; 103 for (int x = 0; x < i; x++) { 104 float cost = Math.max(table[x][j - 1], table[i][0] - table[x][0]); 105 if (table[i][j] > cost) { 106 table[i][j] = cost; 107 solution[i - 1][j - 1] = x; 108 } 109 } 110 } 111 } 112 113 return solution; 114 } 115 } 116
