The title is misleading. This is about probabilistic counting, therefore about estimation. It is not clear if the efficiency benefit extends to exact counting. Counting and estimation are not the same concepts.
Computer scientists invent an efficient new way to count
191–200 of 299 posts
Re: Computer scientists invent an efficient new way to count
#192Earlier quoted context omitted.
But for this algorithm, you need to know the total length ("m") to set the threshold for the register purges. Does it still work if you update m as you go?
You actually don't need to do that part in the algorithm. If you don't know the length of the list, you can just choose a threshold that seems reasonable and calculate the margin of error after you're done processing. (or i guess at whatever checkpoints you want if it's continuous) In this example, they have the length of the list and choose the threshold to give them a desired margin of error.
Re: Computer scientists invent an efficient new way to count
#193Earlier quoted context omitted.
That's not streaming if you're already aware of the length of the iterable.
In python, you can simply substitute `A` with an iterable or generator object, which can be a of unknown length.
I know that. See: https://news.ycombinator.com/item?id=40390192
Re: Computer scientists invent an efficient new way to count
#194Earlier quoted context omitted.
In python, you can simply substitute `A` with an iterable or generator object, which can be a of unknown length.
But for this algorithm, you need to know the total length ("m") to set the threshold for the register purges. Does it still work if you update m as you go?
Besides the ideas from istjohn, empath-nirvana, and rcarmo, you can also just "flip the script": solve for epsilon and report that as 1-delta confidence interval for the worst case data distribution as here: https://news.ycombinator.com/item?id=40388878
Best case error is of course zero, but if you look at my output then you will see as I did that the worst case is a very conservative bound (i.e. 15X bigger than what might "tend to happen". That matters a lot for "space usage" since the error =~ 1/sqrt(space) implying you need a lot more space for lower errors. 15^2 = 225X more space. Space optimization is usually well attended for this kind of problem. And, hey, maybe you know something about the input data distribution?
So, in addition to the worst case bound, average case errors under various distributional scenarios would be very interesting. Or even better "measuring as you go" enough distributional meta data to get a tighter error bound. That latter starts to sound like it's one of Knuth's Hard Questions Which if You Solve He'll Sign your PhD Thesis territory, though. Maybe a starting point would be some kind of online entropy(distribution) estimation, perhaps inspired by https://arxiv.org/abs/2105.07408 . And sure, maybe you need to bound the error ahead of time instead of inspecting it at any point in the stream.
Re: Computer scientists invent an efficient new way to count
#195The title is misleading. This is about probabilistic counting, therefore about estimation. It is not clear if the efficiency benefit extends to exact counting. Counting and estimation are not the same concepts.
Obviously it wouldn’t
Re: Computer scientists invent an efficient new way to count
#196I 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…
That’s really interesting and thanks for sharing. I am very curious about the extraordinarily gifted. What made you think Knuth is crazy good? Was there a particularly moment? Was it how fast he groked ideas? Was it his ability to ELI5?
What made me realize is that I saw some snippets of emails he wrote to a colleague. It was... insane. You could see his mind race. He recognized patterns in minutes that would take me days, if not weeks, to recognize. Also, he actually writes and runs code, overnight if need be. It was as bit of a shock to me. He's not in an ivory tower. He's very much hands on, and when he's behind the wheel, you're in for a ride.
Re: Computer scientists invent an efficient new way to count
#197At 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 you choose a lower fraction, _p2_, retain existing elements only with probability _p2_/_p1_, and continue adding new words with probability _p2_. - Every time the buffer gets full, you lower the faction of words you try to retain.
The choice of using _pn_ = (1/2)^n is just easy for a computer, it only needs entire random bits at each step.
What I _don't_ get is how this is correct for counting unique words. If I have a text of 16384 unique words, then I can accept that each will be in the final list with the same probability. But if I take that list and repeat the last word 30000 times, then it becomes overwhelmingly plausible that that word is in the final list, even though I haven't changed the number of unique words. Maybe there is some statistical property that evens things out, but I couldn't see it from the article.
Re: Computer scientists invent an efficient new way to count
#198I 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…
So now we have you to blame for a delay on the release of his next book. :)
Re: Computer scientists invent an efficient new way to count
#199Estimating 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).
Re: Computer scientists invent an efficient new way to count
#200Earlier quoted context omitted.
That’s really interesting and thanks for sharing. I am very curious about the extraordinarily gifted. What made you think Knuth is crazy good? Was there a particularly moment? Was it how fast he groked ideas? Was it his ability to ELI5?
What made me realize is that I saw some snippets of emails he wrote to a colleague. It was... insane. You could see his mind race. He recognized patterns in minutes that would take me days, if not weeks, to recognize. Also, he actually writes and runs code, overnight if need be. It was as bit of a shock to me. He's not in an ivory tower. He's very much hands on, and when he's behind the wheel, you're in for a ride.
I feel extremely jealous of you.