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

291–299 of 299 posts

Re: Computer scientists invent an efficient new way to count

#291

Post by patrick451 »

modriano wrote: post #284
willy_k wrote: post #268

Earlier quoted context omitted.

He’s barely able to read a teleprompter, not too confident that Biden himself enacted those changes.

We've had nearly 4 years with no scandals and emerged from the pandemic with the best economic recovery of any country, and despite having no margin to spare in Congress, master legislator Joe Biden has secured massive climate change, infrastructure, and gun control bills, not to mention he's ended our two decade war in Afghanistan and overseen the fastest wage growth of the two lowest income quintiles seen in modern…

> We've had nearly 4 years with no scandals

This isn't the flex you think it is. When the media is lapping out of your hand like a 6 week old puppy instead of doing their fifth estate job, of course there are no scandals.

> and gun control bills,

You mean stripping Americans of their constitutional rights.

> not to mention he's ended our two decade war in Afghanistan.

Which was an unmitigated disaster.

> and overseen the fastest wage growth of the two lowest income quintiles seen in modern history.

Hello inflation.

Re: Computer scientists invent an efficient new way to count

#292

Post by vanderZwan »

gnfargbl wrote: post #250
vanderZwan wrote: post #107

Earlier quoted context omitted.

> the top-k items in a stream Hmm, this is phrased in a way that sounds different (to my ears) than the abstract, which says: > it is often desirable to identify from a very long sequence of symbols (or tuples, or packets) coming from a large alphabet those symbols whose frequency is above a given threshold Your description suggests a finding fixed nr of k items, with the guarantee that it will be the top ones. The a…

It's been a while since I used this in anger, but my recollection is that it maintains a fixed-size set of items. The same algorithm is in section 3.2 of https://erikdemaine.org/papers/NetworkStats_TR2002/paper.pdf and might be clearer there.

Thank you, that is much easier to follow indeed! Very elegant, I agree :)

Re: Computer scientists invent an efficient new way to count

#293

Post by Levitz »

sangnoir wrote: post #167
Levitz wrote: post #146

Earlier quoted context omitted.

I agree with you, but we are talking theory here. The algorithm doesn't count, it estimates. You can make an algorithm that counts, you can make an algorithm that estimates, this is the second.

Estimation is counting with error bars. Frankly, most of what you consider counting in your comment needs error bars - ask anyone who operated an all-cash cash-register how frequently end-of-day reconciliation didn't match the actual cash in the drawer (to the nearest dollar.) The following is a list from my personal experience - of presumably precisely countable things that didn't turn out to be the case: the number…

I think I get your point completely, yet I'm not getting through.

Would you agree that 1+1=2? Or that pi is 3.14159...? These are mathematical truths, but quickly crumble in the real world. One apple plus one apple doesn't just equate to double the apple, no two apples are ever the same to begin with, there are no real perfect circles out there either, there is still value to those mathematical truths in that they make it evident that they are perfectly precise and that it is real world interaction which may bring error into the table.

Re: Computer scientists invent an efficient new way to count

#294

Post by throw10920 »

patrick451 wrote: post #291
modriano wrote: post #284

Earlier quoted context omitted.

We've had nearly 4 years with no scandals and emerged from the pandemic with the best economic recovery of any country, and despite having no margin to spare in Congress, master legislator Joe Biden has secured massive climate change, infrastructure, and gun control bills, not to mention he's ended our two decade war in Afghanistan and overseen the fastest wage growth of the two lowest income quintiles seen in modern…

> We've had nearly 4 years with no scandals This isn't the flex you think it is. When the media is lapping out of your hand like a 6 week old puppy instead of doing their fifth estate job, of course there are no scandals. > and gun control bills, You mean stripping Americans of their constitutional rights. > not to mention he's ended our two decade war in Afghanistan. Which was an unmitigated disaster. > and overseen…

>> and gun control bills

> You mean stripping Americans of their constitutional rights.

Not that I disagree with you, but when posters like modriano engage in political/partisan commentary on HN, I find it more productive to merely downvote and flag their comments rather than replying and getting engaged in a war.

A dead post makes quite the impression, as this sort of political commentary just generally defeats the quality of discourse on HN (which, you must admit, is much better than many other platforms, and I'd like to try to preserve it as long as possible).

Re: Computer scientists invent an efficient new way to count

#296

Post by Paddy3118 »

mpalmer wrote: post #260
resonious wrote: post #76

Earlier quoted context omitted.

The blog post was more than half padding. Good that the algorithm is so simple it's hard to write a full length blog post about it!

And yet the blog post still got it wrong: > Now you move forward with what the team calls Round 1. 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. Proceed in this fashion until you have 100 words on the whiteboard. Then randomly delete about half again, based on the outco…

I originally used Guttenburgh to get Hamlet and coded the Quanta method in Python and it did not work. I then moved to Algorithm 1 in the paper and got Copilot to (mis) convert it to Python and then spent time getting Copilot to admit its mistakes. The resultant code seemed to work but I found the Quanta suggested data of the words of hamlet to be uninspiring as for the calculated theta (max set size before halving), was often from ~50% of the total number of words in hamlet to often more than the words in hamlet. I've yet to investigate theta in more depth...

Re: Computer scientists invent an efficient new way to count

#297

Post by zvr »

jandrese wrote: post #198
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…

So now we have you to blame for a delay on the release of his next book. :)

I am pretty confident that this was not the only problem/algorithm that "distracted" Knuth during the years. You can see that whenever he encounters interesting issues he has no problem pausing the work on TAOCP and pursue other goals.

Re: Computer scientists invent an efficient new way to count

#298

Post by zvr »

rep_lodsb wrote: post #58

>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 u…

No, what you propose needs to "keep track of the date of last login for each account", so you need memory of the size of your user population. The idea is to perform it with much smaller, fixed amount of memory.

Re: Computer scientists invent an efficient new way to count

#299

Post by theo1996 »

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…

This looks dumb....very dumb, am I missing something? This is not counting, its just sampling AND if you want to actually count all the distinct words the memory size used doesnt change in comparison to just counting.
Post reply on HN