3 ms·
This is exactly a Succinct Data Structure. The solution proposed by the author doesn't allow random access; that is, you can't access a specific A[i] unless you
by Spoof7726 2y ago
This is exactly a Succinct Data Structure. The solution proposed by the author doesn't allow random access; that is, you can't access a specific A[i] unless you unpack all of them. There is some research (e.g., [1]) allowing random access within reasonable time with slightly more storage, although it is almost entirely of theoretical interest.
[1]: Mihai Patrascu, Succincter, FOCS 2008 best student paper.
- edflsafoiewq 2y agoIt does allow random access. It works like a compressed texture format. Each block of 5 trits compresses to one byte, so you can jump to exactly the relevant byte and unpack only it.
- hinkley 2y agoIf I’m looking for the 3rd position in decimal I ignore everything above and below the third position. Which you can do by taking modulo 1000 and dividing by 100, or dividing by 100 and taking modulo 10, which is easier to calculate in the moment. You don’t need any fixed point math just normal integer floor on division operations. So why would it be different in ternary?
- Spoof7726 2y agoBecause division is not trivial. Even computing x mod 3 for an n-bit integer x is O(n), if x is represented in the binary form.
- chris_va 2y agoYes, nothing here is really new. For inference, trits/sec decoded into L1 cache is a lot more important than random access, and is going to be hardware specific (e.g. what SIMD instructions are available). 8bit seems an odd choice given most available instructions, but the Succincter paper's use of mod and individual decoding is (unless I am misreading it) much slower.
- Spoof7726 2y agoI completely agree. I don’t think the paper is practical either; I shared it only to show that random access is possible in theory.