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

131–140 of 299 posts

Re: Computer scientists invent an efficient new way to count

#131

Post by Alexanfa »

josephernest wrote: post #124
pytness wrote: post #110

Is it me or is the description of the algo wrong? > 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; If i follow this description of "check if exists in list -> delete": if hash_set.contains(word) { if !keep_a_word(round) { hash_set.remove(word); continue; } } else { hash_set.insert(word.to_string());…

I got the same problem. When implementing the exact method as described in quanta magazine (without looking at the arxiv paper), I always had estimates like 461746372167462146216468796214962164. Then after reading the arxiv paper, I got the the correct estimate, with this code (very close to mudiadamz's comment solution): import numpy as np L = np.random.randint(0, 3900, 30557) print(f"{len(set(L))=}") thresh = 100 p…

Quanta:

    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.
To:

    Round 1. Keep going through Hamlet, but now flipping a coin for each word. If it’s tails, delete the word if it exists; heads, and add the word  if it's not already on the list.
Old edit:

    Round 1. Keep going through Hamlet, adding words but now flipping a coin immediately after adding it. If it’s tails, delete the word; heads, and the word stays on the list.

Re: Computer scientists invent an efficient new way to count

#132

Post by sneva »

ericmcer wrote: post #117
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…

I don't think there is a single variable name or comment in this entire code block that conveys any information. Name stuff well! Especially if you want random strangers to gaze upon your code in wonder.

> Name stuff well

OP is following the same variable names of the article. I prefer that over changing the variable names and then figuring out what variable name maps in code to the article.

Re: Computer scientists invent an efficient new way to count

#133

Post by [deleted] »

josephernest wrote: post #124
pytness wrote: post #110

Is it me or is the description of the algo wrong? > 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; If i follow this description of "check if exists in list -> delete": if hash_set.contains(word) { if !keep_a_word(round) { hash_set.remove(word); continue; } } else { hash_set.insert(word.to_string());…

I got the same problem. When implementing the exact method as described in quanta magazine (without looking at the arxiv paper), I always had estimates like 461746372167462146216468796214962164. Then after reading the arxiv paper, I got the the correct estimate, with this code (very close to mudiadamz's comment solution): import numpy as np L = np.random.randint(0, 3900, 30557) print(f"{len(set(L))=}") thresh = 100 p…

[deleted]

Re: Computer scientists invent an efficient new way to count

#134

Post by jtanderson »

Given the topic of the paper[0], the footnote is especially charming:

> the authors decided to forgo the old convention of alphabetical ordering of authors in favor of a randomized ordering, denoted by r⃝. The publicly verifiable record of the randomization is available at https://www.aeaweb.org/journals/policies/random-author-order...

[0]: https://arxiv.org/pdf/2301.10191

edit: formatting

Re: Computer scientists invent an efficient new way to count

#137

Post by jtanderson »

imglorp wrote: post #128
cb321 wrote: post #91

Earlier quoted context omitted.

I agree the paper is better than the blog post, although one criticism I have of the CVM paper is that it has some termination/algo exit condition instead of what Knuth's CVM notes (refed else-thread here) do which is just a loop to ensure getting more space in the reservoir halving-step. It seems more work to explain the https://en.wikipedia.org/wiki/Up_tack than just do the loop. [1] [1] https://news.ycombinator.co…

On that note, I'm also unfamiliar with this \ operator notation which is used without explanation. X ← X \ {ai}

That is conventional set subtraction notation. "Assign to X the same set minus all elements of the set {a_i}".

One example source, but it is pretty common in general: http://www.mathwords.com/s/set_subtraction.htm

Re: Computer scientists invent an efficient new way to count

#138

Post by rocqua »

imglorp wrote: post #128
cb321 wrote: post #91

Earlier quoted context omitted.

I agree the paper is better than the blog post, although one criticism I have of the CVM paper is that it has some termination/algo exit condition instead of what Knuth's CVM notes (refed else-thread here) do which is just a loop to ensure getting more space in the reservoir halving-step. It seems more work to explain the https://en.wikipedia.org/wiki/Up_tack than just do the loop. [1] [1] https://news.ycombinator.co…

On that note, I'm also unfamiliar with this \ operator notation which is used without explanation. X ← X \ {ai}

Set difference.

Set X becomes X without element ai. This is the case whether ai was in the set X before the step was taken.

Re: Computer scientists invent an efficient new way to count

#139

Post by josephernest »

Alexanfa wrote: post #131
josephernest wrote: post #124

Earlier quoted context omitted.

I got the same problem. When implementing the exact method as described in quanta magazine (without looking at the arxiv paper), I always had estimates like 461746372167462146216468796214962164. Then after reading the arxiv paper, I got the the correct estimate, with this code (very close to mudiadamz's comment solution): import numpy as np L = np.random.randint(0, 3900, 30557) print(f"{len(set(L))=}") thresh = 100 p…

Quanta: 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. To: Round 1. Keep going through Hamlet, but now flipping a coin for each word. If it’s tails, delete the word if it exists; heads, and add the word if it's not already on the list. Old edit: Round 1. Keep go…

> adding words but now flipping a coin immediately after adding it

Edit: I thought your formulation was correct but not really:

We flip the coin after adding, but we also flip the coin even if we didn't add the word (because it was already there). This is subtle!

wrong:

    if k not in mem:
        mem += [k]
        if np.random.rand() > p:
            mem.remove(k)
wrong:

    if k not in mem:
        mem += [k]
    else:
        if np.random.rand() > p:
            mem.remove(k)
correct:

    if k not in mem:
        mem += [k]
    if k in mem:      # not the same than "else" here
        if np.random.rand() > p:
            mem.remove(k)
correct:

    if k not in mem:
        mem += [k]
    if np.random.rand() > p:
        mem.remove(k)

Re: Computer scientists invent an efficient new way to count

#140

Post by rcarmo »

planede wrote: post #105
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…

return '⊥' what's this?

An error condition. I decided to do away with it and take a small hit on the error by assuming the chances of the trimmed set being equal to the threshold are very small and that the error condition is effectively doing nothing.

I also changed the logic from == to >= to trigger unfailingly, and pass in the "window"/threshold to allow my code to work without internal awareness of the length of the iterable:

    from random import random

    def estimate_uniques(iterable, window_size=100):
        p = 1
        seen = set()

        for i in iterable:
            if i not in seen:
                seen.add(i)
            if random() > p:
                seen.remove(i)
            if len(seen) >= window_size:
                seen = {s for s in seen if random()
I also didn't like the possible "set thrashing" when an item is removed and re-added for high values of p, so I inverted the logic. This should work fine for any iterable.
Post reply on HN