169: HyperLogLog

0:15A:Programming Throwdown Episode 169: HyperLogLog. Take it away!

0:22B:Jason, hey everybody. Um, so Patrick, do you have are all your cars electric? Any of your cars electric? Do you have an

0:31A:Ice car? Uh, actually I have one normal car and one the plug-in hybrid we discussed. So it does have a battery, but also has a regular 12-volt car battery. Oh yeah.

0:39B:That's what I was going to ask you. So even the hybrids have regular car batteries? Uh, the hybrids?

0:45A:For sure. I think even electric cars still often have like 12-volt sort of normal car batteries for a variety of purposes. I

0:54B:don't know. Okay. I mean, it's probably better than trying to like convert, you know, from whatever voltage the engine battery uses. It looks like.

1:04A:Here they do. Just a quick Google says that yeah, they have the normal lead-acid 12-volt batteries.

1:09B:So you know how do you know when your car battery is dead? Do you just drive until the battery stops working, or what do you do? I

1:17A:mean, in an overall, I guess. Yeah, the car can't start. So I don't know how that works in electric. Your accessory systems like when you sit in the car before you start it, it probably doesn't turn on. Yeah.

1:28B:So like in my experience until recently, I have never tested my car battery. And so basically what happened is I will just drive until the car won't start, and I will have to go and desperately figure out how to replace the car battery, and it ends up being this big thing. And it's just gotten worse as like we've gotten busier over the years. So it culminated when we were about to all go camping and the car didn't start, and it—we've had the same battery for a while, but part of it is you know, you never totally know without a tester if it's if it's the battery or if you left the lights on or if there was some kind of glitch that caused the energy to drain. Like, um, we had the key in the car—like not literally in the ignition, but we had the key next to the car, and I feel like just having the key so close to the car it somehow got confused and it thought we were in there or something. Um because you know, I'm actually so, I guess to answer, I'm ordering a car battery tester which is only 20 bucks. I thought it was going to be like hundreds of dollars because you know when they—when they anytime they do anything at the dealership or you call someone to do something, it always seems like oh, like this must be some amazing device that you know must be manufactured in a laboratory in the middle of the earth or something. And so no, it's like you can get a car tester or battery tester for like 20 bucks. Do

2:57A:You have to disconnect the battery—not remove it, but at least like disconnect the terminals like the rest of electrical system for it to work because that's an annoying thing if you do

3:06B:Yeah, I don't think so, right? Because as long as the car is not on, it's not drawing—it's not drawing any amps. So it should—it should be an insignificant draw. So we're gonna find out. I'm gonna get the car battery tester on Tuesday, tomorrow, and um I'm gonna see what the instructions say, and yeah, I'll let you know. But I'm pretty sure, just, you know, putting my engineering hat on that, as long as the car is not on—well, the car has to not be on, and and not even on accessory mode, like the keys have to be far away, and everything.

3:42A:Could see that, but it's not a voltage thing, right? So the thing you're describing is can you pull enough amps temporarily to turn the car over, right? So it's like measuring like rush current that it can deliver.

3:54B:Yeah. So this $20 thing what it needs to do is draw enough amps for a certain amount of time and make sure the voltage doesn't drop, right? I think that's, but it can also tell you—it can actually tell you whether the battery like all the cells are just old or if you have one bad cell. I don't know what you would do with that information, but it can tell the difference there.

4:17A:Probably a voltage-based thing, knowing that all the batteries are made from the same chemicals or whatever. So yeah.

4:23B:That's right. Yeah, I think if you have one dead cell, then you would have—you'd consistently pull a certain number of amps but at a lower voltage. Well, you'd.

4:32A:Have one cell voltage drop missing. So you like I don't know how many cells are in a 12, but like you would go to 9.3 and that's like all your cells are good except for one. Yeah versus if you just had like 10 instead of 12, then okay. So. That your mission, should you choose to accept it, is to crack open the tester to look at the circuitry, figure out what it's doing. Yeah, after.

4:56B:The last episode where I burnt the Raspberry Pi and I literally have an imprint on my finger from the SD card. I don't know if I'm gonna crack open the battery, but um but yeah, I guess you know it'd be interesting to hear what people out there do. So if you just drive your car until it doesn't turn on—if you have some regimen that works for you and you've never had this happen to you either end of the spectrum, let us know. Um you know, I just, you know, it kind of like it didn't ruin our camping trip, but it definitely set the camping trip back by like multiple hours. So so I kind of feel like I need it to improve this area of my life. So we'll see how it goes. If you have a way of doing this, let us know.

5:44B:Actually, Patrick, do you do anything or do you just drive the car until it doesn't turn on? Yes, that one which.

5:51A:Is horrible. I think when I take it for its regular oil change, I think one of the things in the checkpoint is they hook up their expensive battery tester to it and then try to convince me to buy their battery. Um so that's been my—I do regularly get the oil changes on schedule. Um I don't know if that actually actually is super critical, but I for whatever reason, I just choose to do it that way, and so yeah.

6:14B:Hope it's the same thing. I get the oil changes on schedule, but I've never as far as I know, I've never had a mechanic tell me I need to change the battery. It's always just died. Oh man. All right. On to the news. You're first up. All right. So you know we never really talked about this. This is a news article about, you know, Google continuing to do layoffs. Um but you know, this particular article isn't what I want to talk about. I want to talk about tech layoffs in general. Um you know my view of it—you know there are layoffs. There have been layoffs for what probably 18 months now. It kind of oscillates. So there's layoffs and all of a sudden, you know, there's even articles about companies laying people off and then desperately asking them to come back. Um it's very—it's a very volatile situation. Um you know.

7:08B:My overall take on this is that you know. I think that it's a really complicated situation because on one hand I do think people should choose degrees and majors and careers that have an addressable market. Right? So if you get a degree—well, depending on what your goal is—but you know if your goal is to enter industry and you get a degree in American History, that's going to be really difficult. I mean, there are, you know, you don't need to do what your degree is, but you know it's just making things a little bit more difficult. And so someone might say, 'Well, with all these tech layoffs, maybe we shouldn't get a major in Engineering or Computer Science.' I think my overall take of this is that Engineering is still an extremely strong discipline career-wise, relative to the spectrum of degrees or things you could study. And so I wouldn't be really phased by this. If you're a high school student, college student, you know, I would choose Engineering if it's something you're interested in and not really be worried about the layoffs. I wouldn't make that a really big factor in which college major you're going to pick. What do?

8:33A:You think Patrick? Yeah, I agree. I mean, I would love to say that if you look back to other periods in time like 2001 or the Great Financial Crisis and that the layoffs were completely merit-based. But I mean, I think the unfortunate truth is when a company goes to lay up—when a company hires people, hire against different reasons, different performance targets—they might be overspecializing, overgeneralizing hiring less quality than they need, overpaying for whatever. There's just so many variables that go in. I think when a company goes to do layoffs, it becomes very difficult to sort of run some strict merit-based thing because also layoffs normally come from top down, right? Normally the bottom people aren't doing the layoffs. So it's the top down that, 'Hey, there's a target to hit.' And but bottom up, there's this like obfuscation that happens where everyone says their team is overperforming because it's sort of a game theory thing, right? Like you don't want to say, 'Oh, I have a team full of underperformers.' And that's why I might—you know, that sounds bad on the manager. Right? So you get this like information problem. And so I think when the layoffs happen, it unfortunately it isn't always very fair. But to Jason's point, I do agree that on a whole, I think the industry is fairly robust and there are other people hiring. But times are exuberant and times are lean, and I think what often can happen is if you are in the wrong part of the hype cycle when you come out of college, you can have sort of wrong expectations like, 'Oh, you know, I'm going to start out and make X dollars per year.' And then if times get lean and you're sort of waiting for a better offer that matches what you heard. It's like, well, unfortunately the situation is dynamic, and like, you know, it's not necessarily true that those offers are still there. And so you got to kind of be aware of that. But on the whole, I think you know as an

10:28A:industry, there's still growth here. I mean, people kind of say which they've always said, 'Oh, AI, offshoring,' whatever. There's always some threat to Computer Science or Engineering disciplines, but I don't—I'm not overly worried about it myself and I would still encourage people who are interested in it to pursue it. I think there's lots of adjacent jobs you can do if things really lean. There's plenty of other things you could apply the skills you learn in getting an Engineering degree to. And so also, though, I will like give a shout out for the finance stuff we talk about sometimes, which is the importance of having savings and not living paycheck to paycheck. And it can be hard when you live somewhere expensive, but making sure that if that does happen where you have to sort of go a few months before you can land another job and have the freedom to not have to just take the first thing that comes across your desk. Then I think that's a huge benefit and gives you a little bit more confidence to kind of seek out the thing you're looking for. But yeah, I agree. I'm not overly concerned about it. I think like this latest round that you're mentioning are a lot smaller. So the news likes to hype it up because everything's dramatic. But you know there have been serious cuts. I think the cuts are tapering off. We're probably seeing the last of them, but you'll always see companies wind down, but new companies start up. And it's kind of an ebb and flow. And so as a whole, I think the health of the industry in terms of compensation and stuff is probably steady, probably not as exuberant as it was two or three years ago. But holding steady. Yeah.

