Optimizing an algorithm that's quadratic by design

Optimizing an algorithm that's quadratic by design(whatchord.earthmanmuons.com)

25 points by elasticdog 56 days ago | 4 comments

gopalv 53 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 53 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 50 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?

chaoxu 53 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.