nightcracker

Yes, I am aware it has been 'superseded' but in my experience for lossless compression it's still usually better.

    QOI_DIFF24 {
        u8 tag  :  4;   // b1110
        u8 dr   :  5;   // 5-bit   red channel difference: -15..16
        u8 dg   :  5;   // 5-bit green channel difference: -15..16
        u8 db   :  5;   // 5-bit  blue channel difference: -15..16
        u8 da   :  5;   // 5-bit alpha channel difference: -15..16
    }

It bothers me more than it should that the 5-bit signed differences aren't -16..15 matching two's complement but -15..16 instead.

You could still stream the pixels, you'd just have to stream them in Z order. This may seem pedantic, but this applies to any mismatch between the order in which you store pixels and the order in which the format stores pixels.

E.g. some file formats may be row-major, others column-major, some block-based (like JPEG) or a fancy interleaving scheme (like Adam7). Some might store the channels interleaved, others separate the channels. If any of these choices doesn't match the desired output format, it breaks streaming.

When I download that PNG file it is 10785 KB. If I re-encode it using FLIF 0.4 (to my knowledge still the best off-the-shelf lossless image compression) it is 7368 KB. That's 57% of the size of qoi, quite a lot smaller. You pay for it in encode/decode time though.

Copying the question text verbatim certainly is copyright infringement (and I would guess unlikely to be fair use, but I'm not a lawyer). If you give the problem in your own words, it won't be, just like your solution isn't.

Looking through some of these URLs through Google cache, a lot of these contain verbatim copies of the problem text. Fair enough, legally speaking, if you are the copyright holder.

However, in the DMCA itself HackerRank asks for the removal of entire repositories, claiming "the whole repository is infringing copyright as it contains the solution". This is a blatant lie, HackerRank is not an automatic copyright holder of any solutions to a problem they published.

SlotMap literally cannot, because it must keep track of versions of the used slots, and the slots include the memory space for the data.

DenseSlotMap sort of can. It still can't reclaim the memory used by empty slots for the same reason (at a cost of 8 bytes per slot), but can reclaim the memory used by the actual elements stored.

So if you store 1 million items at one point in a DenseSlotMap, and then clear them all and then shrink to fit (which is actually missing from the API, but I'll fix that soon) you will waste 7.6 megabytes on the empty slots but nothing on the actual data that used to be stored.

This reddit post is such a shame, and I wish people would stop referring to it. The benchmarking code is not apples to apples at all in many places.

E.g. to benchmark removals they used `container.remove(index)` for data structures that support indices but for slotmap they used `slotmap.remove(keys[index])` which unfairly adds another layer of indirection.

There is no fragmentation whatsoever in the traditional sense (unusable gaps left due to size mismatches), because a slotmap only stores a single type of value. Thus every slot is interchangeable and memory can always be reused.

For iteration however, there can be holes that need to be ignored, if the current number of elements in the slotmap is significantly lower than the the maximum capacity. If iteration needs to be very fast (for e.g. game engines) I do have a solution for that, which is the DenseSlotMap. It uses one extra layer of indirection for random access, but stores the actual data values contiguously in a vector, thus iteration is always fast.

Hi, author of slotmap here if anyone has any questions.

Slotmap is essentially the Vec + indices solution, while allowing memory to be reused. It is still completely safe, as it automatically versions each slot, and checks the version contained in the key when indexing.

> It's not hard being faster than zip if you are not compressing/uncompressing

Actually, since CPUs are so fast and disk IO is so slow, it is essentially impossible to beat a properly tuned program that reads data from disk and decompresses it on the fly using one that doesn't use compression at all.

If a significant amount of your new customers find your physical shop through Google maps, what can you do? If someone wants to find a hardware store near them, good chance they'll just write "hardware store" on Google maps. The entry point of people's search is Google - you've already lost the game before it ever started.

I did miss that, oops. That said, it's again unclear if that curve is pre- or post- biased sampling. If it is on the original data it is quite good, but with a heavy biased sample fairly meaningless.