logoalt Hacker News

contravariant • today at 1:42 PM • 0 replies • view on HN

I think there's never going to be a point where you can have the kind of performance you can get by optimising a datastructure for a 'fixed' dataset. Nor can you get the maximal performance updating data if you need to maintain a useful datastructure.

A simple case is a sorted list, you can sort it after every update, you can ignore the ordering and sort it as needed, or you can use a datastructure that is typically O(log(N)) at both updates and retrieval. Better datastructurs help, but they cannot remove the tradeoff entirely (in fact O(log(N)) inserts are kind of theoretically minimal, though a trie can do it in O(1) for fixed length datatypes).