12:01B:Yeah, I agree with that. Um yeah, I think you brought up a really good point which is you know and I know we've talked about this before, but when you start out—you know, let's say you're in college right now, you're looking for different careers. Your goal should be to learn as much as possible. And in fact, like most companies will have source control, will have peer reviews, will have like a lot of different disciplines that will be really important for you to pick up early. And so you really can't—as far as I know, you really can't go wrong. You obviously I've only had one first job as one human being, but you really can't go wrong with your first job. You can always find stuff to learn. There's just a huge expanse of things that you need to know to be a professional developer, and you will learn at least 70 or 80 of that almost anywhere, I would say. That maybe the place that's the most risky would be to join something extremely early. I heard a hilarious story—I don't think I've ever talked about this on a show where this was back when Java was really popular. I had a buddy who worked at a really small company, it's only just a handful of engineers, most of them were straight out of college, so there wasn't really anybody who has experience. And you know, Java used to have these things called JAR files, right? Which were basically ZIP files with some metadata that told you like which Java file to run first. And I'm probably butchering that, but it's basically what it was. And so most people don't know that JAR files under the hood are just ZIP files, but these folks did. And so their continuous deployment strategy was to build the code on their computer, guess at like which dot class files changed based on which Java files they changed and copy those into the ZIP into the JAR that was

14:07B:running on the deployment—like on the production server. So there was no source control. Everyone just copied source files to each other over like Windows shares. And so when it was your turn to update the code, you would open up this JAR file and start dropping Java class files in there. So you know that's a difficult situation to learn—you know continuous deployment and source control and all of that. So you know that might be something I'd be concerned.

14:43B:about, but you know most medium to large size companies—actually all medium to large size companies and most small size businesses would be

14:51A:just fine. All right. Well, taking a hard turn there from the seriousness of that, but I agree with what you say. My next news article is my continual stream of shader descriptions, which is in—I've given up the belief that I'm going to build a killer game, so now I'm just like I'm going to build a killer shader for making a cool visual demo. So this is real-time dreamy cloudscapes with volumetric ray marching. Oh, that's a mouthful. This is check this link out. This is by guessing by the name of the blog—I think it's by someone named Maxime Heckle. Is what I would guess there. But yeah, I think that's right. And they have an article on their blog about doing a couple things. First of all, rendering clouds, as the name says, in real time, so you know doing it nice and fast. It's a beautiful thing if you check it out. But also interesting is if you sort of click around through the linked articles, they have a ton of really just interesting examples of doing shaders and how to kind of make them work. And so shader is a code that roughly runs on your GPU and you know sort of has instructions per pixel about what to render. And it's source of a lot of like how do you call, like computer-generated art demo scene style things which we've alluded to before. But also this discussion of ray marching has come up a few times. I feel like those things ebb and flow. I think it's the algorithm just like honing in on me, but like whatever. So I've seen a lot of YouTube videos or whatever about ray marching recently, and so it's on my list of things to look into, which is a way of sort of thinking about raycasting and understanding how close you are to something—signed distance functions. Anyways, tons of good quality things. It's like a jumping off point. So I one day aspire to make beautiful like mellow screensaver-like shaders, like these articles I keep touting out for everyone. This

16:50B:is amazing. One PSA: don't look at this in Firefox; it will cause all sorts of heartburn, but on Chrome it works just fine. Do you do this Patrick? I use different browsers on my work computer for personal and for work things that way it's like the most isolated environments I could think of.

17:11A:Oh yeah, I do do that, but it's sort of a more because it's a requirement rather than.

17:22B:It works just fine. That is so cool. You know, I wonder how many of these things are commodities? Like if you were to use Godot or Unity or one of these things, do they just have volumetric ray marching, or is it too cutting?

17:38A:Edge. Oh, um that's a good question. I probably it's like you could probably find out implementations of it and you know pieces, but I think this is one of those things that you kind of piece together—the sort of almost algorithms into building the look of your game or your demo or whatever. So you may do things like compile various ways of doing water rendering and cloud rendering if you're doing, you know, this kind of thing. And so I think you might be able to pull down certain—it's not like shaders. I don't think that, you know, my understanding is it's not like pulling down a model, like downloading a model and like, you know, rendering the model and it's rigged and you do animations, like those things. I think you have common utilities for the shaders are more like the sort of look and feel, and so you can probably have a jumping off point with them, but you sort of combine them in your own way to give your game its unique style—um, you know, or realistic, you know, kind of thing. But I think a lot of people make independence are pursuing a very stylistic approach so that kind of looks unique to them or whatever. So rather than, you know, hyper-realistic is a really tough game to play in.

18:42B:Yeah, that totally makes sense. Um, all right. My second news is—I've been diving into. Okay, so what was your first computer, Patrick? First thing?

18:54A:With a keyboard? It must have been one of those, what is that, like an Apple IIe?

18:59B:Okay. Yep, yep. We had those in school. I had a Commodore 64 and, you know, I also had an Apple IIe at school. And I've just been going down memory lane on old, like original games, like the first few games ever played. Um one of them was this game called Street Beat where you ran around with a boom box trying to hit people in the face with music notes to make them dance, right? And so actually the way it worked was first you had to find a song, and the songs were like in people's houses. So you'd see a glowing door that was a sign that this person had made an awesome song. You'd go in his house, you take his song, and then you turn on your boom box and hit people in the face with music notes. And once you hit a certain number, then the song was like, you know, I guess, proven to be good or something baked in or whatever it is. And then you would take your—your baked-in song to your house, your own personal house, and score a point. And so I don't remember how many points you have to get, but um anyway, so that was Street Beat. Um I came across one that I played with my family when I was really little that kind of blew my mind in that it was really an interesting crossover that I don't think I've seen since called Robot Rascals. And so the way Robot Rascals worked is it was a card game and a computer game all in one. So you—

20:35B:know the cards were your private information that no one else could see, and the computer was sort of the community, you know, information. And so you would take turns playing this game on the computer, but you would have your private information, and you know, you try to based on what other people were doing try to guess at what their private information was so that you could exploit it. And I just—yeah. So many good memories of this, but but I haven't really seen anything like that. There are some, you know, companion apps. So if you're playing Monopoly, for example, there's like a companion app where you don't have to pass paper money around, you know, there's things like that, but those are more assisted tools. I haven't really seen like a board game app trying to, you know, crossover like this. Um Have you, Patrick? Have you seen anything like that?

21:30A:I mean, there are a few. So I think, you know, I've played like Ticket to Ride where, you know, like everyone has their tablet and, you know, the screen is rendering the common thing, but you can also do pass-and-play or whatever where like the color—oh, I don't know how people anyway, the color of the cards you have, you know, it shows at your turn. There's also, I think one for Scrabble. Um no.

21:51B:Wait, hang on. I don't know. Maybe—I don't know. Okay? So what I'm saying is you have physical cards, so you're playing a physical card game, but then the computer has like the other half of the game, you know? So like the computer doesn't know.

22:07A:It's like combined, like hybrid. So it's not like you're playing the board game. I was like, okay, no, I missed this. Okay? So like you have like a deck of cards like holding in your physical hand, right? Right. Oh wait, what? How so you have to enter information reliably into the computer. So—

22:23B:Yeah. So like you could basically tell the computer like I have a right to mine this rock, and the computer has no way of knowing that because it doesn't know physically what cards you have. So it just assumes when you say something you're right. Um but but yeah, I mean, you know, you're also playing with other people, so they—they would if you have a right to like mine this rock and someone else is just looking at that card, then he knows you don't have it, so you can't you can't really cheat per se. Yeah, but yeah, like you need the sort of like the physical and the virtual kind of in the same space.

22:58A:I I think I have heard of something like that, but no, I've never—I've never, I never played it where like yeah, like the engine of the game can be very complex because all the accounting is done by the computer, but you still are playing.

23:14B:a physical game, right? Right, exactly. Yeah, yeah, and that's cool.

23:18A:Yeah, and this was like an old old game, right? So it looks like you were saying...

