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

141–150 of 299 posts

Re: Computer scientists invent an efficient new way to count

#141

Post by Alexanfa »

josephernest wrote: post #139
Alexanfa wrote: post #131

Earlier quoted context omitted.

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) co…

Ah, I'm using a set instead of list so I just always add and then toss remove.

Re: Computer scientists invent an efficient new way to count

#142

Post by tsss »

hollerith wrote: post #118
jbaber wrote: post #106

Earlier quoted context omitted.

In some symbolic logic classes, that character "bottom" represents "false" ad flipped "top" means true. Don't know what they're getting at in the code, though.

>In some symbolic logic classes, that character "bottom" represents "false" That's unfortunate, because in the study of computer programming languages, it means "undefined" (raise an error).

Not always. It is also the uninhabited bottom type.

Re: Computer scientists invent an efficient new way to count

#144

Post by V1ndaar »

menthe wrote: post #104
cb321 wrote: post #80

This Nim program might clarify some things for someone. import std/[random, math, sets, times]; type F = float template uniqCEcvm*(it; xfm; k=100, alpha=0.05): untyped = ## Return (unbiased estim. cardinality of `it`, 1-alpha CI ebound*(1 +- e)). var x1 = initHashSet[type(xfm)](k); var x = x1.addr var x2 = initHashSet[type(xfm)](k); var y = x2.addr var p = 1.0 # p always 2^-i means could ditch FP var n = 0 #..RNG & a…

Frankly, who can read this!? I am not sure what's worse, the multi-line comments spanning multiple lines of code, having multiple instructions on a single line, or the apparent disconnect between the pseudo-code of the article.

I would blame the majority of your criticism on the fact that HN is not the best place to read code. Also, syntax highlighting & basic familiarity with Nim helps.

His code is doing a few more things than necessary. The actual algorithm is inside the `uniqCEcvm` template. The `it` it receives is anything you can iterate over (a collection or an iterator). Multiple things in one line really only appear where they directly relate to the part at the beginning of the line.

The `when isMainModule` is Nim's way of Python's `if __name__ == "__main__"`. The entire part below that is really just a mini CL interface to bench different (random) examples. Final thing to note maybe, the last expression of a block (e.g. of the template here) will be returned.

And well, the style of comments is just personal preference of course. Whether you prefer to stay strictly below 80 cols or not, shrug.

I grant you that the usage of 2 sets + pointer access to them + swapping makes it harder to follow than necessary. But I assume the point of it was not on "how to write the simplest looking implementation of the algorithm as it appears in the paper". But rather to showcase a full implementation of a reasonably optimized version.

Here's a version (only the algorithm) following the paper directly:

    proc estimate[T](A: seq[T], ε, δ: float): float =
      let m = A.len
      var p = 1.0
      var thr = ceil(12.0 / ε^2 * log2(8*m.float / δ))
      var χ = initHashSet[T](thr.round.int)
      for i in 0 ..= thr:
          for el in toSeq(χ): # clean out ~half probabilistically
            if rand(1.0) = thr:
            return -1.0
      result = χ.card.float / p

Re: Computer scientists invent an efficient new way to count

#146

Post by Levitz »

jameshart wrote: post #99
lupire wrote: post #94

Earlier quoted context omitted.

Come on. There is a fundamental difference between trying to get an exactly answer and not trying to get an exactly correct answer.

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…

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.

Re: Computer scientists invent an efficient new way to count

#149

Post by hollerith »

tsss wrote: post #142
hollerith wrote: post #118

Earlier quoted context omitted.

>In some symbolic logic classes, that character "bottom" represents "false" That's unfortunate, because in the study of computer programming languages, it means "undefined" (raise an error).

Not always. It is also the uninhabited bottom type.

My point is that there is a difference between a Python function's returning false and the function's raising an error, and sometimes the difference really matters, so it would be regrettable if logic teachers actually did use ⊥ to mean false because programming-language theorists use it to mean something whose only reasonable translation in the domain of practical programming is to raise an error.

I have no idea what your point is.

Post reply on HN