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      */
split(List<IModuleDef> seq, int k)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      */
buildPartitionTable(List<IModuleDef> seq, int k)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