Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Computer scientists invent an efficient new way to count

quantamagazine.org

Post reply on HN
Print view View original

51–60 of 299 posts

Re: Computer scientists invent an efficient new way to count

#51

Post by xwolfi »

drycabinet wrote: post #45

Does finding the number of unique elements in a set actually require comparison of each element with everything else? Can't you use a hashtable? For every element, add it to the table (ignore if already exists), and finally, take a count of keys.

Imagine a million elements. How big must your hashtable be ? The article explains it very well, did you miss it ? It's a way to save memory.

But to be honest I implemented it, ran it on Hamlet, and it's very wrong, it's barely useful but maybe if you just need a vague idea...

Re: Computer scientists invent an efficient new way to count

#53

Post by theginger »

drycabinet wrote: post #45

Does finding the number of unique elements in a set actually require comparison of each element with everything else? Can't you use a hashtable? For every element, add it to the table (ignore if already exists), and finally, take a count of keys.

That is fine when you have say 1 million values and only 1000 are unique. But when you have 1 million values and about 900 thousand are unique you are putting more or less the whole data set into memory.

Re: Computer scientists invent an efficient new way to count

#55

Post by vanderZwan »

kibibu wrote: post #36
vanderZwan wrote: post #30

Earlier quoted context omitted.

If you refer to the subtitle of the paper - An Algorithm for the (Text) Book - I think that is actually a reference to something *Paul Erdos allegedly said about some proofs are so elegant in their simplicity and beauty that they are "from The Book", like representing some divine Platonic ideal. Given that Knuth himself reviewed it, he might have remarked that this was one of those algorithms! Perhaps the authors dec…

I thought The Book was an Erdos thing. I wonder who used it first.

I think you're right, I must have confused the two. I'll edit my comment to reduce the spread of misinformation.

Re: Computer scientists invent an efficient new way to count

#56

Post by Anduia »

drycabinet wrote: post #45

Does finding the number of unique elements in a set actually require comparison of each element with everything else? Can't you use a hashtable? For every element, add it to the table (ignore if already exists), and finally, take a count of keys.

Using a hashtable is effective because you only compare elements within their hash buckets, not the entire set. However, they can become inefficient with very large datasets due to memory usage and processing time, which is where approximate counts shine.

Re: Computer scientists invent an efficient new way to count

#57

Post by coldtea »

dist-epoch wrote: post #54
coldtea wrote: post #44

Earlier quoted context omitted.

No, and Taleb is not relevant for this.

It is if the distribution is extreme.

If Hamlet was 100000000 times the word Hamlet and 1 time the word pancake, it would still give an good estimate measurement - even if pancake gets 0.

Re: Computer scientists invent an efficient new way to count

#58

Post by rep_lodsb »

>What if you’re Facebook, and you want to count the number of distinct users who log in each day, even if some of them log in from multiple devices and at multiple times?

Seems like a bad example of when this algorithm could be useful in practice.

If you already know you will want this info when designing the login process, it's simple: keep track of the date of last login for each account, and increment the unique user counter when the stored value is different from the current one.

And even if not, it should still be possible to "replay" a stream of login events from the database later to do this analysis. Unless maybe you already had years worth of data?

Re: Computer scientists invent an efficient new way to count

#59

Post by BlackFly »

imoverclocked wrote: post #3

When do we stop calling this counting and start calling it estimation?

When it is actually impossible to count something and when the error between estimation and an exact answer is not significant the pedantic distinction is not helpful.

The same thing happens with measurement. No measurement is ever exact. If I said I was measuring a count, someone would probably correct to say that I am counting.

Common speech is like that.

Post reply on HN