4 ms·
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 ha
by Tade0 3y ago
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.
- arnsholt 3y agoAt 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.
- kzrdude 3y agoAnd pattern-defeating quicksort is one example of a solution to that
- epx 3y agoHad 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.