Improve computational time complexity for printing fill()
#16595
Conversation
This comment was marked as resolved.
This comment was marked as resolved.
| expect(endTime - startTime).toBeLessThan(1000); | ||
| expect(endTime - startTime).toBeLessThan(100); |
There was a problem hiding this comment.
On my machine, it was:
- 181.9 on origin/main
- 13.3 on this branch
It get x10~ faster so dividing by 10 should be safe.
There was a problem hiding this comment.
Repeating the test, 181.9 on origin/main looks to be a bad case. It can be sometimes done in about 100ms.
src/document/printer.js
Outdated
| const remainingCmd = { | ||
| ind, | ||
| mode, | ||
| doc: { ...doc, parts: parts.slice(2) }, |
There was a problem hiding this comment.
Maybe we can simply save the the offset to doc?
There was a problem hiding this comment.
That's right. It looks simpler 681a603.
|
We are printing |
|
Thank you for review! Binary search looks good at the first impression. However, probably it won't improve computational complexity. We have to measure length for each element. If we measure it during binary searh, it will get O(n logn). Reducing measuring cost with cumsum, it will get O(n). Note that though binary search is O(logn), constructing comsum costs O(n). |
Description
Algorithm in
printDocToString()forfill()has quadratic time complexity (existing comment is partially wrong).This PR make it linear (possibly log-linear if I miss some logic. less than quadratic at most).
This will improve some edge cases significantly faster.
For common practical cases, most people will be affected little, probably (time for
yarn testwas almost same on my machine).For users who mainly write languages which tend to use
fill(), like HTML, they will get slightly faster formatting (time foryarn test ./tests/format/htmlget ~5% faster).Checklist
(If changing the API or CLI) I’ve documented the changes I’ve made (in thedocs/directory).changelog_unreleased/*/XXXX.mdfile followingchangelog_unreleased/TEMPLATE.md.✨Try the playground for this PR✨