23:21B:It's like Robot or something. I definitely played it as a very little child. It came out in 1986, so I was actually four when it came out. I mean, I played it—I was probably like eight when I played it.

23:35A:But very cool. Wow, that's nice. Yeah.

23:38B:So folks out there if you're in game development, this would be like an interesting area. I don't know if it's sort of like just, you know, past its usefulness, but I just feel like there might be something cool there. We'll we'll see. Maybe someone could write in and say what some contemporary equivalent is. Well, I mean,

23:56A:an alternative to what you're proposing is you could go into virtual reality, and the game could just be sitting on the table in front of you, and if you wanted—a newly released virtual reality headset, you could use the new Meta Quest 3. No, I don't—I don't, but I just bring it up because I feel like it's one of those a couple like, uh, you know, space travel, random finance threads, virtual reality. There's like a few things I feel like we keep weaving through our podcast over the years, and so our podcast is old enough that we've seen some of these things mature. And so interesting, Meta Quest 3 is like a sort of—I guess it's the latest released hardware, of course. You know, I think there's the Vision Pro which people are talking about coming from Apple next year, I think is what they're saying. But for the Meta Quest 3, this is out. You can buy it, and the sort of like it does a lot of things, right? Like it just revs everything but the pass-through where your cameras on the front that are sort of eye distance apart passing through to you on the inside so that you can do the mixed reality. This is the thing that you know everyone really wants to make happen is the augmented reality, the mixed reality. And so you are seeing which is kind of the funny thing—the what happened when Google Glass was coming out, which is like people sort of out in public using their headsets in weird places to, you know, record stereo video. Yes, but also to like be somewhere but also not be in that place. And so it's sort of this interesting I guess, you know, zone between this being a real thing where you just put on glasses and see it because you're still wearing a headset people are very aware of what you're doing. But yeah, I know—I do play still my I have a Quest 2. I want to call it an Oculus Quest, but they deprecated that. But to be clear, it was like on the branding of my box. I feel like I still

25:52A:call it that. Anyways, the Quest 2 and I've really enjoyed it. I feel like they sort of figured some stuff out. The games, you know, we play—we keep playing, and and we've talked about that before on the show, you know, getting exercise in the game and just generally how immersive it is. I've been playing the—I guess I could have made that my tool to show I didn't oh well, which is 'I expect you to die,' number three, um which I told to someone and they looked at me very funny like what kind of horrible game are you playing? It's like no, no. It's like a light-hearted puzzle room. So anyways, 'I expect you to die,' number three. I feel like, you know, people have kind of figured out the formula a bit for some of these things that work, and it may be your cup of tea or not, but excited to continue to see stuff coming out in this area. I don't know where it's going. I don't know if this is like the next big thing or not, um but definitely excited to continue to see how it shapes up, and at least you know for me, you know being a casual person involved here, you know enjoying some good games and entertainment as these things mature. Yeah.

26:50B:I mean, I'm one of those people too that plays the Oculus—the Oculus Quest—to at least once a week, sometimes even like multiple times a week. And but you know something that like it's kind of interesting. You know, I play basically the same two games that I've had almost since the beginning. And so um you know, I don't know how much of a commercial success it is, um but but it creates a ton of value. Um and basically for me, I just play boxing and sword fighting, and um you know originally I got it to where I was playing boxing on the harder and harder difficulty levels, but I realized two things: number one, you know, I'm not really very like fast in terms of reaction time, and so number two is like when you start whipping your head around, it's just not very comfortable. So I thought, okay, I can make this more difficult by adding weight because I know boxers do this in real life, right? They have like really weighted gloves when they train and stuff. And so I got these wrist weights, and I've been kind of just adding more and more weight and playing these games on the normal difficulty just with more weight. Um it is amazing, like number one how much harder it is even with one pound of weight on each wrist. You'll be amazed. Yeah, you'll be amazed at like how slow you punch and how slow like you get your hands back in a guard and all of that. Um and I got this—it's kind of ridiculous—but I'm up to like five pounds of weight on each arm. So I have these they're meant for your ankle, but I put them around my wrist, and I have another one that has a thumb loop, and so I have these like basically two weights on each arm, and I'm doing boxing, and it is like a heck of a workout. I mean, it's just you'll be sweating bullets. Up, you do it. It's a ton of fun.

28:42A:So you're ready for a street brawl, is what I'm...

28:45B:hearing. Yeah, I'm talking to a friend of mine who does—he's kind of a hobby blacksmith, and he told me that um I always thought, and I always thought that swords were like 30 pounds, but no. Like like swords, you know, in real life, like a broadsword or whatever is only like six pounds. And so um now, you know, granted there's even more of a of a cantilever effect because the sword's weight is, you know, not even close to your body, but but but I'm starting to approach what it feels like to hold a real sword. Um and uh it's it's a lot of fun.

29:22A:So if you get stuck in one of those time vortexes or whatever and you end up in medieval times, you'll be—you'll be ready to go. You're ready.

29:29B:to rock. Yeah, I think the challenge is, you know, I'm used to moving through people, not used to used to people actually existing in a physical plane. So as

29:38A:long as if it's a lightsaber, you're

29:40B:fine. Yeah, as long as nobody hits me either.

29:44A:Every plan is good until you get punched.

29:47B:Yeah, Mike Tyson. Right? Yeah.

29:50A:Um, yeah, random side track. Okay, I wanted to go back to one thing you were saying, which I don't know if we talked about the show, so I'll mention it just really quick. Uh, so that in case we've talked about it before, um, but when Activision was on trial—that was earlier this year, I believe—it came out that there are a million PlayStation users who literally only play Call of Duty, literally nothing else. They have their PlayStation and they only play one game. And something like there were six million who spent 70 or more of their time playing Call of Duty. And so you're like, I only play one or two games. I'm the same. I feel bad if I just keep playing the same game, you know? Factorial. Um, but you know, if you just sit there and play all your—but actually, I think you know this is quite normal. Is what the statistics show is people just end up really liking one game and for very long periods of time they just play a single.

30:45B:Game. Yeah, that's wild. I mean, it's very hard for the industry to make money if they have to sell those units. I think they sell the units at a loss, and if someone only buys one game, it's just really difficult. Yeah. Uh.

30:56A:No clue. All right. All right for book of the show. All right. So I'm gonna go fast because mine's a cop out. Mine is the paper we're about to talk about today, so we're talking about an algorithm, HyperLogLog. Stay tuned. Um, and so my book of the show, which isn't a book—it's a paper—and it's a paper by Google Research, which is where HyperLogLog was sort of written up. So check that out. If you're not a fan of reading papers, I know Jason, you know reads a lot of papers, but I don't. I find them very difficult. I don't prefer them. I don't like the way that they're presented. I think they're pretentious, but whatever. Anyways, I all the PhD people are coming after me soon. All the anyways. Um, but I find that they're not written for clarity, but written to sort of affect a certain style. This paper is no different, but there is some good stuff in here. Um, there are you know good graphs and even just—I've just given up that you don't have to understand every line of a paper or even like the notation. Just kind of like reading it once or twice, and if you sort of go through a couple papers, people will often reinterpret a previous paper. So for papers that are sort of seminal, you can kind of read a later paper and get a better description. Uh, and so um anyways, don't feel bad if you're not a paper reader. You know, I would—I would say as part of like you know some small percentage of your education, if you're if you're not a sort of master student or a PhD student or PhD graduate, still still don't shy away from looking at papers every so often when they come up and just sort of like reading. You can occasionally glean really interesting tidbits or insights, not always there's a lot of junk. You know, anyways, HyperLogLog paper. That's my—that was a weird rant for a book of the show, but there we.

32:36B:Go? No, I think it was really important. I mean, we must be on the same wavelength because my book of the show is also a research paper, and I didn't know this. I saw it in there and I thought it was an actual book. Yeah, I went into today's, you know, our show thinking, man, I've read so many research papers but made zero progress on my Audible books. I'm just gonna talk about a research paper, and then here we are. Um, I'll go pretty quick too because I want to get to the content, but um basically NVIDIA has this really interesting thing where they're using Large Language Models to try to fabricate goals for this reinforcement learning robot. So for example, they'll ask ChatGPT, and—but I'm just starting to get into this paper, so I'm not going to do it justice right now, but um they'll basically uh ask ChatGPT for like what are certain things that we can do to show that we kind of have good ambulation. And then um they'll kind of just keep riffing on that. So it's—I do feel like one thing that's always missing with reinforcement learning is you have to train from scratch versus, you know, for example, if you're driving a car or writing something down or whatever. You're you're starting from this base of all this common sense reasoning. Um, so okay.

