Skip to content

perf(calc): optimize GridSelectionCalcEngine median calculation with QuickSelect for large selections #603

Description

@ZhuchkaTriplesix

Problem

In lib/features/main_screen/grid_selection_calc_engine.dart, the compute method calculates the median of a multi-cell selection by copying and performing a full (K \log K)$ sort on the entire numericList:

numericList.sort();
final mid = numericCount ~/ 2;
if (numericCount.isOdd) {
  median = numericList[mid];
} else {
  median = (numericList[mid - 1] + numericList[mid]) / 2.0;
}

When selecting tens of thousands of cells across entire columns, full sorting creates unnecessary CPU overhead when only the 50th percentile (median) value is required.

Proposed Solution

  • Introduce a linear-time QuickSelect ((K)$ average time) algorithm for median calculation when the numeric list exceeds a threshold (e.g. > 500$).
  • Keep standard fast sort for small selections ( \le 500$).
  • Add unit tests in grid_selection_calc_engine_test.dart validating median correctness for odd/even selections and benchmark performance.

Metadata

Metadata

Assignees

No one assigned

    Labels

    performanceTheme parser epic label: performance

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions