4 ms·
you're rle-compressing the first differences of the ids (x[n] - x[n-1]) rather than the ids themselves. though maybe only in the special case of a run of 1s
by kragen 2y ago
you're rle-compressing the first differences of the ids (x[n] - x[n-1]) rather than the ids themselves. though maybe only in the special case of a run of 1s
- josephg 2y agoYep, only in the case of runs of 1s - since that’s the predominant case when typing. Runs with other difference values show up when typing in multi-cursor mode in vscode and other editors, but I haven’t optimised my data structure for that use case.
- kragen 2y agoyeah, that seems quite reasonable reversibly transforming a data sequence into a more easily compressible one of the same size (sometimes called 'whitening' or 'predicting') is a very general technique for data compression, and first differences are a very commonly used transformation here. others include the burrows–wheeler transform, paeth prediction, and linear predictive coding
- josephg 2y agoI didn't know that had a name! Thanks - time to do some reading.