Combine contiguous spreadsheet cell references into larger ranges

Question

For a hobby project, I am using openpyxl to export Excel workbooks as JSON. Part of this involves identifying the formatting applied to cells, and serializing this information (provided the format is not the default - no need to export that). To minimize the output JSON filesize, it is sensible to report the cells that use a given formatting scheme in the largest range notation possible, rather than individually listing cells:

"format": { some format spec },
"ranges": [
  "A1:Z3000",
  "AB4"
]

instead of

"format": { some format spec },
"ranges": [
  "A1",
  "A2",
  ...
  "Z3000",
  "AB4"
]

The code I wrote to do this is as follows:

def collapse_cellranges(ranges: list):
    '''Attempt to combine the given CellRanges. Recursive, since a grown range
    may not be combinable with the constituents of the next range until that
    range has been processed too'''
    start_count = len(ranges)

    i = 0
    working_count = start_count
    while i < working_count:
        rg = ranges[i]
        j = 1
        reassign = False
        # Iterate a slice (as we modify the original)
        for other in ranges[i + 1:]:
            if range_is_adjacent(rg, other):
                rg = rg.union(other)
                reassign = True
                ranges.pop(i + j)
                working_count -= 1
            else:
                j += 1
        # Reassign only once per range, no matter how many were joined.
        if reassign:
            ranges[i] = rg
        i += 1

    if working_count < start_count and working_count > 1:
        collapse_cellranges(ranges)
    else:
        return

The adjacency calculation:

def range_is_adjacent(range, other: CellRange):
    '''Determine if the given range is adjacent to the given CellRange.
    Returns True if joining the range with the CellRange would increase
    only its row span or column span.'''
    if isinstance(range, CellRange):
        if other.issuperset(range):
            return False
        min_col, min_row, max_col, max_row = range.bounds
    else:
        if isinstance(range, Cell):
            min_col = max_col = range.col_idx
            min_row = max_row = range.row
        elif isinstance(range, str):
            min_col, min_row, max_col, max_row = range_boundaries(range)
        if other.issuperset(CellRange(None, min_col, min_row, max_col, max_row)):
            return False

    r_min_col, r_min_row, r_max_col, r_max_row = other.bounds
    if min_col == r_min_col and max_col == r_max_col:
        # Columns aligned, require bordering maxs to mins
        return (max_row + 1 == r_min_row
                or min_row - 1 == r_max_row)
    elif min_row == r_min_row and max_row == r_max_row:
        # Rows aligned, require bordering maxs to mins
        return (max_col + 1 == r_min_col
                or min_col - 1 == r_max_col)
    return False

Definitions for bounds, union, and issuperset are available in the openpyxl source - they're pretty cheap computationally.

For smaller ranges, it works very well. However, on larger ranges where a lot of the ranges are contiguous (i.e. unionable), the performance is atrocious:

2018-11-02 10:55:13,943 Collapsing 1793 ranges for number_format: Accounting
2018-11-02 10:55:14,381 Combined 1793 ranges into 212, recursing to try again
2018-11-02 10:55:14,391 Combined 212 ranges into 24, recursing to try again
2018-11-02 10:57:28,691 Collapsing 510998 ranges for number_format: Accounting
2018-11-02 15:23:09,622 Combined 510998 ranges into 30069, recursing to try again
2018-11-02 15:23:10,711 Combined 30069 ranges into 5, recursing to try again

I logged the progress:

Is there some algorithmic improvement I can use here? 4 hours for just one of these larger regions is not desirable. My first thought is to work backwards through the list, so that there are fewer elements being reindexed with each pop(*some_index*). I could additionally sort the input to ensure ranges with similar starting row (or column) are near other, which would mean the for loop over the slice could exit early (once the top left cells of compared ranges are no longer in the same row or column)

---

Background

Since formatting information is only available as a cell-level parameter in openpyxl (each cell stores an index that points to an instance of the particular formatting object), I iterate through cell regions marked for export (the a1s below) and store the cell address in a dict whose keys are the hashed formatting object. A formatting specifier used in one of the a1s may be used in a different a1 as well, so contents of the list multi_cell_range are not guaranteed to be contiguous. (They are guaranteed to be unique.)

