I don't know why, but this function implementation really makes me happy. It took me way too long to get it right, but it's just perfect now :D - ThreadSky

creationix.blue • 84 days ago

I don't know why, but this function implementation really makes me happy.

It took me way too long to get it right, but it's just perfect now :D

Comments

benlesh.bsky.social•84 days ago

I’m not familiar with the algorithm. It seems to expect a sorted array to build a flattened, balanced binary tree?

It might be good to give more descriptive variable names for the uninitiated. But I can look up the algorithm.

benlesh.bsky.social•84 days ago

Semi related: I’m doing some art with gliding (silver leaf, though, not gold) and Eytzinger is a manufacturer of materials related to that process.

Strange coincidence.

creationix.blue•84 days ago

I had hoped to use simplified perfect hashes for my indexed map type since it would give O(1) access to maps, but they are very hard to use past about 16 entries.

optimized binary search via eytzinger sorted pointers is trivial to generate and O(log2 n) read which isn't too bad.

creationix.blue•84 days ago

True perfect hashes are rather complex to implement, I need something trivial for this use case so I designed my own.

Basically the idea was to find an xxhash32 seed where all n keys have hashes (mod n) with zero collisions.

Then I store just seed and a list of pointers.

creationix.blue•84 days ago

For my format, I use these indexes for both Set and Map. Set is basically Map, but without any associated values, just keys that are treated as set entries.

I'm tempted to include both the perfect hash and the eytzinger indexes, but O(log2 n) of numbers under 16 is small.

creationix.blue•84 days ago

So I'll probably skip the perfect hash and then implementations are a lot smaller as they don't need xxhash32 at all. It encodes slightly smaller too since I don't need to embed the magic seed with each container.

creationix.blue•84 days ago

So I think my final set of value types are:
- positive integer
- negative integer
- decimal
- reference (null, false, true, ...user-defined)
- pointer (to duplicate values in doc)
- string (utf8)
- bytes
- list
- map
- array (list with simple index)
- ??? (map with eytzinger index)
- set
- chain

creationix.blue•84 days ago

I'm not sure what to name the indexed map, maybe "object" to mirror JavaScript? Before when the index was a HAMT in my previous design, I called this type "trie", but can't do that now.

Any suggestions?

Comments

Posting Rules

Reply