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

221–230 of 299 posts

Re: Computer scientists invent an efficient new way to count

#221

Post by jameshart »

seadan83 wrote: post #201
jameshart wrote: post #99

Earlier quoted context omitted.

It’s not a fundamental difference, it’s a fundamental constraint. There are circumstances - and in real life those circumstances are very common - where you must accept that getting an exactly correct answer is not realistic. Yet nonetheless you want to ‘count’ things anyway. We still call procedures for counting things under those circumstances ‘counting’. The constraints on this problem (insufficient memory to reme…

Counting and estimation are different by definition. One is a full enumeration, the latter an extrapolation from sampled data. In both cases 'accuracy' is a factor. Even if we are counting the number of stars, it is still a difference of technique compared to estimating the number if stars. I could try to count fibers in muscle or grains of sand in the beach, chances are accuracy would be low. One can be smart about…

And by that definition this is a counting algorithm.

Re: Computer scientists invent an efficient new way to count

#222

Post by zero_k »

sesteel wrote: post #216
zero_k wrote: post #178

I was involved with implementing the DNF volume counting version of this with the authors. You can see my blog post of it here: https://www.msoos.org/2023/09/pepin-our-probabilistic-approx... And the code here: https://github.com/meelgroup/pepin Often, 30% of the time is spent in IO of reading the file, that's how incredibly fast this algorithm is. Crazy stuff. BTW, Knuth contributed to the algo, Knuths' notes: https…

Maybe you'd know, but why would one choose to not sort favoring larger counts and drop the bottom half when full? It may be obvious to others, but I'd be curious.

The guarantees would not hold, I'm pretty sure ;) Maybe one of the authors could chip in, but my hunch is that with that you could actually introduce arbitrarily large errors. The beauty of this algorithm really is its simplicity. Of course, simple is.. not always easy. This absolute masterpiece by Knuth should demonstrate this quite well:

https://www.sciencedirect.com/science/article/pii/0022000078...

It's an absolutely trivial algorithm. Its average-case analysis is ridiculously hard. Hence why I think this whole Ordo obsessions needs to be refined -- worst case complexity has often little to do with real-world behavior.

Re: Computer scientists invent an efficient new way to count

#223

Post by naijaboiler »

seadan83 wrote: post #201
jameshart wrote: post #99

Earlier quoted context omitted.

It’s not a fundamental difference, it’s a fundamental constraint. There are circumstances - and in real life those circumstances are very common - where you must accept that getting an exactly correct answer is not realistic. Yet nonetheless you want to ‘count’ things anyway. We still call procedures for counting things under those circumstances ‘counting’. The constraints on this problem (insufficient memory to reme…

Counting and estimation are different by definition. One is a full enumeration, the latter an extrapolation from sampled data. In both cases 'accuracy' is a factor. Even if we are counting the number of stars, it is still a difference of technique compared to estimating the number if stars. I could try to count fibers in muscle or grains of sand in the beach, chances are accuracy would be low. One can be smart about…

They are not really as far apart a you think. At small numbers, yes get are distinct. At large enough numbers, they in all practicality the same thing. E.g what’s the population of the US

Re: Computer scientists invent an efficient new way to count

#224

Post by abootstrapper »

mudiadamz wrote: post #102

Python implementation: def streaming_algorithm(A, epsilon, delta): # Initialize parameters p = 1 X = set() thresh = math.ceil((12 / epsilon ** 2) * math.log(8 * len(A) / delta)) # Process the stream for ai in A: if ai in X: X.remove(ai) if random.random() = 0.5} p /= 2 if len(X) == thresh: return '⊥' return len(X) / p # Example usage A = [1, 2, 3, 1, 2, 3] epsilon = 0.1 delta = 0.01 output = streaming_algorithm(A, ep…

New leetcode hard question just dropped.

Re: Computer scientists invent an efficient new way to count

#225

Post by wmwragg »

bzuker wrote: post #95
wmwragg wrote: post #12

Earlier quoted context omitted.

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

any particular one you'd recommend?

I think the classic is "Lateral Thinking: A Textbook of Creativity"

Re: Computer scientists invent an efficient new way to count

#226

Post by klabb3 »

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.

It's been a while, and maybe my brain has smoothened since my time in CS, but man this looks more confusing than it needs to be.

First, the contradiction thing. It's just.. An error/panic, why? Anyway, fine.

Then, there's the whole premise of 1..m: I'm still not sure if the size needs to be known upfront or not. Looking at it a bit more, it seems like no you don't. You pick a threshold, and then depending on the size of the stream the probability changes. But the algorithm is described as if it had a single output, which is not the case(?).

And btw, I didn't know about the Chernoff bounds and delta/epsilon are not explained at all in the paper, which added to the confusion a lot.

Anyway, here's my take in Golang: https://github.com/betamos/distinct

I factored out the threshold parts into a helper instead, which makes a lot more sense than accidentally allocating too much memory.

Perhaps there should be a method for estimating the confidence/error rate. Nobody knows the size of a stream upfront, so it would make more sense to update these values as you go. Brain is not strong enough to implement it, but feel free to send a PR.

Re: Computer scientists invent an efficient new way to count

#227

Post by reichstein »

reichstein wrote: post #197
renonce wrote: post #73

At first find this paragraph confusing: > Keep going through Hamlet, adding new words as you go. If you come to a word that’s already on your list, flip a coin again. If it’s tails, delete the word; heads, and the word stays on the list. Why would you delete the word already on the list by flipping coins? Doesn't this reduce the accuracy by counting less words than expected? And will the word be added to the list lat…

The way I'd describe it is: - You have a buffer. You initially try to fit every unique word on there. - If the buffer gets full, you know that you can't fit all the unique words in there. So you decide to keep only a fraction, _p1_, of them. Run through the buffer, keep each value with probability _p1_. - Keep adding new words, again only with probability _p1_. - If the buffer gets full again, _p1_ was too large, so…

And I got it. When the algorithm sees a word that is already in the list, it discards the word in the list first. Then it adds the word again with the same probability as any other word. This ensures that only the last occurrence of each word can occur in the final list, so the final occurrence of each word are all in the final list with the same probability, and prior occurrences are always removed, if no earlier then when the next occurrence is seen.

If the input is known to be large, there is no reason to start by adding every element. It can treat the first round like any other, and start out with a _p0_ that is smaller than 1.

Re: Computer scientists invent an efficient new way to count

#228

Post by YoshiRulz »

Koshkin wrote: post #199
melq wrote: post #24

Estimating the amount of unique elements in a set and counting the amount of unique elements in a set are very different things. Cool method, bad headline.

True - for (relatively) small numbers. For large (huge) numbers estimation is usually considered to be equivalent to counting, and the result is sometimes represented using the "scientific" notation (i.e. "floating-point") rather than as an integer. For example, the mole is an integer whose value is only known approximately (and no one cares about the exact value anyway).

As of May 2019, the mole has an exact value, and Carbon-12's molar mass is the empirically-determined value.

Re: Computer scientists invent an efficient new way to count

#229

Post by lokar »

sesteel wrote: post #216
zero_k wrote: post #178

I was involved with implementing the DNF volume counting version of this with the authors. You can see my blog post of it here: https://www.msoos.org/2023/09/pepin-our-probabilistic-approx... And the code here: https://github.com/meelgroup/pepin Often, 30% of the time is spent in IO of reading the file, that's how incredibly fast this algorithm is. Crazy stuff. BTW, Knuth contributed to the algo, Knuths' notes: https…

Maybe you'd know, but why would one choose to not sort favoring larger counts and drop the bottom half when full? It may be obvious to others, but I'd be curious.

You want every distinct item to have the same chance at the end. So when items repeat you need to reduce (not increase) the odds of keeping any given occurrence.

Re: Computer scientists invent an efficient new way to count

#230

Post by throw10920 »

gspetr wrote: post #210
almostgotcaught wrote: post #205

Earlier quoted context omitted.

> He recognized patterns in minutes that would take me days, if not weeks, to recognize... he actually writes and runs code, overnight if need be 70-80 years of actually being hands-on and i bet you'd be pretty quick too. dude is definitely naturally "gifted" but it seems pretty obvious being hands-on has a lot to do with it.

Experience and age have diminishing returns. Biden's been hands-on in his domain for over 50 years, yet "quick" is definitely not the word that comes to most people's mind when they think of him nowadays.

> Biden's been hands-on in his domain for over 50 years, yet "quick" is definitely not the word that comes to most people's mind when they think of him nowadays.

Please don't post flamebaity political tangents on HN.

> Eschew flamebait. Avoid generic tangents.

https://news.ycombinator.com/newsguidelines.html

Post reply on HN