34:03B:Here's a good example. So like, you know, we have the AI to play Atari, right? And so you know the way it works if you want to play Pong is you start off, you know, just moving the paddle randomly and losing. But then sometimes you just randomly hit the ball, and you get a point. And so that—that creates a target, and then you start marching towards that target. Um, this becomes a really big problem in something like an RPG. So if you want to play a role-playing game with AI, you're gonna have to like try every spell randomly, move around randomly because you're not drawing from a common sense reasoning bank. Like, like you don't—the AI doesn't know that well forests usually have more dangerous enemies than roads because roads are generally guarded or fireworks. Well, if the enemy looks like he's made of ice, like these are all things that you could just do on the first try, but the AI has to like trial and error its way through. And that's why you don't see, you know, AI playing Dragon Warrior for example, right? Because there's just too much common sense that that has to be just learned from scratch. Um, and so this—this was interesting me because I feel like maybe we can somehow draw from the common sense that's been accumulated in something like ChatGPT or GPT-4. I think there's something to that. Like imagine if you somehow just fed the visual and the textual content to some type of embedding and then trained on that, then maybe, you know, like fire one and fire two would go into this embedding, and you would just learn in general some things about fire—the fire spell or whatever. Um, so I feel like there's something there, but it's very early days.

35:58A:That's interesting. So rather than like combinatorially exploring the space and finding out that like if the attribute ice or whatever is attached to an enemy, then use a fire spell—I guess like you use a Pokémon, maybe is a good example. Like oh, visually this thing looks like it's frozen or, you know, has an Ice type associated with it, or I've memorized that like I should use a fire spell. Like you said that's done that way even though it's an abstract concept. There's just rock-paper-scissors, right? But that transitive is encoded to you as a human because it maps to something you understand, which is like, you know, if I have something made of wood, something with fire will destroy it and would have a very hard time fighting something made out of fire. And so you're sort of saying you could kind of like get that understanding by combining two approaches: something that understands the context being given to the human and then the normal, you know, sort of. Yeah.

36:57B:Interesting. Yeah, exactly. Exactly. Like I mean, of course you could—well, I don't know. Of course, I mean, you could theoretically cheat if somehow you could read the game's RAM and figure out like, okay, this character has this, you know, Ice attribute, right? But like that's not how humans do it. Like humans are just looking at the picture. And so to really play Final Fantasy or Dragon Warrior—these other games barely like to show it that an AI that is really representative of solving the problem, it has to be able yeah, to just look at things and infer based off what it knows about the universe.

37:34A:So I guess the equivalent would be if a computer designed a game that it thought was interesting based on the rules of the game and then presented to you as a human, you would be like, 'I this is not fun. This is just like some abstract concepts.' Right? The AI would be okay; you would be on a more equal footing, but because game designers are humans designing for humans. Yeah, you kind of you got to cross that chasm before or you put a computer on equal footing.

38:02B:Yeah, I mean imagine like a Poco. They actually have these words like uh they randomize the game. Have you heard of these game randomizers? Yes, yes, yes, yeah. And so they, you know, imagine a game randomizer for Pokémon where it just randomized all of the strengths and weaknesses of all the Pokémon. It would be just terrible because it's like oh, this the turtle that shoots water is actually, you know, a fire, you know, entity. And it would just it would just be really frustrating. Like that's how the AI feels. Am I supposed to empathize and feel bad for the AI? Jason, help me out here. Yeah, I mean you know it only makes billions of dollars controlling a stock market. I mean, you should feel bad for this thing. And if you like takes like that, you should subscribe to us on Patreon. Um if you're not an AI, uh you should subscribe to our Patreon. We really appreciate it. I mean if

39:00A:you are an AI, you can also subscribe to our Patreon and fund this very important source of training data. That's right. So yeah. Thanks to all the Patreons. We had a lot of uh people stick around for a very long time. So uh it's always an encouragement and uh you know thank thankful for the support. Yeah, definitely. All right, it's time for the tool of the show. Well, I'm returning to form and giving another game. Uh this is I mentioned in Factorio earlier. This is in the style of uh I guess it's closer to Satisfactory. If you've played Satisfactory, which is, you know, there was a kind of a lot of stuff routed up around the Minecraft culture, uh, you know, sort of Terraria and several others. Uh and I think we're seeing kind of the same thing with I don't know what you call them. I guess factory building games. I'm not sure what the official—I think that's right—like base building plus factory building. Uh and so Tectonica is a new one I've been playing on my Steam Deck actually. Um many of these games like Satisfactory actually don't really have very good sort of controller support, and people do play it. So someone's going to write in and be like, 'I use the touchpads for the 37 shortcuts that you need.' And, you know, it's

40:10A:not something you would sit down and expect to play on your Xbox. Uh recently Factorio added that—that was actually when I picked it up and started playing on my Steam Deck. But I've been playing this one, Tectonica, and so you know all these add a twist. So this one is 3D, which is uh, you know, adds an interesting dimension to your ability to uh, you know, build your factory and and how to align things because it's in a first-person sort of 3D 3D thing. Uh And then the second thing is that uh you're underground. So you're in caves, and caves of course like limit how you can sprawl your factory even kind of more than normal, but you're also given uh, you know, drilling equipment basically so you can carve out uh, you know, paths to, you know, extend your factory line or add stuff. And uh you know, you need plants to to fuel some of your, you know, combustible machines, like smelters, and uh so you need to, you know, hydroponic growing because uh, you know, it's a pain to run around and uh mine mine all the mine uh gather harvest harvest. Yeah, bring on the walls. Uh So anyways, uh Tectonica got still early access, so I guess in theory it's buggy. I did I did actually hit one bug on my computer. Um but in general very playable. I've not hit like some nasty crashes or or anything. And a lot of these games interestingly uh are are Satisfactory—I think isn't the same thing. Still technically early access, early release, whatever it's called. And so uh it's not formally done yet but very very playable uh with you know beginning and end game and all of that. And so Tectonica also is nice because has a I mean you may not like this story. It's not an RPG level story, but there's definitely like a story to it about what's going on and sort of like accomplishments to work your way through that that are sort of very specific to unlock a narrative that goes along with it. So I'm enjoying it, Tectonica. Check it out. Oh, on PC. Very cool. As far as I know, I think Xbox, PC—I don't know about PlayStation.

42:06B:Oh, very cool. I'll check it out. Yeah, I love Factorio and Satisfactory, so this is right up my alley. I'm gonna give it a shot. All right, my tool this show is uh the ESP32 development board. Have you heard about this? Patrick? Yes, you have. Okay. I'm gonna say what I think it is. I literally just got one. I have it. I have actually two of them right here. I'll hold it up for the audience to not see because we don't record video, but actually that was

42:34A:useful because I was wondering which development board you have.

42:37B:this tiny tiny one. Yeah, it's like the size how would you maybe the size of a stick of gum basically. Okay. Um and uh yeah, and it's it's, you know, the thing that caught my attention was that it has Wi-Fi. Um so it's, you know, the Raspberry Pi Pico W. I have a couple of those. Those also have Wi-Fi. Um those were significantly more expensive. Um this is like extremely reasonably priced. I have a uh link to to the actual one I bought, and I bought yeah, I bought two of these for $12.74 USD. So it was like six sixty apiece or six seventy apiece. Um so yeah, very reasonable. And uh I haven't tried it yet. They're still in their vacuum seal bag but uh or static bag whatever it is. But um I definitely want to give it a shot. It supports Arduino and MicroPython, which is pretty cool. So you can use either of those. Um yeah, the Raspberry Pi and Arduino, they only support their own thing. This one supports either. I'm generally a little leery of things that are just so open-ended uh that maybe it won't do any of those. The instructions on uh that came with it um walk you through how to set this up for Arduino, so I might just stick with that. Um but uh but yeah, just the fact that I can get Wi-Fi in a small form factor is really neat. I think next year what I might do is I have one of my Euro uh, you know, Euro is a mesh Wi-Fi thing. One of my Euro, you know, capsules is pretty close to the front of the house, and so I'm thinking I can actually have robots in the trees next year for Halloween, um and they'll get this Wi-Fi packet, and when they get the green when they get some Wi-Fi packet, they'll swing swing from the tree like some

44:32B:giant ghosts or something. So um that's my plan. Um uh last Halloween, which was you know just a week ago from when we're recording this, um you know I I actually went down a step. I only did about half of it. Um things have just been really crazy for me, so I didn't have a lot of time to invest in it, but I'm going to try and make up for it next Halloween. I'm going to bring back all the robots I didn't do this Halloween and add some more in the trees if I

