Prefix Trees in Action

&gt; Because of that, the first step on the road to fast programs is to measure!<p>&gt; Making an operation that accounts for 1% of the overall runtime 100% faster is far less effective than making something that accounts for 50% of the runtime10% faster.<p>Currently dealing with a slow DB and a team of &quot;engineers&quot; who have just <i>NOT</i> internalized the above. It&#x27;s been very demoralizing.

Thanks for writing this up. I&#x27;m solving a similar problem, albeit different in a few important ways, and was planning on taking a semi-similar approach. Like you, today I&#x27;m using a fairly naive implementation with some less-than-ideal complexity.<p>I&#x27;ve never actually worked with a prefix tree before, so this was quite helpful for me.<p>This may be of interest as well - a related paper, Pigasus, does this with specialized hardware but it&#x27;s a similar problem of applying 10s of thousands of rules as quickly as possible. I found it while reading through acolyer&#x27;s morning paper. <a href="https:&#x2F;&#x2F;blog.acolyer.org&#x2F;2020&#x2F;11&#x2F;16&#x2F;pigasus&#x2F;" rel="nofollow">https:&#x2F;&#x2F;blog.acolyer.org&#x2F;2020&#x2F;11&#x2F;16&#x2F;pigasus&#x2F;</a><p>Again, slightly different task - they wouldn&#x27;t be going for the longest match exclusively, but all matches. Also, the rules they use are fundamentally regular expressions, so the filtering pass is to take advantage of the domain specific knowledge that rule-matches are very rare.

If someone can implement a code analyzer that could suggest such optimizations we could save so many compute cycles. Using tries for such problems is a common solution but may be unknown or overlooked by some. Even trying to search for best practices to a problem you feel has likely been solved many times before can be difficult if you don&#x27;t use the right keywords.

Someone&#x27;s Marketing team forced them to write an article!<p>But yes, tries are very cool.