5 ms·
Python implementation: def streaming_algorithm(A, epsilon, delta): # Initialize parameters p = 1 X = set() thresh = math.ceil((12 / e
by mudiadamz 2y ago
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() < p:
X.add(ai)
if len(X) == thresh:
X = {x for x in X 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, epsilon, delta)
print(output)
- planede 2y agoreturn '⊥' what's this?
- jbaber 2y agoIn 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.
- dentemple 2y agoOnce again proving the need for comments in code. Especially for comments that are more useful than "initialize parameters"
- hollerith 2y ago>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).
- tsss 2y agoNot always. It is also the uninhabited bottom type.
- hollerith 2y agoMy 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.
- deleted 2y ago[deleted]
- martinsnow 2y agoAn easy way to identify who copies code without understanding it.
- mudiadamz 2y agoYou can just replace it with something like: print ('Invalid thresh or something')
- martinsnow 2y agoThis however looks scary so an innocent copy/paste programmer wouldn't touch it.
- deleted 2y ago[deleted]
- rcarmo 2y agoAn 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() < 0.5} p /= 2 return int(len(seen) / p) 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.
- deleted 2y ago[deleted]
- sestep 2y agoIs this ChatGPT? Also, I feel like this would be more useful if it included import statements.
- mudiadamz 2y agoimport math import random
- ericmcer 2y agoI 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.
- foobarian 2y agoSpeaking of, one of my favorite discoveries with Unicode is that there is a ton of code points acceptable for symbol identifiers in various languages that I just can't wait to abuse. >>> ᚨ=3 >>> ᛒ=6 >>> ᚨ+ᛒ 9
- tgv 2y agoThe names are literally taken from the paper.
- seaman1921 2y agowell the paper also contains the code so I doubt anyone who looked at the paper cares about this paste - for folks who did not read the paper this is not very readable
- sneva 2y ago> 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.
- rcarmo 2y agoThat's not streaming if you're already aware of the length of the iterable.
- axitanull 2y agoIn python, you can simply substitute `A` with an iterable or generator object, which can be a of unknown length.
- mattkrause 2y agoBut 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?
- empath-nirvana 2y agoYou 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.
- rcarmo 2y agoSee https://news.ycombinator.com/item?id=40390192 https://news.ycombinator.com/item?id=40390192
- istjohn 2y agoYou would want to calculate the threshold by choosing your target epsilon and delta and an 'm' equal to the largest conceivable size of the stream. Fortunately, the threshold increases with log(m), so it's inexpensive to anticipate several orders of magnitude more data than necessary. If you wanted, you could work backwards to calculate the actual 'epsilon' and 'delta' values for the actual 'm' of the stream after the fact.
- abootstrapper 2y agoNew leetcode hard question just dropped.