4 ms·
I do something like this in Kyudosudoku[0] to store the undo history in localStorage, but I took it a few steps further than this author as I was pursuing diffe
by Timwi 1y ago
I do something like this in Kyudosudoku[0] to store the undo history in localStorage, but I took it a few steps further than this author as I was pursuing different goals:
* I don't use bit or byte boundaries. If I need to store a field with 11 possible values, I go (n*11) + value. You'd think that would be a performance bottleneck, but it turns out major browsers are hella fast at this, at least when handling the amount of data in one Kyudosudoku undo item, which isn't a lot. The obvious downside is that you can't index into the data, you can only decode the whole thing, but I always want to decode a whole undo item at a time anyway.
* The main goal was for the representation to be as compact as possible so as to fill up as little of the user's localStorage as possible. Using hexadecimal for this is a massive waste. So I try to use the entire range of Unicode characters that are 16 bits in UTF-16 (that's the BMP minus surrogates, but to be safe I avoid the C0 control characters too). (I reserve the space character so that I can concatenate the entire undo history into a single string and still split it apart later without having to decode all of it.) This means I essentially encode the BigInt in base-63453. Again, dividing and moduloing huge numbers by 63453 seems like a performance nightmare, but it looks like modern browsers handle it fine, as the undo/redo feature is perfectly usable.
[0] https://kyudosudoku.timwi.de/ https://kyudosudoku.timwi.de/
- sltkr 1y agoClever, but it seems like you're still encoding states separately. For an undo/redo stack, you can probably do much better spacewise with some sort of delta-encoding, either by explicitly storing the changes made to the grid (or more accurately, the inverse of changes, so you can undo them) or by comparing the new state with the last one whenever saveUndo() is called and storing only the difference.
- Timwi 1y agoThat is true, and I did think about that, but the current implementation is more than adequate for my years of playing Kyudosudoku, so I considered it not worth the implementation effort.
- afiori 1y agoI wonder if it would be worth compressing the bigint as an Uint8Array So app state -> bigint -> bytearray -> compressed bytearray -> bigint -> packed utf16 string. Probably it would but help much