3 ms·

A bit off-topic, but I have wonder lately if I new language start today, what could be the very best (overall) foundations for it. For example, I read here (ht

by mamcx 10y ago

A bit off-topic, but I have wonder lately if I new language start today, what could be the very best (overall) foundations for it. For example, I read here (https://cr.yp.to/critbit.html https://cr.yp.to/critbit.html) that critbit tries could be a better base structure for a language (ie: like dict and list are for python). So, if we start today, what hash to use? What will be a better default structure (my understanding is that hash-maps is/was the way to go)?

chubot 10y ago
I'm generally a big fan of DJB, but I see a few problems with this scheme. First, it seems like the prefix-free requirement means that the strings can't contain internal NUL bytes. In Python you can store 'a\0' as well as 'a\0b' in a hash table -- how do you handle this with crit-bit trees? Second, in Python, unlike JavaScript, arbitrary types can be hashable. Tuples are hashable. How do you store ('a', 0) and ('b', 1) as keys in a crit-bit tree?
- eutectic 10y ago
  Just store a bit (for a set) at each internal node, denoting whether a string ends there. For a map you also need a value pointer. Hashing keys is also easy: add a pointer to a linked list of key-value pairs to each leaf node. To save space you could even use a flag bit and then a pointer to a single key-value pair, or a linked list in case of collision. Note that you can store tuples directly as the concatenation of their fields; no need to use hashing.
  - socmag 10y ago
    What are you talking about. How do tuples preclude the requirement of a way to hash? That's a very naive way to map using the delimeter of the tuple parts. You might have interior elements that are 10k long.
    - eutectic 10y ago
      And strings can also be long.
- socmag 10y ago
  I'm using Cedar to store arbitrary order preserving tuples. After a lot of perf testing, and that library along with others had the same issue with not allowing null bytes. Initially i thought it was a deal breaker, especially since I needed to preserve order. Ended up doing a possibly mutating prepass on any keys keys that might contain nulls (Which is generally very fast O(len(key)) before storing, to rewrite without them. It was still worth it.

by mamcx 10y ago

chubot 10y ago

I'm generally a big fan of DJB, but I see a few problems with this scheme. First, it seems like the prefix-free requirement means that the strings can't contain internal NUL bytes. In Python you can store 'a\0' as well as 'a\0b' in a hash table -- how do you handle this with crit-bit trees? Second, in Python, unlike JavaScript, arbitrary types can be hashable. Tuples are hashable. How do you store ('a', 0) and ('b', 1) as keys in a crit-bit tree?

eutectic 10y ago
Just store a bit (for a set) at each internal node, denoting whether a string ends there. For a map you also need a value pointer. Hashing keys is also easy: add a pointer to a linked list of key-value pairs to each leaf node. To save space you could even use a flag bit and then a pointer to a single key-value pair, or a linked list in case of collision. Note that you can store tuples directly as the concatenation of their fields; no need to use hashing.
- socmag 10y ago
  What are you talking about. How do tuples preclude the requirement of a way to hash? That's a very naive way to map using the delimeter of the tuple parts. You might have interior elements that are 10k long.
  - eutectic 10y ago
    And strings can also be long.
socmag 10y ago
I'm using Cedar to store arbitrary order preserving tuples. After a lot of perf testing, and that library along with others had the same issue with not allowing null bytes. Initially i thought it was a deal breaker, especially since I needed to preserve order. Ended up doing a possibly mutating prepass on any keys keys that might contain nulls (Which is generally very fast O(len(key)) before storing, to rewrite without them. It was still worth it.