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

41–50 of 299 posts

Re: Computer scientists invent an efficient new way to count

#41

Post by coldtea »

wmwragg wrote: post #12
akamoonknight wrote: post #9

I don't know a word or phrase for this, but I really enjoy any examples of "thinking outside the box" like this because it's something I struggle with in my professional career. Learning not only the right ways to solve problems, but figuring out the questions to ask that make solving the problems you have easier or even in some cases possible. In this case, it's hey, we don't need exact numbers if we can define a pr…

I think it's generally thought of as "lateral thinking", Edward de Bono has written a few books about it you might find interesting.

And some more commonplace words like "creativity" (as in "creative solution") etc. would apply.

Re: Computer scientists invent an efficient new way to count

#42

Post by biscuit1v9 »

HDThoreaun wrote: post #19
biscuit1v9 wrote: post #7

> The trick, he said, is to rely on randomization. > When the space is full, press pause and flip a coin for each word. Heads, and the word stays on the list; tails, and you delete it. I wasn't expecting to go that far: randomization. How can you verify if the answer is good? Only approximation, maybe..

Yes, the result is an estimation.

Thanks. Just wanted to be sure I didn't misunderstood.

Re: Computer scientists invent an efficient new way to count

#47

Post by swores »

usgroup wrote: post #22

I found the paper took about as long to read as the blog post and is more informative: https://arxiv.org/pdf/2301.10191 It is about estimating the cardinality of a set of elements derived from a stream. The algorithm is so simple, you can code it and play with it whilst you read the paper. The authors are explicit about the target audience and purpose for the algorithm: undergraduates and textbooks.

> "The authors are explicit about the target audience and purpose for the algorithm: undergraduates and textbooks."

If you're saying it's just for "undergraduates and textbooks", as opposed to just being simple enough for them to use but not limited to them, would you mind explaining what makes it useful for undergrads but not for professionals?

Re: Computer scientists invent an efficient new way to count

#48

Post by gh0stcloud »

very interesting solution. A perfect example of how even some very complicated problems can sometimes have simple solutions. Will definitely try to write an implementation of this.

The only minor downside to this is that it's obviously not deterministic since it depends on chance. But for many applications where the dataset is so big it doesn't fit in memory, that's probably just a tiny rounding error anyway.

Re: Computer scientists invent an efficient new way to count

#49

Post by cubefox »

pmontra wrote: post #5
imoverclocked wrote: post #3

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

Yes, even the subtile states "a simple algorithm for estimating large numbers of distinct objects".

This doesn't excuse the title though.

Re: Computer scientists invent an efficient new way to count

#50

Post by jangxx »

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 the "normal" approach mentioned in the article. It works of course, but requires memory to store each unique element (or their hashes). If you have less memory available, the described algorithm can still give a very good approximation.
Post reply on HN