OLD | NEW |
(Empty) | |
| 1 #!/usr/bin/python |
| 2 # |
| 3 # Copyright 2012 The Native Client Authors. All rights reserved. |
| 4 # Use of this source code is governed by a BSD-style license that can |
| 5 # be found in the LICENSE file. |
| 6 # Copyright 2012, Google Inc. |
| 7 # |
| 8 |
| 9 """ |
| 10 Table minimization algorithm. |
| 11 """ |
| 12 |
| 13 def optimize_rows(rows): |
| 14 """Breaks rows up into batches, and attempts to minimize each batch, |
| 15 using _optimize_rows_for_single_action. |
| 16 """ |
| 17 rows_by_action = dict() |
| 18 for row in rows: |
| 19 if (row.action, row.arch) in rows_by_action: |
| 20 rows_by_action[(row.action, row.arch)].append(row) |
| 21 else: |
| 22 rows_by_action[(row.action, row.arch)] = [row] |
| 23 |
| 24 optimized_rows = [] |
| 25 for row_group in rows_by_action.itervalues(): |
| 26 optimized_rows.extend(_optimize_rows_for_single_action(row_group)) |
| 27 |
| 28 _remove_unused_columns(optimized_rows) |
| 29 return optimized_rows |
| 30 |
| 31 def _optimize_rows_for_single_action(rows): |
| 32 """Performs basic automatic minimization on the given rows. |
| 33 |
| 34 Repeatedly selects a pair of rows to merge. Recurses until no suitable pair |
| 35 can be found. It's not real smart, and is O(n^2). |
| 36 |
| 37 A pair of rows is compatible if all columns are equal, or if exactly one |
| 38 row differs but is_strictly_compatible. |
| 39 """ |
| 40 for (i, j) in each_index_pair(rows): |
| 41 row_i, row_j = rows[i], rows[j] |
| 42 |
| 43 if row_i.can_merge(row_j): |
| 44 new_rows = list(rows) |
| 45 del new_rows[j] |
| 46 del new_rows[i] |
| 47 new_rows.append(row_i + row_j) |
| 48 return _optimize_rows_for_single_action(new_rows) |
| 49 |
| 50 # No changes made: |
| 51 return rows |
| 52 |
| 53 def _remove_unused_columns(rows): |
| 54 num_cols = len(rows[0].patterns) |
| 55 used = [False] * num_cols |
| 56 |
| 57 for r in rows: |
| 58 for i in range(0, num_cols): |
| 59 if r.patterns[i].mask != 0: |
| 60 used[i] = True |
| 61 |
| 62 if not True in used: |
| 63 # Always preserve at least one column |
| 64 used[0] = True |
| 65 |
| 66 for col in range(num_cols - 1, 0 - 1, -1): |
| 67 for r in rows: |
| 68 if not used[col]: |
| 69 del r.patterns[col] |
| 70 |
| 71 |
| 72 def each_index_pair(sequence): |
| 73 """Utility function: Generates each unique index pair in sequence.""" |
| 74 for i in range(0, len(sequence)): |
| 75 for j in range(i + 1, len(sequence)): |
| 76 yield (i, j) |
OLD | NEW |