111–120 of 173 posts
Looking particularly at latency measurements, I found the "How NOT to Measure Latency" [1] talk very illuminating. It goes quite deep into discussing how percentiles can be used and abused for measurement. [1]: https://www.infoq.com/presentations/latency-response-time/
I watch this video once a year and send it to my co-workers whenever averages or medians shows up in a graph for public consumption.
Earlier quoted context omitted.
> The question was basically, "Find the median of a huge data set without sorting it," Isn't this done using a min heap and a max heap in conjuction?
No, for 2 reasons, 1. huge data set: heaps requires storing the whole set, but "huge" means "more than you can store" 2. without sorting it: heaps are basically semi-sorted, so you are breaking the rules
Really? Where's it coming from?
Earlier quoted context omitted.
> The question was basically, "Find the median of a huge data set without sorting it," Isn't this done using a min heap and a max heap in conjuction?
It's funny that this is often left out from a data & algorithm class.
Earlier quoted context omitted.
No, for 2 reasons, 1. huge data set: heaps requires storing the whole set, but "huge" means "more than you can store" 2. without sorting it: heaps are basically semi-sorted, so you are breaking the rules
> but "huge" means "more than you can store" Really? Where's it coming from?
With a few exceptions this is pretty common scenario.
Earlier quoted context omitted.
i think of it as: if the data is gaussian, use a mean, otherwise go non-parametric (medians/percentiles). or put another way, if you can't model it, you're going to have to sort, or estimate a sort, because that's all that's really left to do. this shows up in things from estimating centers with means/percentiles to doing statistical tests with things like the wilcoxon tests.
Assume up front none of your measured latencies from a software networked system will be Gaussian, or you will die a painful death . Even ping times over the internet have no mean. The only good thing about means is you can combine them easily, but since they are probably a mathematical fiction, combining them is even worse. Use T-Digest or one of the other algorithms being highlighted here.
sadly, the instructor just gave it an A and moved on. (that said, the amount of work that went into a single semester project was a bit herculean, even if i do say so myself)
Earlier quoted context omitted.
No, for 2 reasons, 1. huge data set: heaps requires storing the whole set, but "huge" means "more than you can store" 2. without sorting it: heaps are basically semi-sorted, so you are breaking the rules
> but "huge" means "more than you can store" Really? Where's it coming from?
And possibly it's live data.
Awhile ago I wrote a Python library called LiveStats[1] that computed any percentile for any amount of data using a fixed amount of memory per percentile. It uses an algorithm I found in an old paper[2] called P^2. It uses a polynomial to find good approximations. The reason I made this was an old Amazon interview question. The question was basically, "Find the median of a huge data set without sorting it," and the "…
There’s something called a five number summary in statistics: mean, median, standard deviation, 25th percentile and 75th percentile. The bonus is that the 75th - 50th gives you the interquartile range. Mean is not a robust measure and as such you need to look at variety to truly understand the spread of your data.
IQR is 75th - 25th, aka, the middle-50%
Gamers have an intuitive sense of this. Your average framerate can be arbitrarily high, but if you have a big stutter every second between the smooth moments, then a lower but more consistent framerate may be preferable, typically expressed as the 1% and 0.1% slowest frames, which at a relatively typical 100fps, represents the slowest frame every second and every 10 seconds.
Gamers do not have a more intuitive sense for this than movie watchers, video/voice talkers, not to mention users who type text into bloated web browsers or lagged remote login sessions. I would rather have a rock-steady consistent 500 ms reponse time when typing text, than to have a 100 ms average response time which randomly spikes to outliers that go past one second. A rock-steady, though poor, event rate in a pai…
I would be shocked if gamers didn't on average have a more intuitive sense of this than any of the groups you mentioned.
Earlier quoted context omitted.
I have no hope of finding a cite for this, but a long time ago I read some command line UI research that found if you had a system where commands ranged from instant to taking a small but noticeable time and you introduced delays in the faster commands to make it so all commands took the same small but noticeable time people would think that the system was now faster overall.
I guess that’s because our minds (and animal minds as well) are always aware of the pace of repetitive events. If something is off, the anxiety alarm rings. One old book on the brain machinery described an example of a cat that was relaxing near the metronome and became alert when it was suddenly stopped. Unpredictable delays are disturbing, because a mispredicted event means you may be in a dangerous situation and h…