Algorithms for loading history file
Posted Jun 1, 2005 0:27 UTC (Wed) by Blaisorblade
In reply to: Fish - The friendly interactive shell
Parent article: Fish - The friendly interactive shell
> The history file takes about a quarter of a second to load 1000 entries, > though. That has to improve.
About this: since this is something smart algorithms can help about (I'm not sure about load time, but at least for search time), I wanted to answer. Have you thought to using a trie (also called radix tree)? It's a tree (not binary) where each word is stored split in characters, with one character at each level. So you store "cat a" and "cat b" in the same tree path, except for the last node:
(representing the tree in horizontal)
<c> -> <a> -> <t> -> < > -> <a> | <b>
This helps a lot searches done from the beginning. The root would be an empty node, having all (used) letters as childs.
Actually this wouldn't help for Ctrl-R searches... a solution I have on top of my head (but which isn't on textbooks, so it's not as studied as the above one) is to have a parallel array who contains all letters, and where each letter points to all occurrences of that letter itself in the main tree. So for "a" you find a list of all "a"'s in the main tree. Sadly, it would be better to have a parallel trie of all "a" in the main tree, but this would be hard (either you restore again the whole trie or you all "a"'s share the descendants, which isn't nice).
If you want, we can discuss this further (even if I'm not a deep expert on this)...
to post comments)