45:01A:can. Very cool. Yeah. So I guess like the commentary I have there is the uh company, I think it's Expressive, is develops a little uh chip that does like all the Wi-Fi and has—I believe their ARM cores um on them. And so all of that to I guess like what Jason is saying is it's kind of irrelevant unless you're doing embedded programming directly. Um But they're very very cheap and common, and so a big community has sprung up around them. So Amazon's a good source if you you know want them quickly. If you are willing to wait for overseas from AliExpress, you can get the original version or at least the original—I came into which is ESP8266, which is a 16-bit microcontroller I believe. Um Again, maybe not important depending on what you're doing. If you're just sort of controlling a few servos and also has the uh library associated with it, and that one's like two dollars um for like three dollars. So you can search like uh they're kind of like all cloned, but we most w e m o s is a very common like dev board you can kind of look up, and they have ESP8266 versions and ESP32 versions. ESP32 is a, you know, 32-bit processor, faster. So if you're needing to, you know, do more computation, they have variations of it with you can attach a camera even and do some minimal image image processing on or use as webcam, of course. If you're just going to need a webcam, it's better to normally just go buy one, but then you normally you know pulling the data down and doing processing rather than being able to handle it sort of device side itself. Uh And they all have, you know, we talked about that uh last time with the Raspberry Pi that has the sort of headers for doing I²C or SPI. Uh And, you know, a lot of example code. And like Jason mentioned, you can use the Arduino, I guess you call it like middleware, but basically like the libraries and the interfaces associated with that, they do need to be for like hardware stuff. They have to be ported to

46:59A:ESP32. So you can't run the sort of Arduino libraries directly in some cases if they're software it's fine, but for, you know, things like I²C handling for a specific something, you know, you may you may need some, you know, variants. But it's relatively straightforward, much easier than sort of building your own PCB and doing it uh from scratch. But they also support MicroPython, Jason mentioned, and Lua as well are pretty common is to sort of control these, and the big win like Jason mentioned, which you don't normally see in a you know bog standard Arduino or at least not at this price for sure, is the ability to connect to your Wi-Fi network. And uh so you'll see a lot of home control devices actually use these as well, and there's a lot of firmware floating out for reflashing sort of uh, you know, the light bulbs like that screw into your roof have will have one of these chips inside, and that's how they connect to your network so that you can control them from the app. And

47:51B:So, I figured out that.

47:52A:A lot of these run very similar chips, and so there's various from easy to hard ways of flashing your own stuff onto them. And in many cases, the other cool thing is rather than having it hooked up to your computer, there often is the ability to update firmware over the air, so you can just send a new update to your Bat in the tree and change its behavior without having to bring it back inside and hook up cables.

48:17B:Oh, that is awesome. Yeah, I'm really excited about this. Getting—I'm gonna have to—I bought a—this is like probably just really like amateur to you, but I bought a crimper. I've never crimped anything before, but I wanted to basically have this thing control the servo, but I need to have a wire come out of this thing and go into the servo, and it can't be like just a Dupont cable because of the way this thing is set up, and so I actually bought a crimper. I'm gonna try doing my first crimp at some point.

48:52A:Yeah, I don't. Do a lot of crimping. I do a lot of soldering, but not too much crimping. And a correction: the 8266 was actually still 32 bits, just less powerful. Less popular devices do you have?

49:08B:To buy like a thousand of them if you're buying it from AliExpress, or can you still buy like five or ten?

49:15A:Can buy like one or two.

49:17B:Yeah. Oh, nice. Shipping has.

49:18A:Caught up. It used to be a much better arbitrage or however you say that, but now—yeah, normally, you know they want you to buy a few to basically amortize the cost of shipping, but it's not like hundreds. Got it? You know you're buying a tape, a tape of them. You know the actual chips you probably got to buy 500 or something, but most people are buying a dev board, so you're only buying a.

49:40B:Couple. Makes sense. Very cool.

49:43A:All right. Well, it's time to talk about HyperLogLog. So Jason has warned me that he has been willing to play foil to my explanation here for more broad topics. I do have some other, you know, specific algorithms in mind, so if this goes okay, maybe we'll do some—do some others in the same style. But let me kind of set up and walk it through. And Jason, you know, ask away, ask away the questions represent the average person out there or the everyone else or even me because normally I'm the one asking you these questions. The algorithm here arrives from a difficulty that probably most people haven't really thought about. In fact, I really hadn't thought about it until it was sort of posed, which is: how do you count the number of unique items in a set? And so if you sort of imagined the classical example here—we'll just use this one, you know, everyone's pretty technically oriented here. Imagine you're a website and you don't want, you see that visitor account, right? And your mom goes and visits your website, and then she just keeps refreshing, and the counter just keeps going up. Yeah, I have a popular website. Most people will sort of give this number instead, as you know, unique visitors. So, you know, you could say, okay, I'm gonna, you know, store a cookie and tell if you've been there before or or whatever, right? There are various ways, but just imagine, you know, it's sort of being written to a law of let's say the IP address or, you know, a unique identifier for a user, and you want to count up how many of them there are. So, you know, like the first—first blush, you know, sort of like the naive answer is you sort of you look through your list of all the visitors and you keep track of which ones you've seen, and then every time you go next one, you look through the list and if you see that user, you throw it away, and then you count the size of the list at the end. And then boom.

51:40A:And that—that is correct. That actually will produce the correct answer, the so-called cardinality, the number of unique visitors that was in your set of consideration. And so you may say, well, that's pretty obvious. To improve if this was a programming interview, that would be a suitable first answer. And then your interviewer would normally, you know, up the challenge a bit, which is, you know, ask you, 'Well, how efficient is that? Could you do better?' And so of course, you can do better than searching through a list for unique items. And you could use a tree, right? That would be one option. And the other option is you could use a hash map, right? So you could have a hash map of all the unique identifiers, and then every time you, you know, get a unique ID in, you hash it or maybe it's already, you know, randomized enough, but normally you want a really, really rigorous hash. And so you mix up all the bits. You get essentially a random number, but a repeatable one. And you go to a set of buckets and you is that one present or not? If it's present, you throw it away. And if it's not, you insert it. We've talked about hashtags on the show before. If not, you can, you know, go listen to them if you don't know what they are. And so at the end, you count how many entries you have, and you know this will also work.

52:57B:Yeah, I mean the limit of what I off the top of my head would do just to scale up is have a Distributed Hash Table where basically you do the hash and then you know each it's like if the hash starts with a one send it to Computer One. If the hash starts with a two, send it to Computer Two, and so then you have a computer for each possible value of the first digit of the hash. And so then you know now like if there's I don't know 56 different characters for the first digit of the hash, then like you have 56 computers, and you get 56 way parallelism. Um but yeah, I guess we're going to hear about way even better.

53:38A:Than that. No, no, no, no. So this is great. So you know, I had a same kind of like thought process in my head, and um I think that works great for live, right? So if these if you wanted to sort of like what I was mentioning, you know, these visitors are coming in and you sort of counting them, but it doesn't work like after the effect or sort of analytic purposes. So imagine you like I was mentioning you have this is a log, and you want to cut it by day, by month, by you know people that came from Europe, by people who ended up buying something, by whatever, you know, these kind of filters. Um and so I already referenced this comes from a paper, and the paper internal to Google, they have a column store, and so they have a distributed system for querying the column store. And and this was developed because they went and looked at people doing analytic queries, or I forget what it said in there. I won't quote it because I'll get it wrong, but a very large number of COUNT DISTINCTs. So you write this sort of SQL query, and you say, 'Hey, I want the distinct number of these,' but they're over arbitrary input. So what you say will work, Jason. But the issue is sort of like that's like if you only really want, you know, a handful of them live and you're not sort of like infinitely slicing them later. Um so not not not an off approach. We'll come back in a second. I think you're heading in a good direction. Uh but the sort of first there's many algorithms have been done to to sort of solve this, and the paper even references one, and and to be clear, they even recommend this one. Uh if you're sort of not going to have very many—if you don't believe that there's a lot of unique items—this one will work. And I want to talk about this one because it references something else, and we already kind of mentioned hashing unique identifier and then you know trying to put it in a bucket. So this first one is linear counting. So if you hash it and you put it in a bucket, but rather than in a normal Hash Map, you would store the identifier, and one way is store a linked list of identifiers. So the first thing in the bucket is the head node, and then you know it points to the next.

