Hacker News Reader

Comment by wimagguc | Hacker News Reader

GitHub's search is pretty interesting: every time I refresh the search page it shows a different number of results: 18,401,830; 17,751,631; 15,995,799.

Which is anyways quite a lot of results, but then this search finds ThisShouldNeverHappenException, the string "this should never happen" and stuff like

    // *This* gets run before every test.
    if (b > d) {
        fail("XX *should never happen*");   
    }

With quotations it's only about 500,000.

View on HN

Usually, you'd never actually _count_ the expected results for such stuff. Instead, you'd return the estimate number of records (think SQL EXPLAIN). I'd gather the number seems very dynamic because of the constant stream of commits.

HyperLogLog[1] will do that. You can find it in Redis, Lucene; and I suspect it is also hidden behind BigQuery's count(distinct X)s.

[1] https://en.wikipedia.org/wiki/HyperLogLog

What part of the algorithm would cause the number to change significantly every time you run the query?

All shards compute their own, and send the result in a non deterministic order. My explanation is that the merge part of HLL depends on the order.

Line 95 of this method [1] from this implementation [2] shows a max(mask(x), mask(y)), which is not associative but is a close proxy to max()(which is associative).

[1] https://github.com/addthis/stream-lib/blob/af045cb4199959c07...

[2] https://github.com/addthis/stream-lib/blob/master/src/main/j...

Trying a quoted "should never happen" yields a bit over 3,000,000 results. Trying a quoted "never happen" yields over 5,000,000 results.

Reply on news.ycombinator.com