Optimizing an algorithm that's quadratic by design

https://whatchord.earthmanmuons.com/articles/chord-ranking-performance.html

by elasticdog • 20 days ago

25 4 20 days ago

whatchord.earthmanmuons.com

chaoxu• 17 days ago

You say hard rules can cause A beats B, B beats C, and C beats A. Is it because hard rules itself can have cycles, or because hard rule and scores together causing cycles? What does tie-breaker even mean here, how does it change the ordering?

Let's ignore tie-breaker. Is it the following abstract problem?

Given a partial order A (the hard rules) and a total order B (the scores). Find a total order C that is an linear extension of A and "agrees" with B the most.

I feel if phrase this way, then there is probably some faster greedy approximation of w/e "agrees" you are thinking about, because w/e you are doing here is also just an approximation of w/e true best you are thinking.

gopalv• 17 days ago

The rule partial order problem seems to be very similar to how Rule engines are optimized for ACL rule application.

Once per candidate, we precompute a bitmask, an integer whose bits flag which rules that candidate is eligible for. For a pair, the bitwise AND of their two masks is exactly the set of rules both are eligible for, and we check only those.

Once I see a bit-mask loop, the next item I pick up is a Karnaugh Map[1] as a way of looking at the rules.

If one side is generally immutable to automatically reorder the generators of the bits (i.e can I turn a 192 bit expression into a 64 bit followed by a 128 bit - if so which bits are important).

The C++ template hacks over this looks a bit like a fastdiv from Lemire.

The specific one where I spent 2+ months optimizing this was the UserAgent matcher with regexes - an extension replacement for the get_browser() in PHP where the goal was to split up the regexes and build a KV Map for it, so that you can run 40+ small regexes instead of looping through 400.

[1] https://en.wikipedia.org/wiki/Karnaugh_map#Don't_cares

somat• 17 days ago

With regards to the user agent matching it reminds me of the time I loaded the full useragent database(the same data php get_browser() uses) into postgres and landed my first 3+ hour query.

  from log join ua_data on log.useragent ~ ua_data.match_exp

It was intractable to indexing (gin can almost do it. using like instead of ~ but gin only works on pure prefix or suffix matches) so I moved on to better things.

alexandermorgan• 14 days ago

Neat article but I don't get two things: 1. if there are "hard rules" that always override the ranking decisions, why not weight them with a score that is greater than the total possible from the other ranking elements. E.g. if the highest possible score is 100, then a hard rule can have a score of 1,000 so it will override the other decisions no matter what. An even more significant hard rule can be worth 10,000. 2. Since only the top 1 really matters, why not do an nlargest type of thing so that you only do n-1 comparisons instead of (n^2 - n)/2 comparisons?

Optimizing an algorithm that's quadratic by design

Related Stories