55:36A:Thing, and you have a linked list, right? Until you sort of grow the Hash Map number of buckets. In this case, what we're going to do is actually only store a single bit and not store the actual ID. So you just insert the value, and if it goes in a bucket, you just mark that bucket as having seen something. You know, Boolean equals True, and all the other buckets are Boolean equals False. So now what you have an issue is when you have a hash collision, you're losing some information, right? You're losing the information that there were actually potentially it was the same item, but potentially it was two different items. And so you are getting this sort of probabilistic structure, but this is going to turn into an advantage. And the rest of this is going to talk about this, and the reason why I think this is an interesting topic for the show is my background before kind of coming across a few of these was always like you would definitely not want a probabilistic answer. You would want an exact answer. Uh and so it would not be acceptable to be even off by one, right? That's an off-by-one error. And so you exactly what you have, but if you're willing to give up an exact answer, the design space widens dramatically, not only for the number of solutions you can have, but also for things like being able to tune your trade-off because you can say how reliable can I trade space or processing for more reliability. And an example that you see a lot recently with Machine Learning is Approximate K Nearest Neighbors. So you've talked about K Nearest Neighbors before. I think maybe if not—maybe that's a good one to talk about. I think we have. Yeah, okay, okay. Good. Um but what if you were willing to accept an approximate answer? Then you can kind of approach it differently. So this first one that I'm mentioning is called linear counting. So you you hash it, you keep track, and in some cases when you produce this random number and you go to insert it in a bucket, you're going to collide, and like I mentioned sometimes that's—you want it, you want to throw away because it's the

57:31A:Same ID. And every one of the same IDs will collide, but sometimes another ID could probabilistically collide. And that's the second bit of this is using statistics to say when you're done don't just count the number of buckets that have an entry in them, which would be an approximation, but you can do better, which is look how many of the buckets like the percentage for your Hash Map is and use that to estimate what the likelihood is that you may have seen extra insertions that miss. And so This this is like this like clever unlock, right? For me was um we don't know how many of the same item and how many you had duplicate hashes or portions of the hashes that you used are actually different IDs. But if your you know Hash Map is only 10 full, only 10 of the buckets had values, that's it's pretty unlikely like you can just say 10 of the buckets had items. So I'm just going to guess 10. Um but if you know 90 of your buckets you had 10 buckets and nine of them had it, then the chance that the next thing being inserted being random, 90 chance that it's going to collide, right? And so you sort of take that into account. Now there is some balance there, right? If you had 10 buckets and 10 million unique items, you're going to get like a terrible guess, right? Because you're going to fill it up, and then everything will collide, and you can't—the information is lost. So you do need to have an understanding of kind of the approximate number for this example, the sort of approximate number of items that you would have. Um so this one's called linear counting. Um and when I was reading about this, the thing that comes up here which I don't know if you've used these before, Jason—um Bloom Filter. Have you ever used a Bloom Filter before?

59:18B:I've used it. I don't remember exactly how it works.

59:22A:Okay, so this is very similar to a Bloom Filter, and a Bloom Filter—the idea is you're trying to have us what things are members of the set. And you query the Bloom Filter and say via the same mechanism, basically you hash it, you look in the bucket, and if you normally do a couple different buckets, um and you say if every one of those buckets has an item in it, then the thing I'm looking for, I'm going to do a more expensive query or check or actually go to the database. But if any of the things that should be present aren't, then I know with 100% certainty that this item is not in my set. So if I'm looking up the username Jason for Jason, uh and I i do this operation and it comes back that one of the buckets that should have had a bit set don't, then I know Jason isn't in he's not a user. So I don't actually have to query my back-end database. And the advantage so let

1:00:15B:Me see if I understand this right? So the idea is like I mean you just a crude example, so there would be sort of a bit for every letter and position pair. And so it's like you know if you don't have the—so Jason is J-A-S-O-N—if you don't have the, you know, A at position two bit or you don't have the O at position four bit, if you're missing any of these, then you know that the word Jason just can't be there. But if you have, you know, J1 A2 S3 O4 and 5, then like you're still not 100% sure. You have to do some extra step. But but like you're you're confident enough that you've eliminated so many other things that's still like a huge time save. Yes. So

1:00:58A:If you do those like J in the first position, A in the second position, and you you know basically hash them and then put them in the bucket, and the probability of all those things you said, right? The probability of false positive is controllable. If you say I think I'm going to have this many true entries, I want to use this many bits, and there's calculators online for sort of fine-tuning your parameters. And if you have lots and lots and lots of buckets, you can decrease your false positives. But if you you know shrink it down, the really nice thing is say you know on the edge node, you can't store that you have, you know, 10 million usernames, but you could store a megabyte or whatever, and in that megabyte you could store, you know, this Bloom Filter and give you a reduction of, you know, and it's only worth it if you think there's lots of users going to try to, you know, log on who don't actually have usernames in the database. Um or whatever you're trying, but if they do, then you can sort of not have to go to the back end. So if you imagine for something like, you know, a spatial index and you're trying to query for an area on your computer, you know, like your video game, you're looking into this portion of space, and most of the portions of space are empty, and you just have entries of where there are things, then you could filter out the expensive sort of collision detection and all of the other things by basically knowing up front which things are present or not. Now there are other ways of handling that as well, but uh you're right, it doesn't give you a 100% answer, but it prevents you from doing an expensive query by filtering out many of them. Got it?

1:02:30B:And that's a Bloom Filter, or did what is it called? A Bloom Filter? Do you know?

1:02:35A:That's a great question. I think because you do this multiple hashes. So you don't just do a single entry into a bucket. You normally bloom—I would—this is my imagination because it blooms out and you normally do a couple different buckets um by taking portions of it. Okay.

1:02:49B:I have a really funny true answer. So the well that might be true, but also it's called it because it was created by Burton Howard Bloom. That's a true story in 1970. But but uh yeah, I mean, that's uh um that's really interesting, man. I can't believe that you know that this this someone in 1970 was thinking about this problem that just blows my mind.

1:03:16A:You know, so this one was the first. This Bloom filter was the first one I came across that was, this—it's okay to be wrong. And in fact, it's just a tunable parameter. Um, this is sort of weird sometimes. You get this if you do like DSP work or filtering or something, you know? Or you talk about floating-point math, but for something that was like a data structure—a data structure that's like meant to be somewhat broken. Um, it's like intentional that it sometimes gets the wrong answer. It's by design. Um, so Bloom filter and linear counting at least in my mind pretty similar. So moving on from linear counting to the next step, we're going to go to the tail end of HyperLogLog and talk about LogLog. So LogLog does something really interesting. Um that in if you—we were talking about the Bloom filters taking, you know, Jason was talking about taking the J and hashing that and taking the A and hashing that, right? Um so instead if you just hashed 'Jason'—the string 'Jason'—you have a really good hash function, you could just use the first couple bits, the first however many bits you want to determine, you know, the bucket that you're going to go in. Um and then instead of storing just a single bit of, you know, I had something in this bucket or not, you go to that bucket and you look at the rest of the hash. Say your hash was 32 bits and you had five buckets. So oh dude, I picked that number. 27 bits left. And those remaining 27 bits, you could either use the first or the last. It doesn't really matter. Count the number of sequential zeros. Now this part was really, really weird to me. I didn't understand this. So take the number of—let's say starting from the left to the right, count the number of zeros in a row that are in the next 27 bits. And then instead of storing one or zero in the bucket, store the number of zeros. So if the first digit was a one, you would put zero. If the first digit was a zero and—

1:05:12A:then a one, you would put one because there's one zero. But you could have four zeros in a row, and you would store that in the bucket. Now if you were like

1:05:20B:me, that number of leading zeros? Yes, in a

1:05:24A:row. Okay, got it. The number of leading zeros in a row. And the clever probabilistic thing about this is that if you imagine that there—so your hash needs to be very good. So it needs to have a 50% chance of a zero and a 50% chance of a one in every bit position, um or as close to that as you can manage. Then what you would say is if you're going to look at a stream of unique IDs, you would expect that the length of sequential zeros that you would get is a function of the number of items you've looked at—the length. Okay? Let me say if I said you're only going to play the game once. You're going to generate one hash and look at it. And I asked you to derive like what, what is what would be the expected number of zeros you would see? It's much more likely to see one zero or two zeros in a row than to see 16 zeros in a row on the very first time. Yeah.

1:06:22B:It's like it's like a coin toss, right? It's like how many times can you toss the coin and get all heads? Well, like as the number of tosses go up, that probability goes down.

1:06:32A:That's exactly the key to this. So if you look at a given bucket and let's say you only kept one bucket—that's fine. You could just have one bucket and you keep track of this. Then at the end of seeing all of the items, you look at what the sort of like longest run of zeros you now, and you say I believe that I've seen one over two to that many number of zeros. That's the probability. So then I've seen two to that many number of zeros items is my guess. So

