Hacker News Reader

I've seen this referred to as the "BBBB problem", as in: "nobody types BBBB into the search box, so it makes no sense to optimize the algorithm so it doesn't have worst-case complexity with repeated characters".

That is, until someone searches for e.g. git conflict markers.

View on HN

At a previous job, I debugged a close relative of that exact problem: sorting list views was very slow when you wanted to sort on a column with very few distinct values in a large table. The culprit was of course a quick sort degenerating to n squared performance.

And pattern-defeating quicksort is one example of a solution to that

Had this problem in xBase (Clipper with NTX indexes): sorting by date but there were many null (empty) dates in that particular column. Added another date column (that was never null) to the index just to provide entropy.

Reply on news.ycombinator.com