Peter

Come join me for a picnic to celebrate late summer bank holiday (Monday Aug 25th), by the river at Grantchester. About 1pm until we get bored.

Bring general picnic things, anything you're likely to want. I will bring some general things to get us started.

If the weather is hot some people may also swim.

It's past the voting deadline, and I didn't vote in the dramatic presentation long form category, but I'm still trying to watch the shortlisted films.

I'd not seen Dune part one, so watched that and then part two (which was on the shortlist this year). It's one book turned into two lengthy films, and part two has a rubbish ending - we get no sense of Paul becoming Emperor as any kind of triumph before it's undermined by the immediate start of the next war. They are both grand spectacles, but their pacing is odd - at times it seems to be dragging and then key events are rather rushed over (so you're left not really quite understanding what happened without resorting to plot summaries after the fact). And the racial politics have dated poorly, shall we say? And I don't think the whole sandworm ecosystem is even vaguely plausible. But there's some great scheming and some interesting characters (albeit that a lot of the villains are entirely 2-dimensional).

The Wild Robot is an altogether different film, very heavy-handed with its messaging and happy to tug on the heart-strings. The plot doesn't really stand up to scrutiny (robot has access to all human knowledge, but doesn't know how geese swim? etc.), but it's well-animated and has lots of fun moments. And despite being the film of the first book of a trilogy, it actually has a decent ending! But I really struggled to suspend my disbelief because the plot is so full of holes.

https://dotat.at/@/2025-08-06-p-fast-trie.html

Previously, I wrote some sketchy ideas for what I call a p-fast trie, which is basically a wide fan-out variant of an x-fast trie. It allows you to find the longest matching prefix or nearest predecessor or successor of a query string in a set of names in O(log k) time, where k is the key length.

My initial sketch was more complicated and greedy for space than necessary, so here's a simplified revision.

( Read more... )

https://dotat.at/@/2025-08-04-p-fast-trie.html

Here's a sketch of an idea that might or might not be a good idea. Dunno if it's similar to something already described in the literature -- if you know of something, please let me know via the links in the footer!

The gist is to throw away the tree and interior pointers from a qp-trie. Instead, the p-fast trie is stored using a hash map organized into stratified levels, where each level corresponds to a prefix of the key.

Exact-match lookups are normal O(1) hash map lookups. Predecessor / successor searches use binary chop on the length of the key. Where a qp-trie search is O(k), where k is the length of the key, a p-fast trie search is O(log k).

This smaller O(log k) bound is why I call it a "p-fast trie" by analogy with the x-fast trie, which has O(log log N) query time. (The "p" is for popcount.) I'm not sure if this asymptotic improvement is likely to be effective in practice; see my thoughts towards the end of this note.

( Read more... )