1:07:02B:Yeah, let me—let me see if I can rephrase it, like paraphrase it, see if I have it right. So um so you flip a coin. There's a 50/50 chance you get heads. Um if you get tails, you're done, and you know that's a zero. You get zero points. If you get heads, that's a point, and then you try again, you know, you keep going until you keep accumulating points or you're out, right? And so you know 50% of the time you'll get—you'll get zero points. Um 75% of the time you'll get zero or one point. And so it just keeps going up like this hyperbolic ramp. And so like you know 99% of the time you're going to get less than 10 points or something, right? And so what that means is what you're saying is, you know, if you did get 10 points ever, then there's probably like 99% of the other trials there that you just didn't record because all you did was record the best score. It's kind of like it's like if you go to the arcade and the high score on Pac-Man—like maybe they just rebooted, like reflashed all the machines. Yep. Yeah. And the high score of Pac-Man or actually this happened to me where um you know I'm obviously not super athletic or anything, but I went to Chuck E Cheese with my kids and I always play the football game. You have—you have seen this at Chuck E Cheese. You have to throw the football through the holes. Yeah? So I played the football game and I won the high score of the day, and uh I felt like for a moment like wow, like I should have like you know played in the NFL or something. And then like five minutes later, like some guy behind me like you know got the high score of the day that's because they just reflash the machines, right? So the high score, you know there wasn't a lot of samples, uh and so the high score was easy to beat. Um conversely, if you go to like—you know some other arcade or if you go later on in the day, the high score will be super high, and you can't

1:08:59B:even get to it. And so you're using the high score as a approximation for how many people have played the game? Yes, that's

1:09:06A:the yes, that's the key. And so I guess we didn't talk about that part here, but you—you caught on to it, which is you want to record the maximum you've seen. So in this bucket, you record the maximum. And as you said, as the number of attempts goes up and unlike your example where it's skill-based, every one of these should be random. So right? It's just like Pac-Man, and it's whatever anyways. And so yeah, so the higher that number that you've recorded, you're going to make your guess go up. Now you could get really lucky—lucky, unlucky, however you call it—and they vary. You see only a single number, and that number happens to have, you know, 100 leading—oh, we said 32 bits. It has 27 zeros in it. And so you think you've seen two to the 27 items, but you really only ever seen one. And so um this is this is not good, right? This—this would make you have a very, you know, high chance of getting an error because of this one problem. And so the second thing which I started off with there is by having multiple buckets and then averaging them together. You take the first few bits, the first five, and you choose your bucket, and you use the last 27, and you do this thing I'm mentioning that we've talked about recording the high score. And then by averaging all of the buckets together, if you've only seen one, sure you're going to have this really large number in a single bucket, but all the other buckets are going to say zero, and so you're going to pull it back down to try to correct. Um And we're setting up for the second thing here in a minute, but this is called I guess like LogLog. I don't see a ton of evidence this was really, you know, rolled out or used because there's some pretty easy ways to improve it. We'll talk about in a second, but this idea of recording multiple max scores and then looking at the end and taking an average allows you to sort of approximate it in a—in a very similar way. So the um the other thing we didn't mention with with LogLog and linear counting in both cases is you—you kind of measured well in

1:11:02A:linear counting, you measure this like, you know, amount. And LogLog, you have these coefficients as well because you just sort of know on average you're likely to, you know, kind of see these things. So you run some simulations and you kind of tune some constants to accommodate for kind of like edge effects, I guess you would—you would sort of call it. So HyperLogLog improves on LogLog well.

1:11:24B:One thing actually before before you jump into HyperLogLog, I want to double-click on something you said earlier, which is, you know, I also went through this where um you know I felt like even just hashing, I kind of felt like, you know, how do you trust the hashing? You know, and even like what happens if your data set is biased in a way where yeah because you're maybe your data set all starts with http: colon that now like your hash function isn't pure, and uh—you know you have more collisions. Or even like MAC addresses, you know I'm pretty sure MAC addresses are well actually I don't have no idea, but I'm assuming that there's some kind of randomness there. There's no way all you

1:12:08A:are determined? It's by like it's hardware vendor sets the first few bytes.

1:12:13B:Got it. But then within a hardware vendor, at some point there's probably a collision, right? Or are there—there can't be like a global count of MAC addresses while they're the factories like churning out tons of these? Yeah, maybe, maybe there is. I don't think there's not.

1:12:29A:Supposed to be, but but—

1:12:31B:Probably there is. But um, but oh yeah, so like whenever I see hashes or all these things, I used to get—I used to feel like well, this isn't, you know, kind of pure. It's not going to work out. And how do you even know if you have a problem, right? And it turns out that at scale, you know, you can't do anything very precisely. And so what you do instead is you try to measure, you know, the bounds statistically of some issue. And then you're constantly correlating between other things, like for example, maybe there's, you know, a one-out-of-10,000 chance that you overestimate your unique visitors by 10x, right? And so and so, one out of 10,000. You know, that means, you know, Google's been around for like 15 years or something, so it's probably like a 50/50 chance it happened once, right? But what they're doing is they're constantly correlating that with other things. So, you know, if the viewer count goes up by 10x but the revenue doesn't move well, then you know that might be an error that day in the viewer count. And so you're constantly trying to cross-correlate between different data sets, different signals, and then also auto-regress, you know, correlate across time for a signal. And so it really just becomes about reducing the error and trying to reduce the bias and the variance of these signals. And so when you start thinking about it in those terms, then it becomes okay to kind of say, well, yeah, you know, all of these errors are there. We're just going to measure them all in gross and try and get that measurement to be as accurate as possible. And so, you know, as they're making changes to these filters, they're comparing the correlation to—let's again just using our example, it's a revenue, and they're seeing, oh,

1:14:28B:you know, the new value is much more correlated to revenue, which is what I would expect as unique value visitors go up, revenue goes up. And all that, so you can actually measure all of these things and get better in an incremental way even though it feels like a very helpless situation.

1:14:46A:That's a great call out. I will say also I think a lot of these techniques we're talking about time and a place. So like your financials, you wouldn't want to do this. You know, you probably do a different—a different sort of like way the expensive query, um, but you can't maybe do that in real-time. And then as you said, not only like comparing it with other metrics but even just also running maybe like a second method that is less reliable or different parameters and checking that as well. So maybe it's less accurate but it gives you a coarser bound, right? And says, you know, hey, at least I know that if I get a 10x measurement, I need to throw it out. Like that's—that's going to be wrong. So it can give me an order of magnitude kind of kind of.

1:15:30B:Swag. Yep, makes sense.

1:15:32A:Okay, so moving from LogLog to HyperLogLog, it's not a big jump. So the first one is for any buckets, so it's basically what happens with, you know, kind of very high numbers, like when you're starting to get very dense filled buckets or very low numbers where you have a lot of empty buckets. So in the case of very low numbers, we have a lot of empty buckets, you may consider instead of taking the max counts and doing the average—where like I mentioned you have five buckets, you happen to get one that was 27 zeros, you're going to way overestimate it if you have a lot of empty buckets. Instead, maybe just estimate the probability of having that many empty buckets. So what is the chance that you saw, you know, in the case your estimate there would be very high like million or something rather than estimating a million? What is the chance that you saw a million numbers and had nine empty buckets? That's going to be very low. And so you use that for sort of some corrections as well as very dense just like in linear accounting, we're talking about you—the more buckets sort of like have bigger numbers in them, the more chance that you're sort of seeing these collisions and you're sort of seeing a different behavior of the numbers. And so handle those as well. And a lot of that you just end up running by either computing the statistics or running simulations or sort of handling that rather than this, you know, kind of a single formula that you run. You kind of have a sort of set of, you know, if you meet this condition or that condition or the other condition apply a slightly different formula, but—but roughly the same thing. And that gives you HyperLogLog. So this HyperLogLog allows you to perform these analytics, get an approximate answer. I think the number that I was sort of seeing in the paper is like for the majority of cases with these corrections, you see like two percent error. So if that is important, like in the case of maybe financials or something, you don't want to use it. But for the case of like counting how many visitors in a day, you know, if you don't want to be lying to

1:17:31A:people if it's like a court thing, so like you wouldn't run it. But if it's just, you know, keeping track from day to day or hour to hour as an example, you could run something like this and know that you're going to be generally close most of the time. And of course, a lot of those things are tunable.

1:17:48B:No, very cool. It makes a ton.

