hddqsb

Demo: https://tio.run/##tVddc6IwFH3nV0Q7WyXFIlrdUWr7uC/9B213BkIQKo...

    pattern = "a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z"
    text    = "aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzza"
    running time = 1.6s

> To bootstrap the system, an initial set of Actors who share the same core values about the to-be-created reputation each gets allocated a bootstrap Reputation Score. This gives them the ability to receive Rating Tokens with which they can rate each other and newly entering Actors.

So basically it assumes there is an initial set of trusted Actors.

But even with this assumption there are potential issues (e.g. good Actors may be bribed).

Here is a simple patch to make the runtime O(len(pattern) * len(text)) instead of exponential. It adds 5 lines and a new parameter. The idea is to memoize (cache) the results, specifically the failures (there is no need to cache the successes, because all the functions return immediately on success).

     // Match reports whether regexp matches anywhere in text.
     func Match(regexp, text string) bool {
    +    seen := make(map[[2]int]bool)
         if regexp != "" && regexp[0] == '^' {
    -        return matchHere(regexp[1:], text)
    +        return matchHere(regexp[1:], text, seen)
         }
         for {
    -        if matchHere(regexp, text) {
    +        if matchHere(regexp, text, seen) {
                 return true
             }
             if text == "" {
                 return false
             }
             text = text[1:]
         }
     }
     
     // matchHere reports whether regexp matches at beginning of text.
    -func matchHere(regexp, text string) bool {
    +func matchHere(regexp, text string, seen map[[2]int]bool) bool {
         switch {
         case regexp == "":
             return true
         case regexp == "$":
             return text == ""
         case len(regexp) >= 2 && regexp[1] == '*':
    -        return matchStar(regexp[0], regexp[2:], text)
    +        return matchStar(regexp[0], regexp[2:], text, seen)
         case text != "" && (regexp[0] == '.' || regexp[0] == text[0]):
    -        return matchHere(regexp[1:], text[1:])
    +        return matchHere(regexp[1:], text[1:], seen)
         }
         return false
     }
     
     // matchStar reports whether c*regexp matches at beginning of text.
    -func matchStar(c byte, regexp, text string) bool {
    +func matchStar(c byte, regexp, text string, seen map[[2]int]bool) bool {
         for {
    -        if matchHere(regexp, text) {
    +        if seen[[2]int{len(regexp), len(text)}] {
    +            return false
    +        }
    +        if matchHere(regexp, text, seen) {
                 return true
             }
             if text == "" || (text[0] != c && c != '.') {
                 return false
             }
    +        seen[[2]int{len(regexp), len(text)}] = true
             text = text[1:]
         }
     }

    $ printf '%s\n' 'asterisk: *' 'backslash: \' | grep '[*]'
    asterisk: *
    $ printf '%s\n' 'asterisk: *' 'backslash: \' | grep '[\*]'
    asterisk: *
    backslash: \

Yes, my argument is specifically for the case where the fine etc. is directly proportional to the difference (or absolute difference). I'm pointing out that the two cases are similar apart from the signedness.

To put it mathematically, I'm just observing that if you have a set {x_i}, then:

- avg{|x_i - y|} is minimised by setting y to median{x_i}

- |avg{x_i - y}| is minimised by setting y to avg{x_i}

The excerpt in the article says "the mean minimizes the average squared distance" (i.e. setting y to avg{x_i} minimises avg{(x_i - y)^2}), which is correct but not obvious (the proof is non-trivial, and if you were to ask the students who chose the mean why they chose it I bet none of them would say "because it minimises the squared distance"). So I find it odd to include that statement. If I was the author I would have said "the mean minimizes the average signed distance", which I find more intuitive and think is a better explanation of why those students chose the mean. (Also, I like how "average value of the absolute difference" and "absolute value of the average difference" are the same words just in a different order.)

It should be obvious that the mean is the correct representative value for weighing nails. My point is that there are cases that call for the mean and cases that call for the median, and the distinction can be explained by considering the signedness (without having to consider squared distances).

Maybe the following variation on the nail example would help: Suppose the manufacturer of the nails must publish a reference value for the weight of a nail, and will be fined for every nail that is not exactly the correct weight. The fine is proportional to the absolute error. Question: Should the manufacturer publish the mean or the median in order to minimise fines? Answer: The median.

Why is the mean the correct representative value for counting nails, but not for minimising fines? I'm arguing that it's because when the nails are weighed together the errors are signed, but when the fines are calculated the errors are unsigned (in the same way that the distances to the elevators are unsigned).

Yes, obviously you'd estimate the mean/median by taking a small sample (or using a published value). I left that detail out because it's not relevant to the choice between mean and median.

This is true, but I find it more intuitive to think about the signed distance: if you define signed_dist(x, y) = x - y, then the mean is the value that makes the average signed distance closest to 0. Of course in reality distance is unsigned – if you walk 1m left then 1m right, you've walked 1m + 1m = 2m, not 1m + -1m = 0m, so the signed distance is not appropriate.

Here is a practical example where the aim is to get the average signed difference to be closest to 0: You want to count a large number of nails by weighing them. To do that, you need to know the weight of a single nail. But the nails have slightly different weights, so you need to pick some representative value. Question: Should you pick the mean or the median? Answer: You should pick the mean, because when you weigh all the nails together the differences will cancel out.

So the rule is:

- To minimise the average value of the absolute difference, pick the median.

- To minimise the absolute value of the average difference, pick the mean.

- It doesn't tell you how many days there are in the month (31/30/28/29).

- Working out how to move the frame at the end of the month isn't very difficult, but it's not trivial either (especially given the previous point).

> An iterator could query a database, for example—including the unfortunate possibility that it might alter data, or that iterating through it twice might yield completely different results! Some tools (like ReSharper) will warn you against multiple enumeration for this reason.

[1] Calculation: Lindy proportion 1 corresponds to a Pareto distribution with probability distribution function `a / x^(a+1)` where a = 2 and the range of x is [1, ∞). The cumulative distribution function is `1 - 1/x^a`. So the probability of the remaining lifetime being less than or equal to the observed lifetime is CDF(2) = 0.75.

And note that the Lindy effect is about the expected value (mean). The statement "probably run another T hours without incident" could be interpreted as relating to the median, which is actually a little less than the mean. So the statement should either be "the expected value of the number of hours until the system stops is T", or "the probability of the system running for at least another T hours is a little less than 50%".

    < /tmp/com.txt awk ...

This design seems like a surprising oversight on Google's part. The correct design is to only add the recovery account if a verification link is clicked (which is in fact what they do for enabling mail forwarding). That way you could simply create a filter to mark the requests from that guy as spam. However, being the recovery address of this guy doesn't seem like such a serious problem – it should be relatively easy to filter the emails that Gmail sends to recovery accounts (something like "from:no-reply@accounts.google.com <guy's email address>").

> OpenJDK implements threads as thin wrappers around the OS thread [...] OS threads are expensive, by which I mean that we cannot have too many of them. Maybe a few thousand active ones, maybe ten thousand active ones, but that's about it. And the reason for that is that the OS doesn't know the various languages, and the most costly component of a thread is its stack, and the operating system doesn't know how the various languages it might support makes use of the stack. So it must address the worst case and allocate a very large stack. It's usually on a megabyte scale. And even though we use virtual memory and not all of it is committed to physical memory, once we touch a page it becomes committed – it can't be uncommitted again because the OS doesn't know how the stack is used. And in any event, all the operations are done at a page granularity which is 4k, it's also not that small.

There may also be arbitrary OS-specific limits. For example on Linux there is system-wide limit on the number of threads, controlled by /proc/sys/kernel/threads-max (docs: https://www.kernel.org/doc/html/latest/admin-guide/sysctl/ke..., see also: https://stackoverflow.com/a/8849114). On my system it's ~60,000 (with 8G RAM).

If you call `time.Sleep()` the reported duration will reflect that call, but it's only simulating the delay. The duration of a CPU-heavy task is always reported as 0.00s.

Demo: https://go.dev/play/p/UZToqFseAwO

Output:

    === RUN   TestSleep // calls time.Sleep(2 * time.Second)
    Real duration: 554µs
    --- PASS: TestSleep (2.00s)
    === RUN   TestBusyLoop // for i := 0; i < 1000000000; i++ { ... }
    Real duration: 390.826ms
    --- PASS: TestBusyLoop (0.00s)
    PASS

Concurrency is one of Go's core features, so it figures the playground would allow some form of concurrency even when the clock is fake.

Here is a hacky workaround to measure the actual time using a syscall: https://go.dev/play/p/kF6Bh048siE

It shows 979ms for the original version and 0.212ms for the fast version.