3 ms·
I love little optimizations like this. What I'm reading is that the node in the b-tree remembers the most recently found index during search, and if the next s
by mabbo 5y ago
I love little optimizations like this.
What I'm reading is that the node in the b-tree remembers the most recently found index during search, and if the next search happens to be for the same value or one very close, the binary search goes much faster. This only helps in situations where searches correlated in time tend to have nearby key values, but that's probably very common.
- anonymouse008 5y agoI'm not qualified to truly understand this, but when Lex first interviewed Jim Keller, Jim basically said regarding processor design -- 'yeah, if you just guess the same result as last time, you get a 50% speed increase.' First Interview (where that poorly paraphrased quote resides): https://www.youtube.com/watch?v=Nb2tebYAaOA&t=13s https://www.youtube.com/watch?v=Nb2tebYAaOA&t=13s Second Interview: https://www.youtube.com/watch?v=G4hL5Om4IJ4 https://www.youtube.com/watch?v=G4hL5Om4IJ4
- sitkack 5y agoThe Weather Prediction Algorithm, weather will be the same as yesterday. Only wrong on transitions, very useful when you have runs of the same state. After that you implement a Markov Chain [1] https://en.wikipedia.org/wiki/Markov_chain https://en.wikipedia.org/wiki/Markov_chain