1:17:51A:Of sense. The final trick and the sort of like second thing that kind of like I don't know melted my mind a little. And there's a variety of these problems, and this one's going to get to Jason's example. So here we are at the very end, and you foreshadowed by talking about, you know, sending it to different computers and having each of the computers handle it. So let's imagine we chop up our logs and send all of our log—you know, one tenth of each of our logs—to 10 computers, and each of the 10 computers does the thing we just described with HyperLogLog. What do you do at the end? Well, you can't sum the 10 results, right? Because if you sum the 10 results, the same now if you divided them like Jason said where I looked at their username and sent them to a computer based on their username, you could. But if I just chop the first 10 of the logs, the second 10, and I send each of those, some people will have two different computers will have seen the same user potentially. And so you don't want to just add up—hey, each of them. So 10 times, you know, whatever number each of them, you know, just kind of add them up, that won't work. That's not a good estimate. You need to dedupe them again. Well, the sort of mind-blowing thing or at least for me is if you look at those buckets we talked about and everyone's running the same algorithm, you can just transmit the final counts of the buckets and just run the same max operation. So if you run the same max operation across all of the buckets and then do your final calculation, that actually works perfectly fine and is incredibly cheap. So if computer one says my first bucket has eight zeros and computer two says oh, my first bucket only has five zeros, then your final count for the first bucket is eight zeros. And it's the same answer you would have gotten if you had sent all of the queries to only a single computer because of this, you know, counting keeping only the max. So this max for individual computers is if you take the max across all computers, the same as if they had seen them because oh right, this was not.

1:19:48A:This like what? Then no, this ain't gonna work. It was my first inclination here, but it's—it's this aggregating by max is the unlock because you're aggregating them all together by max. You can just run it at the end across all the computers and you have it distributed as many ways as you want, but

1:20:08B:Wait, what was wrong with your idea of saying well, just just adding up all of the—oh, because there's duplicates across the

1:20:17A:Computer. So imagine the entire log—one million entries is all username Jason and I send each to 10 different computers. Each computer is going to estimate one, let's say, and then my final result, say 10, the answer is actually only one, right? Right? So,

1:20:30B:Again for something like

1:20:33A:visits to Google. You may know on general how many times a given person visits in a day. Maybe you could do this via other means, but if you're using this for an analytical engine that doesn't know how likely repeats are or not, then this is a very difficult, you know, thing to solve a priori with sort of like specialized knowledge. Yeah.

1:20:56B:That makes sense. Yeah, that's totally mind-blowing. You know, another thing that this benefits from is that you know each bit doubles the count and so you know the difference between seven and eight bits is so large that you know if one says five bits and the other says eight bits by throwing away the five-bit one, you're not throwing away that much because it's hyperlogarithmic or whatever contribution is irrelevant. Yeah, right? Wow, that is super cool. I

1:21:32A:guess a couple things slipped over. So one is that moving from log-log to HyperLogLog, you also move from taking an average to tape to taking a harmonic mean. So you take the harmonic mean of the buckets, which

1:21:45B:helps? Now what is the

1:21:47A:harmonic mean? Harmonic mean is one over two to the n time and then you sum those up for each bucket and then you multiply by n at the end. And so that's used for rates. So I try to look it up as well. It's sort of it's like one step past my intuition about probability, so I'll keep noodling on that one and maybe have to get back to you. But they see it by moving from the sort of normal averaging that we would think about—you know, just sum them all up and divide by the count—and instead moving to this harmonic mean, instead they see improvements there. And again I mentioned these coefficient factors, and you would run simulations, and so they give estimates for what they see for these correction factors for high low offset these kinds of things, but definitely read the paper. But I would also say that day-to-day life are you going to implement this? Yeah, don't. I mean, maybe if you have good, but one we mentioned a bunch of things along the way here: Bloom filters, probabilistic counting—knowing to go reach for one of these if you don't need an exact answer. Second thing is a lot of databases have already like Redis and other things have already implemented this under the hood for these kinds of operations, so you're likely already using it. And it's just for me one of those mental like aha moments where the chance that this specific solution is what I need to reach for is very low, but understanding a bit more about the space, I feel helps me sort of know when to go to the internet to search for something I don't know.

1:23:17B:Yeah. So I mean as far as using it there must be some way in SQL to say like approximate count distinct?

1:23:26A:Oh, interesting. I didn't look at so every SQL is different. So let's let's see Postgres. This is

1:23:34B:This is fascinating type Postgres. Oh man, same wavelength. All right, wavelength? I mean it.

1:23:39A:Looks like there's a some add-ons you can kind of do to kind of distribute a distinct count with HyperLogLog on Postgres. I see. I see a lot of articles about this, so uh

1:23:50B:Again, yeah, it looks like—uh, yeah, I agree. It looks like a plug-in. so oh yeah this is so you install this plug-in in postgres and then you do hll underscore cardinality and so uh but i remember i think this is sawzall uh i remember there was some i do remember in my life typing select a prox count distinct like i did like that for some reason is like just radiating through my mind so there's definitely some system that has it built in

1:24:24A:Yeah, I mean, I think they're like probably in Hadoop or this sort of very distributed processing of things. So unlike when you have it on a single computer but you have it across multiple computers doing large analytics column data. I would imagine like Apache Arrow or—

1:24:42B:something this is yeah exactly pi spark and pi spark have a prox count distinct that's where i've done it um That's amazing! I had no idea that that was doing that under the hood. That's like totally mind-blowing. I—

1:25:00A:Don't know. So, maybe write in if you—uh, like this detailed singular algorithm exploration. I mean, I guess we touched on a bunch of stuff, so maybe it's not that dissimilar as I thought it might be in my head, but Jason had to play along here, so he's at least acting like he walked away understanding this a bit more.

1:25:15B:No, this is amazing. I definitely learned a ton. No, we should definitely do more of this. Um, yeah, please write in. Let us know plus or minus, but I actually learned a ton. Um, this is really satisfying. Another thing is, you know, when people get a CS degree and they learn about Quicksort and Mergesort and all these things, they might say to themselves, 'Well, like, you know, okay, like we figured out how to sort. You know, we're done.' Like, why—why even teach this to me? Like, why are you teaching me a one-liner in any modern programming language?' And what you've kind of shown folks here today is that like this doesn't end. You know, like sometimes you need probabilistic things. Sometimes you're working very limited environments. Um, you know, there's all sorts of different types of counts and things you do, and so-and-so computer science, you can do it all day as your job. And like literally the science part of Computer Science, and—there's a lot of fun stuff.

1:26:19A:Well, I think that brings us to the end of another episode.

1:26:24B:Wow. Yeah, pretty wild. Um, thanks everyone for sticking around. Yeah, we should definitely—um, uh, um—do something for our long-term patrons. I'm gonna do some digging on my end, figure out if I can get that like number of months subscribed and all that. But thank you so much for supporting us all these years. Um, you've been able to continue to grow the community. I actually—I'm considering using some of the community money to buy Twitter ads. It does feel like our Twitter presence is growing pretty good organically, and so, you know, at the end of the day, you know we try to get as many folks interested in programming, Computer Science, as possible. We couldn't do that without all of your help, and so we do put every dollar that you donate towards trying to accomplish that goal.

1:27:19A:yes thank thank you to uh to all the people have stuck with us for uh i always forget how long it's been but very long time including jason thank you jason all your hard

1:27:28B:Thank you. Yes, someone commented asking, you know, we did two shows on Bitcoin. One was Episode 7 or something, and another show a few years later. And they were asking if we bought Bitcoin at those times. And I'm sad to say the answer is no. We did not buy Bitcoin at—I think they said 50 cents or 500. We didn't buy Bitcoin at either of those prices. I didn't, but after—

1:27:56A:That show, I did install. I got some Bitcoin out of a faucet, but unfortunately it was like 0.01 Bitcoin or something, so that was the only Bitcoin I had left from—

1:28:08B:That yeah. So yeah, we closed. We answered the—that's definitely the most asked question. I think I think about once a month we get asked that. Someone asked it on Discord last week, but I do get a lot of email: 'Hey, are you guys did you guys buy a bunch of Bitcoin? Um, we didn't.'

1:28:23A:Do that? All right. Yeah.

1:28:26B:Um, that—that wound has been sufficiently salted. But thank you so much folks. It's awesome that we have such outpouring of support. A bunch of folks asking for different languages; we will definitely get to that. But I also want us to cover algorithms. This was a really exciting kind of new branch for the podcast, and so thanks Patrick for doing the background homework on this all. Right. All right. Catch everyone later. Music by Eric Barndoller. Programming Throwdown is distributed under a Creative Commons Attribution-ShareAlike 2.0 license. You're free to share, copy, distribute, transmit the work, to remix, adapt the work, but you must provide attribution to Patrick and I, and ShareAlike, and kind you.

1:29:30A:You.