cli-table / cli-table3

Pretty unicode tables for the command line
MIT License
527 stars 44 forks source link

Refactored table layouts + Layout fix for #269 #278

Closed speedytwenty closed 2 years ago

speedytwenty commented 2 years ago

Been attempting to ensure support for all varieties of table-layouts as well as reducing the time-complexity. This PR will solve #269 as well as open the door to supporting larger datasets and faster rendering.

Previously, when layout is being calculated, for each cell in the table it would traverse all cells that had come before it. It was not able to detect rowSpans left-wards beyond the immediate left. Not sure how to express this mathematically, but the time-complexity is/was exponential.

With this refactored table layout, the time-complexity is mostly reduced to match the complexity of the table.

The first commit includes failing tests. One specifically for #269 and one generally that demonstrates an advanced implementation of rowSpan and colSpan.

speedytwenty commented 2 years ago

To briefly describe the refactored layout calculation mechanism (layoutTable()), it essentially allocates columns for rowSpans exceeding 1. I guess pseudo-code may best describe it concisely:

function next(columnNumber) {
  if (columnNumber is allocated) return next(columnNumber + 1);
  return columnNumber;
}
table.forEach((row) => {
  row.forEach((cell) => {
    cell.x = next(currentColumn); // tracking of "currentColumn" not shown here
    if (cell.rowSpan > 1) allocate cell.rowSpan by cell.colSpan;
  });
  decrement all allocated columns by 1
});
speedytwenty commented 2 years ago

Here are some benchmarks that demonstrate a pretty substantial improvement in rendering performance:

5k cells

1,000 rows X 5 columns

before: 302.522ms after: 169.297ms

50k cells

10,000 rows X 5 columns

before: 18.401s after: 6.055s

100k cells

10,000 rows X 10 columns

before: 1:12.584 (m:ss.mmm) after: 22.489s

speedytwenty commented 2 years ago

While there is still some refactoring left to do to enhance performance (#68, #285), this PR solves a bug as well as adds a test that demonstrates a really complex layout. To attempt to minimize confusion with continued refactoring and to get this fix out into the wild, I'm merging this now. Enjoy!