# Linearization post-processing (O(n^2) fancy chunking)

**URL:** <https://delvingbitcoin.org/t/linearization-post-processing-o-n-2-fancy-chunking/201>\
**Category:** Implementation\
**Tags:** wg-cluster-mempool\
**Created:** [November 16, 2023, 10:45pm UTC](https://delvingbitcoin.org/t/linearization-post-processing-o-n-2-fancy-chunking/201 "2023-11-16T22:45:48Z")\
**Posts on this page:** 1\
**Showing post:** 6

<div class="post-metadata">

**Author:** ![sipa](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/sipa/32/1100_2.png) [@sipa](https://delvingbitcoin.org/u/sipa)\
**Post date:** [November 17, 2023, 8:28pm UTC](https://delvingbitcoin.org/t/linearization-post-processing-o-n-2-fancy-chunking/201/6 "2023-11-17T20:28:02Z")

</div>

When implemented as a post-processing to linearization, the following also holds:

- It results in decent sub-chunk linearization (for use at the very end of a block when a full chunk no longer fits, though some amount of search, or skipping clusters to find ones with smaller chunks, is likely better).
- When re-running post-processing on an already-post-processed linearization, it runs in \mathcal{O}(n) time (no swaps).

So if there are reasons to keep cluster in linearization format (rather than chunked format), I think it may be reasonable to actually do this post-processing at chunking time, but then also keep the result. This means chunkings always get the quality benefit, but sufficiently trivial re-chunkings stay linear in time.

---

_[View the full topic](https://delvingbitcoin.org/t/linearization-post-processing-o-n-2-fancy-chunking/201)._