COORD = '{}{}'
result = {}
for a1, params in cell_styles.items(): # params is (dict{str: 2d sequence(str / object)})
    min_c, min_r, _, _ = range_boundaries(a1)
    for style_attr, rg in params.items():
        style_dict = result.setdefault(style_attr, {})
        for r, row in enumerate(rg):
            for c, attr in enumerate(row):
                val = attr if isinstance(attr, str) else attr._StyleProxy__target
                multi_cell_range = style_dict.setdefault(val, [])
                multi_cell_range.append(COORD.format(get_column_letter(c + min_c), r + min_r))

So the above would produce a result dict like

{
  "font": {
    <Font1>: [
      "A1", "B1", "C1", "D1", ...
      "A2", "B2", "C2", "D2", ...
      ...
    ],
    <Font2>: [
      ...
    ]
  },
  "alignment": {
    <Alignment1>: [
      "A1", "A2", "A3" ...
    ],
    <Alignment2>: [
      "B1", "B2", ...
    ]
  ...
}

I then convert each simple multi-cell range list into the MultiCellRange class and "agglomerate" the A1 notations:

for style_attr, style_dict in result.items():
    for key in style_dict:
        mcr = MultiCellRange(style_dict[key])
        collapse_cellranges(mcr.ranges)
        style_dict[key] = mcr

Answer 1

I was able to massively improve the performance by incorporating two changes:

1. Work backwards, to avoid calling pop(some_index) mid-list. For a large list, mid-list pops are nasty.
2. Create a lookup table with the relevant CellRanges to inspect, as a dict keyed by the maximum row. Since I'm walking backwards, I want to be able to easily find all CellRanges that are in a row immediately above the one I'm working with.
   This same key works well for growing within a row, as any eligible CellRanges have to have the same max_row as the one being worked with.

This approach actually entirely obviates the need for a mid-list pop, through the use of a set that stores which CellRanges have been used already. It's possible I could further modify the method to avoid popping.

The new performance graph:

There are considerably more recursions of the same input if the growth steps are not done in reverse (since only the last of the elements in the dict key will match). Adding in a reversal of the elements of cr_dict yields this graph:

With the same input, I can now process ~24,000 CellRange per second immediately (compared to ~15 in the original code).

def collapse_cellranges(ranges: list):
    '''Attempt to combine the given CellRanges. Recursive, since a grown range
    may not be combinable with the constituents of the next range until that
    range has been processed too'''
    start_count = len(ranges)

    # Sort the input, to ensure a logical ordering of the CellRanges.
    ranges.sort(key=cellrange_sort_key)

    # Construct a dict with the relevant information for smart adjacency checks
    cr_dict = {}
    for cr in ranges:
        cr_dict.setdefault(cr.max_row, []).append(cr)
    # Reverse the lists once, rather than using reverse iterators each time.
    for val in cr_dict.values():
      val.reverse()
    # Consume a CellRange only once.
    used = set()

    kept = []
    while ranges:
        # Start from the end, to limit list reindexing.
        rg: CellRange = ranges.pop()
        while ranges and str(rg) in used:
            rg = ranges.pop()
        if str(rg) in used:
            break
        used.add(str(rg))

        # Attempt to grow `rg` horizontally
        row_merge_candidates = cr_dict.get(rg.max_row, [])
        for cr in row_merge_candidates:
            if str(cr) not in used and __range_is_adjacent(rg, cr):
                used.add(str(cr))
                rg = rg.union(cr)

        # Attempt to grow `rg` vertically
        while rg.min_row - 1 in cr_dict:
            grew = False
            col_merge_candidates = cr_dict.get(rg.min_row - 1, [])
            for cr in col_merge_candidates:
                if str(cr) not in used and __range_is_adjacent(rg, cr):
                    used.add(str(cr))
                    rg = rg.union(cr)
                    grew = True
            if not grew:
                break

        kept.append(rg)

    # Add the kept CellRanges back to the input list object.
    for cr in reversed(kept):
        ranges.append(cr)
    # Recurse if needed:
    kept_count = len(kept)
    if kept_count > 1 and kept_count < start_count:
        collapse_cellranges(ranges)
    else:
        return

(The implementation of CellRange as of openpyxl v2.5.9 is not hashable, so str is used to obtain a hashable representation.)