Computer scientists invent a memory-efficient way to estimate the size of a subset
The subset is very important, it is the subset of unique elements.
This is implied by the word "set" in "subset". Otherwise it would've been a multiset.
Computer scientists invent an efficient new way to count
251–260 of 299 posts
Re: Computer scientists invent an efficient new way to count
#252Earlier quoted context omitted.
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.
> 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.
Disagree, there are thousands of highly experienced and hard-working computer scientists. If we grant that very few of them are the equivalent of Knuth, there must be something else at play.
Re: Computer scientists invent an efficient new way to count
#253Am I correct in thinking the accuracy of this method has more to do with the distribution in the sample than the algo itself. Meaning, given a 100% unique list of items, how far off would this estimate be?
I don't think so. I think the point of the removal in
X Re: Computer scientists invent an efficient new way to count
#254This is actually a really sad, redundant example of the regression of education in the United States.
This "sure to be lauded" technique is pretty simple and has been exploited by simpleton gamblers for a very long time.
Its basically simple math disguised as "mentalism".
But since you, "very new to " "the real world" people figure out your folly. I promise I wont laugh. But I am laughing at how incredibly hollowed out the education system of the USA is when a simple compund method for an old trick, substitutes itself for math.
The "math" involved is purely low IQ points on the inventors side.
Re: Computer scientists invent an efficient new way to count
#255Earlier quoted context omitted.
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…
[I am one of the authors]. We have a follow-up work (admittedly, more technical) that can remove reliance on m completely: https://www.cs.toronto.edu/~meel/Papers/pods22.pdf But yes, our theorems can be reworked to estimate the confidence/error rate; that's what Knuth did: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
Didn’t realize you were here so let me be clear that I did overall find the paper so approachable that I could implement it with only a couple of outside pointers (also a little clever impl optimization around storing p if you’re curious). The above should be read more as “even this well-written simplified paper is not necessarily trivial to understand for practicians”. So more of a general point around academic obscurity.
> But yes, our theorems can be reworked to estimate the confidence/error rate
I think that’s useful for practical implications. Also, for practical use, how does one decide the tradeoff between delta and epsilon? Perhaps it’s covered elsewhere, but I have a hard time intuiting their relationship.
Re: Computer scientists invent an efficient new way to count
#256I 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…
What are the main applications of this?
Re: Computer scientists invent an efficient new way to count
#257I jumped on the code generation bandwagon pretty soon after ChatGPT was released. I like to think of similar to a catalyst in a chemical reaction, it lowers the activation barrier to writing code, especially in new contexts (to you). It makes it easier to just get started. However, it struggles with solving actual problems or even putting together the right context. If you know how to break the problem down to simpler steps, it can help with those. It won't write a new kernel driver for you.
Re: Computer scientists invent an efficient new way to count
#258Which books are in background?
Re: Computer scientists invent an efficient new way to count
#259Which books are in the background, I can't read their titles because picture is blurred too much?? Help please !!! :)
Re: Computer scientists invent an efficient new way to count
#260I 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 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 outcome of 100 coin tosses. That concludes Round 1.
It's not just removals you test with N coin flips in Round N, it's whether to insert the new item at all.