5 ms·
Hello! o/ I’m the author of this post. Happy to answer any questions, and love to get feedback. The code for all of my posts can be found at https://github.co
by samwho 1y ago
Hello! o/
I’m the author of this post. Happy to answer any questions, and love to get feedback.
The code for all of my posts can be found at https://github.com/samwho/visualisations https://github.com/samwho/visualisations and is MIT licensed, so you’re welcome to use it :)
- malwrar 1y agoLove your website’s design, I find all of interactivity, the dog character as an “audience”, and even the font/color/layout wonderful. Loved the article too!
- samwho 1y agoThank you so much! The dogs on the playing cards were commissioned just for this post. They’re all made by the wonderful https://www.andycarolan.com/ https://www.andycarolan.com/. The colour palette is the Wong palette that I learned about from https://davidmathlogic.com/colorblind/ https://davidmathlogic.com/colorblind/. Oh, and you can pet the dogs. :)
- lol768 1y agoIt would've been easy to just use green for the held card and red for the discard pile. Thank you for using a colour-blind friendly palette; as someone with deuteranopia :)
- samwho 1y agoYou're welcome! I think it's a beautiful palette, and I think people have come to associate me with it now so I don't think I'll ever change. I view all of my posts using the various colour blindness filters in the Chrome dev tools during development, to make sure I'm not using any ambiguous pairings. I'm glad that effort made you feel welcome and able to enjoy the content fully.
- zerd 1y agoJust noticed the physics simulator at the top is interactive. Then I was stacking squares on top of each other to see how tall I could make it, and started throwing things at it angry birds style. Fun stuff.
- samwho 1y agoSomething no one seems to have realised yet is that the hero simulation at the top of the page is using reservoir sampling to colour 3 of the shapes black.
- simonw 1y agoI love the commissioned art! Found this post with more details: https://samwho.dev/dogs/ https://samwho.dev/dogs/
- DonHopkins 1y agoSo many nice touches that combine to be much more than the sum of the parts. Doe's bandana is cool, your dogs must worship you for your commitment to them! My only suggestion is a way to slow down or ^S the log to read the funny messages, since they were flying by so fast I could only get a glimpse, even with reservoir sampling. something something "needs more emojis"! ;)
- samwho 1y agoDoe’s bandana is my attempt at tasteful solidarity and support. Glad you noticed it! I did consider a pause button for the logs but it felt too unsubtle, and distracts from the content of the post. You could argue the log messages are already distracting, but I really wanted my own take on “reticulating splines.” You can read how the messages are constructed here: https://github.com/samwho/visualisations/blob/main/reservoir-sampling/src/core/Logs.ts https://github.com/samwho/visualisations/blob/main/reservoir...
- DonHopkins 1y agoI THOUGHT I saw a a Herman-Miller chair fly by! So I'm not going crazy. whew
- Nezteb 1y agoI loved the "Sometimes the hand of fate must be forced" comment!
- samwho 1y agoRecovering WoW addict. :)
- rdtsc 1y agoWell done, I really like the animations and the explanation. Especially the case where it's a graph and we can drag ahead or click "shuffle 100 times" One thing that threw me for a bit is when it switched from the intro of picking 3 cards at random from a deck of 10 or 436,234 to picking just one card. It's seems as if it almost needs a section heading before "Now let me throw you a curveball: what if I were to show you 1 card at a time, and you had to pick 1 at random?" indicating that now we're switching to a simplifying assumption that we're holding only 1 card not 3, but we also don't know the size of the deck.
- pandaxtc 1y agoThis is awesome, I loved the interactivity!
- istjohn 1y agoDoes your blog have an RSS feed?
- fiddlerwoaroof 1y agoDoes this method compose with itself? E.g. if I implement reservoir sampling in my service and then the log collector service implements reservoir sampling, is the result the same as if only the log collector implemented it?
- NoahZuniga 1y agoYes
- samwho 1y agoI hadn’t considered this, cool to know it works!
- eru 1y agoThough I think it's only strictly true, if the intervals you sample over are the same. Eg they both sample some messages every second, and the all start their second-long intervals on the same nanosecond (or close enough). I find it easier to reason about reservoir sampling in an alternative formulation: the article talks about flipping a random (biased) coin for each arrival. Instead we can re-interpret reservoir sampling as assigning a random priority to each item, and then keeping the items with the top k priority. It's fairly easy to see in this reformulation whether specific combinations of algorithms would compose: you only need to think about whether they would still select the top k items by priority.
- fiddlerwoaroof 1y agoThe second formulation sounds easier to use to adapt to specific use cases too: just bump the priority of a message based on your business rules to make it more likely that interesting events get to your log database.
- eru 1y agoYou could do (category, random priority) and then do lexicographic comparison. That way higher categories always outrank lower categories. But depending on what you need, you might also just do (random priority + weight * category) or so. Or you just keep separate reservoirs for high importance items and for everything else.
- nightpool 1y agoI loved the graphics! However, I'm not sure I understand the statistical soundness of this approach. I get that every log during a given period has the same chance to be included, but doesn't that mean that logs that happen during "slow periods" are disproportionately overrepresented in overall metrics? For example, if I want to optimize my code, and I need to know which endpoints are using the most time across the entire fleet to optimize my total costs (CPU-seconds or whatever), this would be an inappropriate method to use, since endpoints that get bursty traffic would be disproportionally underrepresented compared to endpoints that get steady constant traffic. So I'd end up wasting my time working on endpoints that don't actually get a lot of traffic. Or if I'm trying to plan capacity for different services, and I want to know how many nodes to be running for each service, services that get bursty traffic would be underrepresented as well, correct? What are the use-cases that reservoir sampling are good for? What kind of statistical analysis can you do on the data that's returned by it?
- samwho 1y agoGood question. I'm not sure how suitable this would be to then do statistical analysis on what remains. You'd likely want to try and aggregate at source, so you're considering all data and then only sending up aggregates to save on space/bandwidth (if you were at the sort of scale that would require that). The use-case I chose in the post was more focusing on protecting some centralised service while making sure when you do throw things away, you're not doing it in a way that creates blind-spots (e.g. you pick a rate limit of N per minute and your traffic is inherently bursty around the top of the minute and you never see logs for anything in the tail end of the minute.) A fun recent use-case you might have seen was in https://onemillionchessboards.com https://onemillionchessboards.com. Nolen uses reservoir sampling to maintain a list of boards with recent activity. I believe he is in the process of doing a technical write-up that'll go into more detail.
- eru 1y ago> However, I'm not sure I understand the statistical soundness of this approach. I get that every log during a given period has the same chance to be included, but doesn't that mean that logs that happen during "slow periods" are disproportionately overrepresented in overall metrics? Yes, of course. You can fix this problem, however. There are (at least) two ways: You can do an alternative interpretation and implementation of reservoir sampling: for each item you generate and store a random priority as it comes into the system. For each interval (eg each second) you keep the top k items by priority. If you want to aggregate multiple intervals, you keep the top k (or less) items over the intervals. This will automatically deal with dealing all items the same, whether they arrived during busy or non-busy periods. An alternative view of the same approach doesn't store any priorities, but stores the number of dropped items each interval. You can then do some arithmetic to tell you how to combine samples from different intervals; very similar to what's in the article. > What are the use-cases that reservoir sampling are good for? What kind of statistical analysis can you do on the data that's returned by it? Anything you can do on any unbiased sample? Or are you talking about the specific variant in the article where you do reservoir sampling afresh each second?
- glial 1y agoThis is really beautiful design, and excellent teaching. Thank you!
- TheAlchemist 1y agoVery nice post - thank you. This is how maths and stats should be taught. Reminds me a bit about https://distill.pub/ https://distill.pub/
- samwho 1y agoI loved distill.pub. Usually didn’t fully grasp what the papers were about but they were beautiful and I usually got _something_ out of them. Was very sad when they announced their hiatus. Made me nervous about the viability of this sort of content. You may also enjoy https://pudding.cool https://pudding.cool.
- eru 1y agoVery nice post! Another interesting direction you can take reservoir sampling is instead of drawing a random number for each item (to see whether it replaces an existing item and which one), you generate a number from a geometric distribution telling you how many items you can safely skip before the next replacement. That's especially interesting, if you can skip many items cheaply. Eg because you can fast forward on your tape drive (but you don't know up front how long your tape is), or because you send almost your whole system to sleep during skips. For n items to sample from, this system does about O(k * log (n/k)) samples and skips. Conceptually, I prefer the version of reservoir sampling that has you generate a fixed random 'priority' for each card as it arrives, and then you keep the top k items by priority around. That brings me to another related interesting algorithmic problem: selecting the top k items out of a stream of elements of unknown length in O(n) time and O(k) space. Naive approaches to reaching O(k) space will give you O(n log k) time, eg if you keep a min heap around. What you can do instead is keep an unordered buffer of capacity up to 2k. As each item arrives, you add it to the buffer. When your buffer is full, you prune it to the top k element in O(k) with eg randomised quickselect or via median-of-medians. You do that O(2k) work every k elements for n elements total, given you the required O(n) = O(n * 2*k / k) runtime. Another related topic is rendezvous hashing: https://en.wikipedia.org/wiki/Rendezvous_hashing https://en.wikipedia.org/wiki/Rendezvous_hashing Tangentially related: https://www.keithschwarz.com/darts-dice-coins/ https://www.keithschwarz.com/darts-dice-coins/ is a great write-up on the alias method for sampling from a discrete random distribution.
- samwho 1y agoI actually read that post on the alias method just the other day and was blown away. I think I’d like to try making a post on it. Wouldn’t be able to add anything that link hasn’t already said, but I think I can make it more accessible.
- eru 1y agoI have a few more topics we could cooperate on, if you are interested. https://claude.ai/public/artifacts/62d0d742-3316-421b-9a7b-d3a47e3a9c8d https://claude.ai/public/artifacts/62d0d742-3316-421b-9a7b-d... has a 'very static' visualisation of sorting algorithms. Basically, we have a 2d plane, and we colour a pixel (x, y) black iff the sorting algorithm compares x with y when it runs. It's a resurrection (with AI) of an older project I was coding up manually at https://github.com/matthiasgoergens/static-sorting-visualisation/blob/master/images/quick_random_xy_1500.png https://github.com/matthiasgoergens/static-sorting-visualisa... I'm also working on making https://cs.stackexchange.com/q/56643/50292 https://cs.stackexchange.com/q/56643/50292 with its answer https://cs.stackexchange.com/a/171695/50292 https://cs.stackexchange.com/a/171695/50292 more accessible. It's a little algorithmic problem I've been working on: 'simulate' a heap in O(n) time. I'm also developing a new, really simple implementation of soft heaps. And on my write-up for the solution to https://github.com/matthiasgoergens/TwoTimePad/blob/master/description.txt https://github.com/matthiasgoergens/TwoTimePad/blob/master/d... > I actually read that post on the alias method just the other day and was blown away. I think I’d like to try making a post on it. Wouldn’t be able to add anything that link hasn’t already said, but I think I can make it more accessible. If memory serves right, they don't do much about how you can efficiently support changes to your discrete probability distribution.
- tambourine_man 1y agoYour whole blog seems like a treasure trove. I’m glad I found it, thanks for sharing.
- purrcat259 1y agoI just listened to your episode on fafo.fm a few days ago and recognised your handle and already knew the link was worth clicking. Your stuff is awesome!
- slig 1y agoIt's so nice to read things written by someone who cares. Thank you so much for sharing!
- Matumio 1y agoThe post looks interesting, but I'm still building my triangle castle so I haven't read it yet. This probably means I should read it later when I'm less distracted. Anyway, already love the layout and the playful visualisations.