Bug 58651 - Replace all O(N^2) usage of getting merged regions on a sheet
Summary: Replace all O(N^2) usage of getting merged regions on a sheet
Status: RESOLVED FIXED
Alias: None
Product: POI
Classification: Unclassified
Component: SS Common (show other bugs)
Version: 3.14-dev
Hardware: PC All
: P2 enhancement (vote)
Target Milestone: ---
Assignee: POI Developers List
URL:
Keywords:
Depends on: 57893
Blocks:
  Show dependency tree
 
Reported: 2015-11-25 11:35 UTC by Javen O'Neal
Modified: 2015-11-25 11:50 UTC (History)
0 users


Attachments
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Javen O'Neal 2015-11-25 11:35:05 UTC 
Sheet.getMergedRegions() was added in POI 3.13 for bug 57893, which has O(n) running time. Prior to this, functions used a for-loop around Sheet.getMergedRegion(i), which had poor performance on both HSSF and XSSF.

SheetUtil and perhaps other files haven't been updated yet to use the more efficient code.
Comment 1 Javen O'Neal 2015-11-25 11:50:07 UTC 
Correction: only XSSF had an O(N^2) cost using [Sheet.getMergedRegion(i) for i in range(Sheet.getNumMergedRegions())]. HSSF internally stores merged regions as a list,

Added in r1716362.

This change is internal to POI and shouldn't affect users of POI.