News for hackers. Stuff that matters.
Re:Sorted Integer Compression by raphlinus on Friday June 18, 2021 @12:42PM (#27552226)
There are a bunch of ways to do this. One of the more straightforward is to use a temporary buffer big enough to hold both the new values and the existing stream, and start by shifting the existing stream to be right aligned (using memmove or the equivalent). Then read bits from the old stream while writing bits into the new stream. Using Elias-Fano coding (which I believe is an instance of Golomb coding), the write position will never overtake the read position, so the merge can be done in-place.
Re:Sorted Integer Compression by GistNoesis on Friday June 18, 2021 @02:27PM (#27553328)
Thanks. I think I understood it now : https://news.ycombinator.com/item?id=27553076

In my solution though when the extra temporary buffer is very small,in the worst case, we need to make sizeof(compressedStream)/sizeof(temporaryBuffer) memmove which can potentially make the algorithm quadratic.