Programming Throwdown: Episode 112: Trees – Beragampengetahuan

Programming Throwdown
Episode 109 – Trees

Patrick Wheeler: Programming
Throwdown Episode 112: Trees. Take it away, Jason.

[00:00:21] Jason Gauci: Hey
everybody. So, this is going to be a pretty cool episode. Another duo
episode, as we talked about a little earlier. You know, we got some
awesome folks, literally the company’s called Awesome Pros. So check
them out if you’re interested for your podcast. But we got some
awesome folks helping us out on the, you know, editing, recording
side. So we’re able to produce more content, which is super exciting.

[00:00:45] And, and we we’ve had a bunch of ideas. We have, we have a
whole list of ideas lined up of stuff that we want to chat about. And
today we’re going to be talking about trees, computer trees, although
there is that whole thing about planting a million trees. Have you
heard about that?

[00:00:59] Patrick Wheeler: On
YouTube? I thought, you know, that’s funny. I thought the same thing.
People are going to assume we’re talking about fundraising for
planting trees.

[00:01:05] Jason Gauci: Yeah. You
know, honestly, I don’t know very much about it. I mean, it sounds
cool. Sounds like, you know, planting trees sounds like it’s pretty
universally, like a good thing to do, but no, this is about computer
trees.

[00:01:17] Yeah. We’re gonna, we’re gonna dive really deep into that,
but first of all, we’ll talk a little bit about avoiding drama at
work. So…

[00:01:24] Patrick Wheeler: Dramatic.

[00:01:25] Jason Gauci: You know
(laugh) this, so there is, you know, a lot of sources of
drama at work. There are, you know, political things. There are
various sort of social situations or like, I dunno, social phenomena.

[00:01:39] I mean, there’s also just, you know, other than the macro
stuff, there’s also just like what we call like office politics. You
know, this person, you know, is in a bind, and they kind of
backstabbed this other person. And then, you know, there’s all of
this drama and… I’m here to tell you to avoid the drama and we’re
to give some tips on how to avoid drama at work.

[00:01:59] You know, maybe we’ll just ping pong back and forth. I
mean, my biggest thing, my biggest piece of advice, that really like
it’s, it’s actually, you kind of influence people just by being
yourself. Right. And so you don’t really have to go out of your way
to tell people how you feel about things that are, like besides the
work you’re doing. Right?

[00:02:20] So, I mean, you know, just by being, you know, yourself
and having opinions that you’re proud of, you know, and all of that,
you know, that that’s kind of, in my opinion, that’s kind of enough,
right? I mean, you don’t then have to like engage in like a whole
bunch of these other discussions. And so when I see… and you might
see a lot of things, this, this is true even in your public life, but
especially in your professional life, like you might see a lot of
things and then feel compelled to say, Oh, like, I want to argue with
this, or I want to go back and forth, you know, on this, on this
topic or this issue with this person at work.

[00:02:55] And it’s really important to just kind of take a step back
and say, you know, like, just remember that just your kind of
presence and, you know, in the way that you kind of think about
things is already being expressed just through you being yourself,
you don’t also have to kind of take the extra step.

[00:03:15] Patrick Wheeler: Yeah.
I, I think I hear what you’re saying. I think what you’re saying is
like, by, rather than explicitly having to state loudly, what you
think or how you want something to be, what you’re saying is like,
over time, sort of being consistently acting in a manner, which is
true to those things that you think, then, you kind of like express
them into your work environment.

[00:03:37] Jason Gauci: Yeah,
exactly. And another thing too is, you know, there was a situation a
really long time ago where someone had done something that I felt
was, was not, was not right. Now, of course, like if there is issues
with, you know, harassment or anything like that, you know, of course
you need to speak up. I mean, that is extremely important, but I’m
just saying, I mean, this wasn’t anything like that, but it’s
something where I kind of felt really compelled to kind of, you know,
start, kind of a discussion that that was probably not going to be
very productive.

[00:04:11] And I decided, you know, no, I don’t really want to kind
of get into this kind of stuff at work. And then actually, what ended
up happening is this took a little bit of, it took a while. You know,
it’s not something happened overnight, but, but eventually that
person, you know, ended up kind of losing a lot of their authority
and their, and their seniority and things at work.

[00:04:34] And, and the thing I realized from that experience was.
You know, at that moment, I felt like, you know, there was this kind
of real attack on me personally. And then I had to stand up for
myself. But then, you know, in hindsight it was obvious that, you
know, this person kind of had a problem with everybody.

[00:04:53] It really had nothing to do with, to me. I was just one of
the people that this person was interacting with. And, now there is
sort of a tragedy of the commons. Like you could, you could say to
yourself, well, if no one does anything, then this sort of toxic
person might just continue being toxic forever.

[00:05:10] And so you do have to kind of balance that out, but at the
same time, I think it’s so easy to go the other way and kind of get
into a really big battle that is, you know, ultimately just going to
take a lot of your time and energy and resources and, we’ll just not
really be productive for anybody.

[00:05:27] Patrick Wheeler: This
is going to come across sounding a lot like a self-help.
(laugh)

[00:05:31] Jason Gauci: Well, I
mean, I think it’s, yeah, actually I saw a study that said, the
number two reason why CEOs get fired is actually like public scandal,
which, you know, the number one reason is performance. So I mean,
that’s kind of a no brainer, right? People get fired for performance,
especially at that high of a level. But you know, the number two
reason is effectively, you know, some type of like public faux pas or
something.

[00:05:56] And that’s huge, when you think about all the other
reasons someone could get fired. I mean, they could get fired for,
like maybe they, they had some financial problem. Like they, they had
a financial error and so like, you know, the SEC gets involved.
There’s all these other reasons why a CEO could get terminated, but
that was number two. Right. And so, so yeah, I think it’s a really
poignant topic. And I guess the biggest thing is, is just to always
just keep a level head and kind of keep your cool.

[00:06:25] And, especially, you know, at work, I think, I also don’t
really understand why people argue political stuff over the internet,
but if you’re going to do it at least do it over the internet, not at
the water cooler or something.

[00:06:37] Patrick Wheeler: At
least do it pseudo-anonymously and not in person.

[00:06:40] Jason Gauci: Yeah,
exactly. (laugh) Yeah. All right.

[00:06:43] So that’s, that’s my rant about avoiding drama at work.
It’s so important and it takes a lot of, fortitude, but I think at
the end, you’re always going to look back and say, you know, I’m
really proud of myself for having that kind of reserve. Right.

[00:06:57] Patrick Wheeler: Makes
sense. Yeah. That’s hard to follow up, man. I don’t know. That was a,
a heady opening topic.

[00:07:02] Jason Gauci: All
right. (laugh) We’ll jump into the
news, then. The news is much more benign.

[00:07:07] Patrick Wheeler: Okay.
No, good stuff. Good stuff. Yeah. A drama, ugh.

[00:07:10] My completely unrelated to drama is, my first link is
C++20. New features with example, this article that I found shows
almost all of the new C++20 core features, and gives a little like
code snippet for how each of them works.

[00:07:26] Now, this is obviously like gonna make sense to a subset
of the subset of a subset of our audience.
(laugh) I always find this like, it’s so useful because to me,
I always, someone was showing, you know, recently we went to C++17 at
work. And although, you know, that’s an upgrade install a few years
old, it takes a while for these things to kind of roll out if you’re
not familiar with C++, and someone was like listing off the new
features.

[00:07:51] And all I’m doing is like, I don’t even know what that
means. Like, what was it? There was like the ternary operator. And
I’m like, I don’t even know what the, or the trigraph. We knew what
the ternary operator is, but there’s something like the trigraph
operator has been deprecated in C++17. Like, I don’t know what that
is. Like,go look it up.

[00:08:08] Jason Gauci: Is that
the thing with the question mark in the colon?

[00:08:11] Patrick Wheeler: That’s
the ternary operator, that one’s still good.

[00:08:14] Jason Gauci: Okay.

[00:08:14] Patrick Wheeler: But
there’s a trigraph operator, which I forgot. I don’t even remember
what it is now. It’s like question mark, angle, bracket, angle
,bracket, or something.

[00:08:21] Jason Gauci: What?

[00:08:21] Patrick Wheeler: And I
(laugh) didn’t even know it was a
thing, which is why it’s been deprecated.

[00:08:26] Anyways. So seeing all this, like this was super helpful
for me to be able to realize like, what these named things actually
meant, because I know it means something very specific and language
is very important, and the C++ Standards Committee, I’m sure, worked
very hard to make sure it makes sense, but it doesn’t make sense to
me.

[00:08:43] And so seeing the code examples allows me to quickly
discount 90% of them as not useful to me. I mean, to understand, you
know, what these new features are. I’m not a big fan of jumping in
and using all of the new features, but it’s definitely helpful to
kind of see them written down.

[00:08:58] So I really appreciated this article. we’ll have a link in
the show notes because it’s, on someone’s get hub page and it’s
really long. So I’m not gonna say it out loud, but if you use C++,
you’re interested in seeing what new features are in 20, check out
the show notes and definitely visit this link.

[00:09:13] Jason Gauci: What was
the version that added lambdas? Thst was the last big feature.

[00:09:17] Patrick Wheeler: 13 or
11? I think 11.

[00:09:20] Jason Gauci: Oh, it’s
that old? Yeah. Lambdas, and then, well, actually one that came out,
it might be in 20, or it might be in 20 where it’s not experimental
anymore is the file system library. That was another really important
one

[00:09:30] Patrick Wheeler: Oh,
17. Yeah. Okay.

[00:09:32] Jason Gauci: Those are
the two I remember where I was like, Oh, we totally needed this for
such a long time.

[00:09:37] Cool. All right. My news is: Play Co-op Diablo II in the
browser.

[00:09:42] So there’s always this interesting, kind of, march
towards, you know, doing just more and more exotic things in the
browser. So this is, you know, I know a while back, Maim was ported
to the browser. This is using like m script and these other
technologies like web assembly. And so yeah, one of the challenges
though, for something like, like this is, is, you know, the network
stack, right? Because you can’t really run a server, for example, in
the browser and have other peop–or maybe you, maybe you can. Let me
think about that.

[00:10:15] Actually, you kind of can, using a WebRTC and stuff like
that. But it’s definitely not a one-to-one mapping between, you know,
these low level kind of Windows sockets, or Unix sockets and what you
can do in the browser. And so, you know, that’s kind of been an area
where you haven’t seen a lot of development, but here it’s, they
actually have Diablo II.

[00:10:37] I know, assuming they don’t have the source code or
anything like that. So this is just using the Diblo II binary. We are
able to actually play in the browser and it’s able to talk to a
Diablo II Battle.net server. And you can actually play with other
people co-op online, without even having to really do it, download
anything, you just visit the website

[00:10:57] Which is pretty wild. I mean, I’ll have to do a bit of
research into how this actually works. My guess is maybe they hacked
the, like, DOSBox emulator. And so, and so they, they somehow wrote a
translation layer, where when you try to create a Windows socket, it
uses WebRTC, which is just pretty amazing, or WebSockets or something
like that.

[00:11:19] Pretty amazing. Check it out. It’s clouddiablo.com. We’ll
have a link in the show notes, but I thought that was pretty wild
achievement there.

[00:11:26] Patrick Wheeler: That
is really awesome. And now I’m going to get depressing. I remember
playing Diablo Iwhen it came out, and I was not a super young person
when it did, and playing it really enjoying it, playing a lot. Do you
know when Diablo II came out?

[00:11:38] Jason Gauci: You know,
I’ve never, I played Diablo I, just the demo. I only played the demo
though. So I’ve never been into the whole Diablo thing, but yeah, go
ahead and tell us, when did it come out?

[00:11:48] Patrick Wheeler: 2000.
So it’s 21 years old, or it will be 21 years old in June.

[00:11:53] Jason Gauci: Oh man,
that’s nuts. Yeah, that’s right. I remember right around, that would
be senior year of high school for me.

[00:11:59] Patrick Wheeler: Oh,
now you just, Oh no, no, now people are doing the math in their head,
man. (laugh)

[00:12:03] Jason Gauci: Yeah. I’m
going to hit the big four, oh, in I guess 10 months or something.

[00:12:07] Patrick Wheeler: Ohhh,
okay.

[00:12:09] Jason Gauci: Yep.
Diablo II had, if I remember correctly, Diablo II is the one that
actually had like an overland map, right? ‘Cause the one I played was
just, you’re in a town and there was a dungeon, and that was it. But
then II added, like, a whole world, right?

[00:12:22] Patrick Wheeler: Yeah,
like you walk around, and then you go into dungeons. Yes.

[00:12:25] Jason Gauci: Yeah.

[00:12:25] Patrick Wheeler: Yeah.
The Diablo games are actually pretty fun. I enjoy them. I don’t know.
For me, there’s like a whole layer of complexity, but I never really
got into it, as like, you’re number crunching, and min-maxing your
character buildouts? So I never got competitive like that. I always
just sort of like wandered around and like, you know, smashed a lot
of stuff, and I always thought that was fun.

[00:12:45] But I never got super, super into it, but a lot of people
really did. And for me, games that allow both kinds of players are
super awesome. There’s a lot of recent games that people get really
into that I don’t feel support casual or semi-casual play.

[00:12:58] Jason Gauci: Yeah.
Yeah. Totally agree with that. You know, the, the games I’ve been
getting into lately have been racing games, and I’ve been considering
buying a steering wheel. The challenge is, if you buy a steering
wheel, you also, they all come with the pedals, and I feel like you
can’t really use the pedal as if you’re standing up and I have a
standing desk.

[00:13:18] So it’s like, it’s like, (laugh)
it’s starting to spiral out of control. It’s like, okay, first
I need to buy a bucket seat and then I need to buy, you know..

[00:13:24] Patrick Wheeler: With
the hydraulics to make it react to you.

[00:13:27] Jason Gauci: Yeah.
(laugh) Yeah. So I’m not sure what to do, have a little bit of
analysis paralysis. But I think maybe, I did see there’s some
steering wheels that have like, basically like a grip. So like the
harder you grip, the faster the car goes. And so I might try and pick
one of those up.

[00:13:42] Patrick Wheeler: Interesting.
I think you need to like, come up with a custom, like DDR-style map
for…

[00:13:47] Jason Gauci: Oh, that
would be awesome. (laugh)

[00:13:49] Oh man. I’ve been playing this game Wreckfest. I just want
to give a shout out to Wreckfest. They’re not a sponsor or anything,
but Bugbear is a company, and they made this game, Wreckfest.

[00:13:59] It’s really interesting. So you, you have 24 racers, 20
are what you’d expect. They’re just in cars, they’re racing around
the track, et cetera. The other four are in giant heavy school buses.

[00:14:12] And their job is to go around the track backwards and
wreck like, the people in the top three positions.
(laugh) So like, you’ll be driving, it could be an oval or
whatever, but like you’ll be driving around the track, and all of a
sudden, like a school bus will just, just crush you. So it’s kind of
like the blue turtle in Mario Kart.

[00:14:33] Patrick Wheeler: Are
they, but are they computer controlled? Or like, it’s like in, like
some players are playing one and some players the other?

[00:14:38] Jason Gauci: Yeah. No,
they’re all real people. So it’s kinda like if the blue shell is
sentient, (laugh) it’s just crush…

[00:14:44] Patrick Wheeler: Oh,
oh all man.

[00:14:45] Jason Gauci: It’s
really, really fun. I highly recommend Wreckfest. I actually, you
know, I never buy cosmetic stuff like just buy a new skin for your
car or whatever. I never really done that, but I actually went and
bought a bunch of cosmetic stuff in Wreckfest. I don’t even use it. I
just, I’ve put so many hours into that game that I was like, these
guys deserve more than the 20 bucks or whatever it was.

[00:15:06] Patrick Wheeler: Interesting.
I’ll have to check that out.

[00:15:07] So your news article was a Diablo II in the browser,
talking about browser games, but on a complete different level. This
was something I came across that I thought was like, super cool. And
one of those things, which we have said probably 500 times in the
podcast, which is like, I wish this was around when I was learning to
program. And that’s Kaboom.

[00:15:28] And, the URL is replit.com/kaboom. And so I guess Replit
is, they have a free tier, but it’s also like a paid service, like
IDE in the cloud, where you can run code and do development and
stuff. I can’t vouch for it. I haven’t tried that.

[00:15:44] But this Kaboom thing is they were able to host a Java
script game development library. If you do nothing else, search it
and watch their opening video, which is like hand-drawn, MS Paint,
pixel art, like, with just a hilarious, like, run up. And the audio
is made by them. The drawing is made by them.

[00:16:04] And it’s not meant to be the next blockbuster AAA title
game engine. It’s literally like, Oh, I want to drop a character
here. And then it’s like, you know, draw the sprites for your
characters animation sequence, and you draw them in a little pixel
editor. And then, you know, draw the wall tile, and you draw the wall
tile and it manages the assets and your video game thing. And it’s
kind of not really like a, definitely not a no code way of building
it, but just sort of this like right at your fingertips, like
everything’s sort of kept right there.

[00:16:34] And I imagine for complex games, it gets out of hand
really fast. But for just making super simple, like a side scrolling
engine and, doing ASCII descriptions of your text level, like, you
know, equal signs for the walls and plus signs for where you want
item pickups, and doing those kinds of things in a very simple
environment, but something that really gets you into programming and
allows you to make these.

[00:16:57] I think they’re pretty, it looked pretty cool. Retro,
nostalgic looking games. And I thought this was a really cool thing.
Kaboom digest. I actually wonder if this was a way to try it easily
in a, in the browser, which is how I was able to play around with it
for a few minutes, but they may have a, I’m not a big JavaScript
person, so I don’t know how people pick up JavaScript libraries
normally, but it looks like they also have, you don’t need to go only
on Replit. They have a way to do it. If you want to just host it
yourself and try it. They have it available as well at kaboomjs.com.

[00:17:27] Jason Gauci: That’s
awesome. I’ll have to check that out. And so, the idea is you, you
draw the map in ASCII, but then you, for each, like ASCII character,
you have a picture attached to it or something.

[00:17:38] Patrick Wheeler: Yeah,
you just like has like the assets right there. And you say like,
invent a new asset, and then it just gives you a little pixel editor
and asks you to draw it.

[00:17:45] Jason Gauci: Oh, very
cool. Yeah. I’ll have to check this out. All right.

[00:17:48] My topic is on remote work. And so, so Patrick and I are
both, well, everyone is working remote, but you know, at some point,
offices are going to reopen and, I don’t know, Patrick, if you’ve
what your plan is, or if you know, or anything like that.

[00:18:05] But, but in my case, I’m permanently remote. So this is,
this is the real deal forever and ever.

[00:18:10] Patrick Wheeler: Oh,
ever and ever, that’s a big commitment.
(laugh)

[00:18:13] Jason Gauci: I mean,
as far for who knows, but yeah, I mean, I’m basically a remote
employee permanently. And so, and so, so you know, this whole like,
“Oh, maybe remote wasn’t a good idea” article is definitely
scary to somebody who’s really, there’s no going back. But yeah, I
think it’s an, it’s a really interesting debate. And I, you know,
honestly, I don’t have a lot of answers or insights really. I mean, I
think that so far being a remote has been really great. I think we
might have talked about this.

[00:18:40] I think we talked about this when we, we talked with
Kevin. But, but yeah, we both have loved being remote, but then the
question is, you know, when people come back into the office, what’s
the hybrid solution?

[00:18:51] That’s really what it is, where it’s, it’s, maybe there’s
four people who are all sitting next to each other, and another four
people who are spread out around the globe. How do you sort of, you
know, keep the sort of social environment kind of like healthy and
fair and all of that in, in that kind of world? And I think that’s,
that’s what this article is kind of positing. And I don’t know if
there really any answers yet.

[00:19:12] Patrick Wheeler: Yeah,
I think that’s going to be a hard question for people. Like what does
the future look? And then the debate we were even having at work the
other day is, is this a kind of one and done thing? And then like, it
just slowly over time returns back to normal, or like, is this going
to keep creeping up?

[00:19:25] There will be at least, for some while, people’s concern
that it may come back, or that, you know, the next version, you know,
the… in Silicon Valley, I guess the whole open office, densely
packed people real estate at a super high premium is kind of very
incompatible with the view that there might be reasons to not be
super close to people.

[00:19:45] And so it’s very interesting to see how we’ll run a sort
of real life experiment in the various ways of solving the problem
over the next couple of years.

[00:19:53] Jason Gauci: Yeah,
that’s another really good point. I mean, a lot of companies in the
Valley will have to double their office space, right. Because of the
density.

[00:20:01] Do you think they’re going to have laws around the
density, or do you think it will be mostly like self-governance?

[00:20:06] Patrick Wheeler: I
mean, laws is one of those things that’s tough, right? Like at best
case, I think laws are sort of slower, slower-moving, slower to catch
up, which makes sense. I actually think that, you know, too fast
lawmaking, you might end up in a problem.

[00:20:19] And so I think, what will happen is, the employees in some
ways will sort of express what they’re comfortable or not comfortable
doing. And if, especially if there’s a, like, I think Silicon Valley
had gotten quite homogenous in the approach, and I think this will
shake it up and allow for some experimentation to take place, which I
think traditionally has been where you see a lot of innovation
happen, right?

[00:20:41] And so I think we might be entering an era where you see
some interesting innovation around this and a lot of people trying
things, and the ones that will succeed will attract people to them,
away from the ones that are on the other end of the spectrum.

[00:20:53] Jason Gauci: Yeah.
That makes sense. I mean, one thing that, I don’t know if I mentioned
this on the show, but one thing I’ve been thinking a lot about is
like, is it possible? And like, sort of safe from a privacy
standpoint to like decouple your kind of work team and your social
team, like, you know, look at WeWork for example, right?

[00:21:13] So WeWork as this company or this, this idea where, you
know, they have a big office and you might go and rent one cubicle in
this giant office, and the person next to you, and a person on the
other side of you worked for totally different companies. You’re just
sharing this, like, you know, a physical space, right?

[00:21:31] And so, you know, if you wanted to go start, like, a ping
pong club, you could do it with the people around you, even though,
you know, the 12 of you work for 12 different companies. And so I
wonder if that is going to, if that idea is really going to fly,
where, you know, it’s, it’s like you kind of have a group of people
and you have a whole relationship with them, but then you also have
like your work team, which is spread out through, throughout the
whole globe. And it’s sort of like two different social networks,
right?

[00:22:00] Patrick Wheeler: Not
to get back into the avoiding drama at work you’re talking about
before. But I think it’s been interesting. This thing you’re saying a
little bit reminds me of something I thought some about, which is,
the different way different people treat their sort of a work team.
And some people, the team becomes like an extension of their family,
which makes sense. I mean, you spend, used to spend, you know, 40
hours a week minimum with those people basically.

[00:22:24] And in some ways that’s more awake time than, you know,
you often spend with other members of your family. And so for some
people, they sort of re really bring those people in and treat them
as family.

[00:22:34] Other people want to maintain a separation, right, between
their, their sort of work teammates, and they can be sort of work
friends with them, but there’s a difference between a friend and a
work friend, and they maintain that pretty solidly.

[00:22:45] And then of course people all along the spectrum. And then
of course, people who have no interest in sort of the social aspects
at work. And I’ve always thought it’s interesting that how a person
approaches that problem impacts how the work evolves. Right? So how
the manager treats the team and their personal life separation
probably colors how they view people on their teams, treatment of
work stuff.

[00:23:09] That is, that was a really vague way of saying it, but
like, if you come to work and your managers are very like super
everyone’s my friend, let’s hang out all the time, and you want to
maintain a stronger separation, that creates a bit of awkwardness.
And so, I actually think this thing you’re saying Jason, where like
they get separated, for ill or good, I’m not sure, but at least it
sort of evens out that some.

[00:23:29] If people realize I’m not going to be at work all the
time, or we enter a hybrid, or a mostly remote work and people really
understand that separation, and it’s sort of somewhat forced in and
you can still have fun with the people at work, but it’s a little bit
different. And I think that will even out the people who maybe felt
trepidation or awkwardness with those relationships before.

[00:23:47] Jason Gauci: Yeah.
That’s a really good call-out. And so then, as a thought experiment,
what happens to the other people? Like the people who, you know,
always want to go golfing with the boss or something, but now the
boss is, you know, a thousand miles away. Maybe, maybe people of that
personality will, we’ll just won’t be remote. Right? They won’t be a
remote employees.

[00:24:07] Patrick Wheeler: Yeah.
I don’t know. Maybe they seek out a team or environment where for
some reason or another, they sort of need everyone together or that’s
a culture thing or whatever.

[00:24:16] Jason Gauci: Yeah.
Yeah. It’s interesting. Yeah. That’s pretty wild. Yeah. I think, I’m
really curious to see what’s going to happen.

[00:24:22] I wonder to what degree, like technology can help with
something like this? Yeah. I mean, it’s hard to know because we’re
not really in that situation yet. Like it’s hard to kind of project
what that’s going to look like and what the social feelings are going
to be. You know?

[00:24:37] Patrick Wheeler: I
mean, I, for one welcome our, telepresence humanoid robot deskmates.
(laugh)

[00:24:46] Jason Gauci: Oh yeah.
All right. Cool. So on that note, Book of the Show.

[00:24:51] My book of the show is Debt: The First 5000 Years. I have
to confess, I haven’t read this yet. I just got it. But, you know,
I’m always looking out for books on finance, finance, or just, the
history of finance is just super interesting to me.

[00:25:05] And somebody at work, you know, sent me a ping, maybe a
couple of weeks ago. And he said, Hey, you know, I read this book,
you know, I think it’s right up your alley. And so, I’m just catching
up with, you know, I finished Antifragile and so I’m just kind of
getting caught up with my current books and jumping into this new
book. So, yeah, I have to admit I haven’t read it yet, but it does
seem really cool.

[00:25:27] I think that, if you think about it, like the whole thing
around debt and credit and lending is, is really, really fascinating.
Like it, you know, in my case, like I, I try not to have any debt if
possible. I mean, there’s things that, you know, there’s large
purchases that you have to pay over time, like you buy a house, or
something like that. But, you know, on the credit card and some of
these things, you know, I try not to have debt, but at the same time
I don’t preload anything either.

[00:25:54] So the credit card is super, super useful because I can
make a payment on something that has zero balance using something
that has zero balance and then, and then pay it later. And so, you
know, I think, and then, you know, of course, like if, if for
whatever reason I didn’t pay it, well, now it’s like there’s debt. So
it’s like, you can’t really have a credit card without debt. So it’s
kind of unavoidable. If you want to have that level of convenience.

[00:26:19] And you can kind of ask yourself, I mean, there’s a lot of
really fundamental questions about debt that I have. And I think this
book will clear a lot of it up, like one of them is, and Patrick,
tell me your take on this, but like, something is backed by the
government. I still don’t quite understand why they could charge
interest. You know what I mean? Like, like how can you charge
interest on a loan, if you’re not actually taking any risk? Because,
in effect the person who’s paying the loan as like a, you know, a
citizen of a country, that’s also only backing the loan is actually
taking the risk and giving you interest.

[00:26:52] So, that’s just one thing, but there’s, you know, debt is
really fascinating to me. And I think this book is really going to
explain a lot of stuff.

[00:26:59] Patrick Wheeler: Yeah.
I think I’m going to opt out of getting into an in-depth
fractional-reserve banking discussion and interest just now, like in
here, this is going to, avoiding drama.

[00:27:08] Jason Gauci: I don’t
know. So, okay. A couple of things. So one thing is, is, yeah, I look
at it just, just super objective. I don’t have like a horse in the
race per se. I just try to learn as much as possible. But the other
thing is, is what is fractional reserve? Cause you mentioned that a
while back and I always meant to ask you off the air. I never got a
chance. So what is fractional-reserve banking? What does that mean?

[00:27:29] Patrick Wheeler: So,
so you, you kind of were bringing it up by saying the, you were
admitting the realization that the bank borrows money from the
government at some level before lending out money. So the naive way
of viewing a bank and I, I might mess it. I’m going to try.

[00:27:47] The naive way is that the bank has somebody come in and
say, I’m going to give you a hundred dollars and then they say, cool,
we’re going to pay you a 0.001% interest on your a hundred dollars.
Then they go find a mortgage customer who says, Oh, I want to use a
hundred dollars to buy a house and you go, okay, cool. I’m going to
loan out my hundred dollars to you that I got from this other person.
And then you can use it to pay the person you’re buying the house
from.

[00:28:17] And then what I now have is someone who believes the
hundred dollars is at the bank. But in actuality, it hasn’t, it’s
been given to someone to buy a house and that person’s making
payments. And then the hope is that like when the, when the payments
come in, that the person doesn’t come and ask for their money back
before it’s there.

[00:28:36] So you can’t loan out money that you don’t have, unless
you have a way of borrowing it. So the question is how much of the
amount of money that you have loaned out your obligations, your
liabilities for a bank, do you need to have in reserve? And that
fraction that you need, is, is, is sort of governed by the government
and saying like, you have to have this.

[00:28:59] Now, the difference is that you can also, sort of borrow
money, but what happens with the whole fractional-reserve banking, if
banks borrow money from each other or from the government, and keep a
small amount in a reserve, and say, someone takes out a loan at Bank
A, and then deposits it in Bank B, and starts earning interest, and
then takes it out again and puts it somewhere else.

[00:29:21] Now, if you ask each of the banks, each of the banks will
say like, Oh, I have a a hundred dollars deposited times three banks,
but what if you’ve just gone in a circle, you actually only have a
half a hundred dollars.

[00:29:32] Jason Gauci: Oh.

[00:29:33] Patrick Wheeler: And
so fractional-reserve banking is pointing out this thing that you can
sort of artificially create money by not requiring that banks fully
back the deposits.

[00:29:44] Jason Gauci: Oh, I get
it. Oh, it’s interesting.

[00:29:46] Patrick Wheeler: And
so the government can sort of, by controlling what percentage of
liabilities are needed to being held and by the interest rate at
which they’re willing to loan you money and do these audits, they can
sort of have a, I guess, not a direct, but an influence over sort of
how much total money is circulating out in the environment.

[00:30:07] So, by lowering the interest rates from the government,
they can encourage the banks to lend out money because they can lower
their rates, which are like a delta on top of the, the government’s
rate. And so they can encourage people to take loans by making
interest rates lower and lower, and thereby cause sort of inflation,
right? By the money, there’s more money, a parent money in the
system. I probably didn’t get that a hundred percent. Right. But
that’s the gist.

[00:30:34] Jason Gauci: Yeah.
Yeah. No, totally makes sense. I mean basically if the government has
a really high interest rate, then you could invest in that. I don’t
know what you would call that investing in, I don’t know, the
government or something. Yeah.

[00:30:45] Patrick Wheeler: You
buy treasuries

[00:30:46] Jason Gauci: Yeah,
yeah, yeah. Right. No, I know like the vehicle, but it’s like, what
are the treasuries actually doing? Are they just like building
bridges or something?

[00:30:52] Patrick Wheeler: They’re
a bond backed by the government. So it’s a government taking out a
loan from you.

[00:30:56] Jason Gauci: Oh, I got
it. So, so it’s basically just going to whatever the government pays
for. It could be anything.

[00:31:01] Patrick Wheeler: Yes.

[00:31:02] Jason Gauci: And so,
and so, yeah. And so the higher the interest rates go, the more
people who are going to do that. And that means there’s less people
who want to invest in other, like, private things. And so I think
right now, the interest rates are very low. And so people are always
looking for things to invest in, so real estate and other things.

[00:31:22] Patrick Wheeler: Yep.
Okay. Yeah. That’s going to get, if we keep going down this path,
another few steps, it’s going to get dramatic and political.

[00:31:28] Jason Gauci: Okay. All
right. Let’s not do that.

[00:31:30] Patrick Wheeler: The
other thing I was going to bring up here, that’s interesting. So
I’ve, I’ve read the first sort of 50 pages of this book. Well, listen
to the equivalent of about the first 50 pages of this book, because I
have this book on Audible. But I haven’t made it through, it’s
definitely not the most exciting read at least in the first few
pages, but I’m also intrigued by this concept. And it also plays into
the thing that we’ve been a common theme here on the, on the show,
which is the cryptocurrency and blockchain. And this concept of DeFi
this distributed finance, and how would you allow on the blockchain,
people to borrow money, by depositing one asset and taking money out
of, you know, some sort of contract and going and using that money
and then paying back that debt over time. And how would you handle
that if it needed to be done all via algorithm and not by human
intervention or judgment?

[00:32:19] Jason Gauci: Wow,
that’s actually in the book?

[00:32:20] Patrick Wheeler: No,
no, no, I don’t think so. I’m just saying this conversation we’re
having about fractional-reserve banking, inflationary versus
deflationary politics, and the common theme of cryptocurrency leads
to a very interesting topic, if anyone wants to go sort of look in
that and hasn’t yet about this distributed finance. I don’t think
it’s in the book.

[00:32:36] Jason Gauci: I haven’t
seen anything about crypto derivatives. I mean, I’m sure it exists,
but I haven’t, it’s definitely not a popular thing.

[00:32:43] Patrick Wheeler: Oh,
the book was written in 2011, so yeah. There’s zero chance it’s in
there.

[00:32:47] Jason Gauci: Oh yeah.
Oh, there you go. I think crypto derivatives would be a pretty
interesting thing, but, but then the thing is like, how do you do
that?

[00:32:54] Because derivatives have to trade faster, presumably, have
to trade at higher cadence than the original thing and, and crypto
is, is so slow. I mean, you have to somehow make the algorithm, the
whole process would be much faster.

[00:33:08] Patrick Wheeler: My
book of this show is not well-suited to, audio edition in the format
I’m going to recommend it, but that is a Harry Potter and the
Sorcerer’s Stone, the Illustrated Edition.

[00:33:18] So we’ve talked about before, both Jason and I have
children, and my children are now old enough to sort of start
introducing them to Harry Potter, and they’re getting interested in
reading. And so I figured to, to read to them, I would read Harry
Potter and the Sorcerer’s stone. And then I decided to go in and pick
up the Illustrated Edition just to kind of keep it more, engaging for
them, unless at least until we saw how it went.

[00:33:43] And Oh man, I read Harry Potter, I don’t even know how
long ago. I’m not… long ago. I went back like when they were first
coming out.

[00:33:51] Jason Gauci: It also,
it came out around the time Diablo came out.

[00:33:54] Patrick Wheeler: Oh,
did it?

[00:33:55] Jason Gauci: I think
so. Yeah. Correct me if I’m wrong, I’ll look it up.

[00:33:58] Patrick Wheeler: But
going back through it again, and reading it and then like, also
seeing the pictures, they’re just so well done in this book. These
books aren’t cheap. Like I’ve gotten used to like really cheap books.
These books are just very well done though. The drawings, even the
pages that don’t have sort of full color illustrations have like
texture to the page, and it’s not just a black and white.

[00:34:16] Small nit is like, there are some places where the text is
a little hard to read against the background. But, just like thematic
and sort of, you know, nice to look at, and just a really nice book
to read, and sort of go page by page through. I’ve really enjoyed
that, so…

[00:34:32] Jason Gauci: Harry
Potter and the Sorcerer’s Stone came out in 1997.

[00:34:37] Patrick Wheeler: We’re
going to keep going. (laugh) So if
you’ve not, if you’re interested in Harry Potter or if you have
children or you’ve never read it before, or if you just really like
pictures, you know, I don’t think it’s probably everyone who’s into
this, probably seen these before, but anyway, my recommendation is
Harry Potter and the Sorcerer’s Stone.

[00:34:54] Jason Gauci: So it’s
not a small book. Right? So how does that work? Is there a picture
every few pages or is there one every page or what’s the…

[00:35:01] Patrick Wheeler: So
the, I mean, the book is both large in sort of height and width, and
then also it’s sort of normally deep, so it’s a little bigger than a
normal book that you would not want to carry this book to the beach
and read it on the beach or whatever. Like it’s a bigger book. And
then, you know, also– And there’s, you know, so every page has like
some sort of like thematic texture drawing to it if I recall, but
then yeah, sort of every other page or every third page pair will
have like some picture related to the things sort of like off to the
side or in the corner.

[00:35:30] Jason Gauci: So is it
abridged or is it like actually the whole book?

[00:35:33] Patrick Wheeler: No,
it’s the full thing.

[00:35:35] Jason Gauci: Wow.
That’s cool. Yeah. I find out about so many good products on this
show. (laugh)

[00:35:41] Patrick Wheeler: This
is like, what is it, Oprah? Who does the Christmas best things or
things you have to buy–

[00:35:46] Jason Gauci: Yeah,
that’s right. Yeah. Very cool. I’ll definitely be picking that up.

[00:35:49] Patrick Wheeler: So,
so I alluded to it, and, and, I actually do have Harry Potter and the
Sorcerer’s Stone on Audible, but it’s obviously not illustrated, but
it is well narrated and it’s a very pleasant way to consume the book.

[00:36:02] But if you’ve never tried Audible before and you can check
it out and help sponsor the show by going to
audibletrial.com/ProgrammingThrowdown, and there they’ll do a free
one month trial of Audible, which, you can pick sort of any book
that’s in Audible, download it and you get to keep that book.

[00:36:18] And then you can cancel the trial if you decide you don’t
want to keep it, or keep going and get a book a month. I’ve done that
for awhile, you also get access to their sales and I’ve built up,
quite a collection. But, you know, honestly, I really enjoyed, I
don’t have a bookshelf at home with dozens and dozens and dozens of
physical books. It’s just not a thing I do anymore, but I do enjoy
actually scrolling through my Audible list of books and picking out
my recommendations for the show.

[00:36:43] Jason Gauci: Yeah,
very cool. And for folks who either already have an Audible account,
or aren’t interested in that, they can support us on Patreon. So
Patreon and Audible are how we can keep this show going and how we
were able to get more content.

[00:36:57] I mean, this episode exists because of your support. And
so we really appreciate that. You can reach us at
patreon.com/ProgrammingThrowdown.

[00:37:05] Patrick Wheeler: It’s
time for Tools of this Show.

[00:37:09] Jason Gauci: My Tool
of the Show is Vagrant! Have you ever used Vagrant, Patrick, or are
you new to Vagrant?

[00:37:15] Patrick Wheeler: I
feel like I know the word, but I’m not thinking of what it is right
now.

[00:37:20] Jason Gauci: Okay. So
Vagrant is, it’s similar to Docker. We talked about Docker on an
earlier episode, but it is for virtual machines. So Vagrant is a way
to spin up a virtual machine, and to initialize it with a set of,
sort of, you know, parameters and, and, and a set of scripts.

[00:37:41] So for example, I use Vagrant a lot when I’m testing new
versions of Eternal Terminal. So before I release a new version,
which is kind of a big process, you know, it goes to all the Debian
and Fedora, like official, you know, like the package systems, and it
runs through a million different tests. People like download it. I
want to make sure that at least like all the tests run and build and
everything.

[00:38:05] And so I have a set of Vagrant scripts. And so the way
this works is similar to Docker, you know, you write a Vagrant file,
and in that file, you say what the virtual machine should be like.
It, should it be Ubuntu, should it be Windows, should it be, you
know, Fedora or openSUSE or whichever one, and then you specify the
things, like how many CPU’s should the virtual machine have, et
cetera, and you can specify scripts.

[00:38:34] So in my case, the script goes to GitHub, grabs the latest
Eternal Terminal release and, builds it, and it runs all the tests,
and then, and then kind of exits, right?

[00:38:47] And so all of that, you know is nice because, for example,
there was a, a GitHub issue the other day where someone said, Oh, the
open… and I don’t know how you pronounce this.

[00:38:56] It’s open S U S E. Open… susie? But that, that variant
of Linux, you know, wasn’t compiling and, I just pointed them to, to
Vagrant. I said, Hey, you know, install Vagrant, run Vagrant up in
this directory and you’ll see it totally builds the works. And it
turns out that the person who actually maintains the openSUSE
package, who, you know, isn’t, isn’t me, that person, there was some
error there. I don’t actually know the details, but I was able to
just, you know, get anybody to, to just go on there and, and run and
build, which is super convenient.

[00:39:29] Now you might say to yourself, well, if you have Docker,
why do you need this? Right. And the answer is, you know, there is
that layer in between Docker and the virtual machine, right? There is
the whole, the Docker, like Docker daemon, right? And so Docker tries
to, you know, be really good about, you know, giving you a lot of
freedom and flexibility, but when you’re doing things like building
packages or especially you’re doing things which involve low-level
networking, you know, that can give you results that aren’t really
natural, and sometimes you really need like a bare bones virtual
machine.

[00:40:04] And so Vagrant is kind of like the Docker for that, for
that kind of stuff. So, if you need that, check it out, it’s super,
super useful. Especially if you’re deploying software on a bunch of
different OSS, you know, I literally have just one script that I run
and I can test every OS. And when the script finishes, I know like
every OS works. So it was just a one-liner and so I’m a big fan of
Vagrant.

[00:40:28] Patrick Wheeler: Nice.
What is the difference between something like Vagrant and VirtualBox?

[00:40:33] Jason Gauci: Oh yeah.
So under the hood Vagrant uses VirtualBox. I think Vagrant is just
like a scripting library for VirtualBox. That’s a good way of looking
at it.

[00:40:42] Patrick Wheeler: I
see. I see. Okay.

[00:40:43] Jason Gauci: The other
thing it does is, it maps like a folder on your computer to a virtual
machine. So if I do,like Vagrant up in a certain folder or with a
certain Vagrant file, it, it has a UID for that file. And if the
machine already exists in VirtualBox, then it won’t have to like
totally destroy it and bring it back up and stuff like that.

[00:41:04] Patrick Wheeler: Nice.
My Tool of the Show, I actually had one, and then I switched it to a
collection, because indecisiveness. I was playing a new game by Zach
Gage Games, and that was Good Sudoku. So I, I played Sudoku for
awhile. I go off and on in books, but I never really got into it just
didn’t feel the same.

[00:41:22] Like I couldn’t use my pencil to kind of make notes on
iPhone or you know, on an Android phone. I use an iPhone, but I I’m
sure it works the same. And so, you know, I kind of never really did
it, got into it on, on mobile, but then I tried this Good Sudoku, and
I didn’t realize it was by the Zach Gage Games, but I tried it, and
they just liked the kind of UI they built up around playing Sudoku.

[00:41:44] It’s not exactly the same as how I would do it on pencil,
on paper. It plays a little faster. It does actually what I want. And
I just really thought it was very well done. And then I realized,
like I was searching this, you know, Zach Gage Games, this is a maker
of, of Good Sudoku. And then I’m like, Oh, I actually like a lot of
these games.

[00:42:01] So they’re the people that made Ridiculous Fishing, Really
Bad Chess. So Ridiculous Fishing is like, you’re a dude on a fishing
boat. And then you use like the motion sensor in your phone to drop a
line down into the depths of the ocean, catch a fish and then sort of
reel it back in. It’s ridiculous.

[00:42:18] Jason Gauci: Did you
reach the end of that game?

[00:42:19] Patrick Wheeler: No.
Uh-uh.

[00:42:20] Jason Gauci: Oh, okay.

[00:42:21] Patrick Wheeler: Do I
need to?

[00:42:22] Jason Gauci: I’ll
spoil the ending after you explain it. (laugh)

[00:42:25] Patrick Wheeler: No,
don’t spoil it! No, you can tell me offline.

[00:42:28] Jason Gauci: Okay. All
right. I won’t spoil it, I won’t spoil it.

[00:42:30] Patrick Wheeler: No, I
need like a week, give me a week, I’ll go do it. Now I know there’s
an ending.

[00:42:33] Jason Gauci: It’s
actually pretty good.

[00:42:35] Patrick Wheeler: Oh,
okay. So Really Bad Chess is, you know, I know Jason is like, a
master chess person, so we’re not going to,
(laugh) we’re going to ignore him for a second. But, I’m
really bad at chess actually. So in this game, they don’t even try to
make an attempt that decides white and black or even, it is
effectively, randomly placed chess pieces on your side of the board.
So you might have like five Queens and the other person has all
pawns. Or something you’d only get one King or something, you know,
and then you try to play.

[00:43:03] So the expectation is just to like, be a little more goofy
and a little free and make it not have to be, this super serious,
chess game.

[00:43:12] Anyways. So if you’ve never checked out any of these games
,Good Sudok, Really Bad Chess, Ridiculous Fishing, some are available
on iOS, some on the play store. Go check them out. They’re actually
this, I didn’t know anything. I need to go learn more about this
company, but it turns out right before the show, just doing research.
It turns out I’m actually really into these games and I’m going to
follow them and watch for new ones that come out.

[00:43:31] Jason Gauci: Oh, very
cool. Yeah the Really Bad Chess sounds awesome. Do you play online
with people or is it against the computer?

[00:43:37] Patrick Wheeler: You
know, I, I played it once, and I don’t do online playing, so I
actually don’t know if you, I’m sure, there’s probably like this
based on it. There’s a way to do it. Multiplayer. Is just for me. I
never, it always feels embarrassing even though it’s…
(laugh)

[00:43:51] Like, I don’t want to lose to real people. I don’t care
about losing to the computer, but… (laugh)

[00:43:56] Jason Gauci: You know,
when we, when we first moved, my family first moved to, to the West
coast, I actually set up a meetup group called, Sports for People who
are Really Bad at Sports. And, it was great because, you know, you
kind of self-select for people who aren’t going to take it real
seriously.

[00:44:14] And it actually, I was worried that like, somebody would
see that title and be really good at ping pong and then just kind of
embarrass us and like, I have to deal with it. But no, actually like
everyone who showed up genuinely was really bad at sports and we all
had a really fun time.

[00:44:28] Patrick Wheeler: Oh,
that’s cool. It does not look like Really Bad Chess has multiplayer.
It looks like it’s only single player.

[00:44:33] Jason Gauci: Oh, okay.
That, that, it kind of makes sense. ‘Cause I think that could be more
frustrating.

[00:44:37] Patrick Wheeler: I
think it’s supposed to be more like, it’s kinda like puzzley, right?
Like they sort of know like here’s the best you could do with this
crappy set of pieces. And if you play multiplayer and one person got
like, decidedly, a good advantage against you and they win. So what?

[00:44:52] Jason Gauci: Yeah,
exactly. Like, like, like teasing apart, the computer’s kind of
strategy is part of the fun, and part of it’s kind of gone if you go
online.

[00:45:03] AD: Hey everybody, we
have new sponsor, and that is ConfigCat. And I’m going to tell you a
little bit about, what ConfigCat is. It is a feature flag service.
You can easily use flags in your code with ConfigCat libraries for
Python, nine other platforms, toggle your feature flags visually on
the visual dashboard.

[00:45:22] Hide or expose features in your application without
redeploying your code. Set targeting rules to allow you to control
who has access to those new features. ConfigCat allows you to get the
features out faster, test in production, and do easy rollbacks. With
ConfigCat, simple API and clear documentation, you’ll have initial
proof of concept up and running in just minutes.

[00:45:43] Train new team members and minutes easily, so you don’t
have to pay extra for growing teams. With a simple UI, the whole team
can use it effectively. Whether you’re an individual or a team, you
can try it out with the Forever Free plan.

[00:45:57] Release your features faster and with less risk with
ConfigCat, check them out today at configcat.com.

[00:46:03] Jason Gauci: Cool.
Yeah. For people that don’t know what feature flags are, it’s, you
imagine you have something out in production and you want to change
some kind of behavior. So you might say, you know, now use this other
database, but then you do that and then it’s broken and now you’ve
broken it for everybody. And that’s, that’s kind of a nightmare.

[00:46:20] So, so what you want to do instead is you want to try
something out on like a few people and then slowly kind of add more
and more and more people. And one way to do that is to have a feature
flag, have a flag says if you know, this is part of my test group of
people, then switch to the new database.

[00:46:38] Otherwise use the old database. And, and slowly like that,
if becomes true for more and more people. And so ConfigCat is a
service that, that kind of handles a lot of that for you. So they can
like handle deciding, like who gets the feature and who doesn’t. And
then you can go in their UI and change all of that and slowly, slowly
get it to a hundred percent and they take a lot of that burden off
you. So check them out. They’re great.

[00:47:03] All right. So we can jump into trees.

[00:47:08] Patrick Wheeler: Why
are trees important?

[00:47:09] Jason Gauci: Why are
trees afforded? So, so, just a quick story, you know, a lot of search
indexes and e-commerce sites, so if you go to Amazon or you go to
Google or you go to any of these websites, you know, they need to
serve content to you really quickly.

[00:47:27] And the way that you can do that, especially in a place
where you’re adding a lot of content, very dynamic, you, you’re going
to be using hash tables, which we’ll talk about another time, and
trees, and, and especially trees.

[00:47:42] And so for this, you could say money grows on trees. If
you work for Amazon, money literally grows on the trees. And so
that’s, that’s why it’s so important. If you’re going to be doing
queries, insertions, you’re going to be doing partitioning of data,
you are going to use trees a lot, and they are extremely important.
They’re going to come up all the time.

[00:48:03] Patrick Wheeler: I
think it’s also one of the like, first things people learn in
computer science because I feel, and you get this like, if you look
on the internet, you get the, Y if I interview at X tech company, do
they ask me about binary trees or about linklists or,…and, you
know, I, I somewhat, I hear, and there’s there. I don’t want to get
into the drama or the politics (laugh) or
whatever around all of that. But what I’ll say is that, you know,
being able to think through trees and their trade-offs and, so it’s
just like, it’s part of, you know, kind of like the problem solving,
even if like Jason and I were talking before.

[00:48:38] So some of these trees we’re gonna talk about, I
definitely use and use them all the time, but the sort of basic
vanilla binary tree that, that most people are introduced to first,
like actually have trouble coming up with exactly how I would use
that one. and it’s not clear if it has a ton of use. But as a
learning tool or reasoning tool or thinking tool, or like a, a
minimum backstop, like I got to at least do better than this, it
actually serves a really good purpose.

[00:49:03] Jason Gauci: Yeah.
Yeah, totally. I think that, I mean, the thing that trees teach
people at a fundamental level is the idea of, sort of divide and
conquer and also like Agglometric thinking. So we’ll jump into like
how trees are built and hopefully we can use that to kind of motivate
why they’re so important to know about.

[00:49:22] So, you know, imagine if you have, you know, some set of
numbers and you need to put this set of numbers into a tree, and
we’ll get into why you’d want to do that late,. But imagine, you
know, your task is sort of doing this, you have this binary tree and
you want to, you know, you want to fill it full of these numbers and
you want the tree to be pretty balanced and stuff like that.

[00:49:43] So there’s two kinds of ways to do this. One way is, sort
of divide and conquer. So you can imagine saying, well, what I’ll do
is I’ll, I’ll start with all my numbers. So I kind of in a way have
like a single node that just has my entire set of numbers in it. And
then what I’ll do is I’ll just split the set into two halves.

[00:50:06] One half is the, the bottom 50% of numbers, right? The
bottom half of the numbers, if I was to order them, like maybe you’ll
sort them and then cut that sorted list in half. And then say, you
know, I’ll send that half down the left side of the tree, and I’ll
send, the bigger half down the right side of the tree, and maybe I’ll
take the node that’s right in the, on the median and make that my
node.

[00:50:28] So, you know, imagine like you have 20 as the root of the
tree and everything to the right of 20 is bigger, everything left of
20 smaller. And so now you can repeat that process again on the left
and right side, right. You have a less than half the size of your
original set, but that process stays the same.

[00:50:47] And if you were to just go to that, that left branch, that
has those, that half of numbers, and just look at it in isolation,
you actually have the same problem as you did in the very beginning,
just with fewer numbers. And so trees are a really good way to
explain recursion and to, you know, deal with all of that phenomena.
And to cover a lot of other phenomenon in computer science. Right?

[00:51:13] So, so trees are kind of, you could even think of like the
call graph when you’re doing recursion and we’re doing computation
as, as sort of this, this tree, like the history of all the functions
you’ve called. So, so yeah, trees are kind of ubiquitous. And so, you
know, it kind of like introduces you to a lot of other areas of
computer science.

[00:51:34] Now, another way to build trees is what we call
Agglometric or bottom up. Well, to do the same thing, like an
Agglometric way, you might say, I’m gonna take all my numbers, I’m
going to sort them. And then I’m going to group them into, you know,
16 different groups.

[00:51:56] And then for each of those groups, I’m going to, you know,
pick a number out and put it and call it like the leaf node of that
group. And then I’m going to, you know, do that and then kind of go
bottom up and then start kind of merging some of these mini trees
together.

[00:52:14] So now it’s like, I have a bunch of these smaller trees,
I’m going to kind of merge them, merge them, merge them. And when I’m
done, I have one big tree. And that’s kind of the Agglometric way of
assembling these trees.

[00:52:26] And so, and so, you know, that is also, you know, if you
look at, for example, merge sort or something like that, you actually
see kind of both of these things, right? So in merge sort, you start
by kind of splitting a list into halves and then halving it, halving
it, halving it, just these successive halfing algorithm. And then at
some point you reach a point where it’s just all just lists of size
one, and then you start kind of merging, merging, merging. And so,
you know, merge sort actually has both, you know, a divide and
conquer approach and then an Agglometric approach to kind of bring
everything back together. But when it comes back together, it comes
back sorted.

[00:53:03] Patrick Wheeler: Oh. I
didn’t know that had to name.

[00:53:06] Jason Gauci: Yeah.
Yeah. So, so it’s, so then, then you have this question of like, how
do you go about doing that divide, right? Like if it’s, if it’s
small, you know, like for example, you know, you have 100 items and
you’re just putting it into some binary tree. Well, then you can, you
can kind of what we talked about, sort it and then split it, and
you’ll have this like perfectly balanced tree that look really nice.

[00:53:28] But in practice you’re dealing, with like massive, massive
datasets. And so you can’t, you can’t really, you can’t really do
that. It doesn’t really make sense. Or you might even have things
that are multi kind of modal or multi-objective. So there might be
different ways to split data. You know, maybe you have a list of
people, and those people have, you know, ages, they have genders,
they have other characteristics, and you want to have some binary
tree that says, you know, that ultimately like results in different
equally sized buckets of people.

[00:54:07] So your binary tree might say something like, well, let’s
first look at everyone who’s over 18 is on one side and everyone
who’s under 18 is on the other side. And it’s everyone who has been
to my website in the past a day is on one side. And so in this kind
of decision tree,at the end of all of these decisions, at the end of
all, asking all of these questions, you now have this, you know, end
state, which hopefully doesn’t have too many people in it.

[00:54:35] And so, you know, you know, whether you’re doing a
decision tree like that, or you’re doing just a, you know, a sorted
tree, but have a really large dataset, you can’t try every possible
way to, to, to construct that tree. It’s just too expensive. It’s I
think it’s like NP-hard. Like coming up with the best possible
decision tree.

[00:54:57] And so that’s where you end up with trying to do some of
these approximations. So you might try, you know, at every node in
the tree, you might try 50 or a hundred different ways of splitting
it. Now there might be thousands, but you’re just going to try 50.
And because you’re trying 50, you might not, you know, get the best
way of splitting, but hopefully the best one out of 50 is decent.

[00:55:22] And then when you go to all these children that you’ve
created from the split, you’re going to do this again. And you’re
going to pick 50 at random, a different 50 ways of splitting. And if
there was a really good way of splitting that you missed, hopefully
like you catch it, you know, at the next level.

[00:55:40] And so this is how a lot of these decision trees or binary
trees over really large data sets are kind of assembled. There have
been a lot of other like search-based approaches, but, It’s actually
really hard to beat the, just a greedy way of doing it.

[00:55:57] Patrick Wheeler: So,
so to back it off of, back to the, kind of like the basic stuff, I
think Jason was already jumping ahead that we, or at least me. I tend
to think of trees as storing, like strictly orderable things in the
data, like numbers, or strings. And, one of the other things to point
out is that you may not be exposed to all of them all up front. So if
you are experiencing them over time, having these things that Jason’s
talking about and figure out how you split, how do you insert new
data or remove data or modify data plays a part too, and what tree
and algorithm you might select.

[00:56:39] The other thing that I, that has come into play for me is
that, I often think about first about trees as being sort of, no
individual allocated nodes with pointers between them.
(cough) I work in C++ (laugh)
That’s how I think, but they don’t have to be actually. In fact, in
some cases, in many cases, it may be better served to have an array
of all of your data and then order the stuff in the array where like
the zero item in the array is your root node.

[00:57:08] And then the, you know, first and second, are the children
nodes. And then you can do sort of what level are you on and where in
the level are you, and then you can do the visitation of the nodes
and the search by simply going to the right place in the array. and
that has efficiencies for keeping your data, you know, more close to
each other, more local, and that’s more cash efficient, and we’re
going to get into some other things where that plays a role as well.

[00:57:33] But I think it starts off when you’re first introduced
trees is, in my experience, like this very rigid. They’re always
binary trees. In fact, they’re normally always binary search trees,
and you always divide them up in a, in a certain way, but actually
the sort of body of all kinds of trees that are using computer
sciences is quite big and they often share interesting similarities,
but also very interesting differences.

[00:57:56] Jason Gauci: Yeah.
Yeah, totally makes sense. Yeah. A lot of people have invented,
different trees for different specific use cases and, and a lot of it
comes down to, you know, being able to split the data in a way that
more often than not splits evenly. Right. Because what you don’t want
is, and you’ll hear this like trees that are balanced or unbalanced.
Right?

[00:58:18] So imagine if, imagine if you have a binary search tree
over, over numbers, but it’s completely unbalanced. So the root node
has, let’s say, let’s say you have the numbers 1 to 100, the root
node has a one. It has just one child to the right. That’s a two. And
you just do this all the way to a hundred. Now you actually have a
linked list, right. You used the tree idea, but you ended up with a
linked list and, you have all the performance problems of a list,
right? If you were expecting something to be really, really fast,
you’re, you’re not going to get that ex, you’re not going to meet
that expectation. Right?

[00:58:57] And so you want these trees to be balanced, but you also,
as we talked about before, like you can’t spend a lot of time
building it because you’re dealing with such large volume, right? So
you can’t look at all of the items, do many, many passes. And so a
lot of these structures that we’ll get into have really nice kind of
like a really nice propensity to just naturally break data down into
ways that are even, you know, for a specific type of problem.

[00:59:26] Patrick Wheeler: I
mean, yeah. I think the algorithms for keeping them balanced are
probably slightly difficult to communicate over audio.

[00:59:33] Jason Gauci: Yup.

[00:59:34] Patrick Wheeler: But
what are some of those, what are some of those ? If people want to
look them up?

[00:59:39] Jason Gauci: Yeah,
it’s really good point. So, so in addition to like choosing the right
tree, and people are inventing new types of trees all the time, you
know, no matter what you do, especially if data is coming in and
going out, you know, the trees will become unbalanced, either when
you’re building it, or when you’re modifying it.

[00:59:56] And so there is, you know, there are special kind of trees
called AVL trees and red–black trees. And, and for things like
b-trees, there are ways to rebalance them. But as Patrick said, I
mean, you know, definitely, take a look at, if you search for any of
these trees on Wikipedia or other places, you’ll see really nice kind
of visuals of how they’re rebalanced.

[01:00:19] But, I remember from, from, you know, undergrad,
rebalancing trees is one of the hardest things that I have to
implement. And I just remember having so many issues because you have
to kind of project yourself into different parts of the tree and
like, think, okay, at this point of the tree, you know, I, I am like,
like I’m at this node in the tree, but because I’m in the middle of
this rebalancing, I know this, this and this.

[01:00:44] And so I have to do that. And, so that, that’s what gets
really, really difficult. So yeah, I think in general, you know, if
you’re going to use trees, try to find a library on the web, you
know, definitely take the time to understand how they work, but if
you’re going to put something into production, there’s, there should
be a really good implementation of a variety of different trees that
are, that’s publicly available.

[01:01:10] Looking at binary trees specifically. So, you know, a
binary tree is one where you only have two children. And so you might
see yourself, well, like why would I, why would I, you know, have
that restriction, right? Like, what’s, what’s, why would I limit
myself, right? But there is one thing that binary trees can do
really, really well. And that is like upper or lower bound search.

[01:01:35] So for example, imagine if you have a set of numbers and,
and you’re asking the question, you know, what is the biggest number
in my set, you know, less than 30, right? That question requires you
to, to do kind of an in order search.

[01:01:54] So you have to kind of look for 30, if you find 30. Well,
I guess I said less then, so, so yeah, even if you find 30, you still
have to kind of go backwards. And find the biggest number less than
30. So you have to kind of March in sorted order through that
structure, right? And a binary tree is really nice because, since
there’s only two children, you know, that the child to the left is
smaller, and assuming there’s no duplicates in the tree, the child to
the left is smaller and the child to the right is bigger.

[01:02:26] And that’s always true. And, and you can also do this
trick where if you take any point in the tree, if you take the child
to the left and then keep going to the right as many times as you
can, you’re going to get the number that is smaller than the one
you’re currently at, but bigger than, than, all the other ones. And
so that’s, that’s a unique feature to binary trees. And I think that
is one of the biggest reasons.

[01:02:52] Another reason why people use binary trees is in machine
learning. We talked about there’s, in machine learning, you’re
typically not using a tree to store a lot of numbers or something
like that, you know, you’re using a tree to the structure of the tree
to store decisions.

[01:03:10] And so at the end of you got the, the, the leaf or the end
of a binary tree, if you’ve searched through it, you have kind of a
list of constraints and you can use that as a, as a way to learn
things. Right?

[01:03:24] So in that case, it’s actually pretty difficult to split
it multiple ways, depending on what kind of decision you’re making.
So it’s, it’s decisions like, you know, this number should be greater
than X or, you know, this binary number should be set to true. Like
these are all kind of binary kind of decisions like thresholds and
binary operators. There might be times where you have some kind of
categorical thing. So, you know, day of the week, it could be seven
choices and you should have seven children.

[01:03:59] But, but even in those cases, it’s, it’s kind of hard to
calculate whether that is a good decision to put in your tree or not.
Versus if you have a binary. Yes. No decision. It’s pretty easy to
calculate. Yes. I want to take that decision and put it here in the
tree. And so for that reason, a lot of machine learning will use,
will use binary trees, when they’re making these decision trees.

[01:04:25] You’ll also hear in machine learning the term random
forest. At the time, I thought random forest was this really
complicated thing because I had heard, you know, where it was used.
And so I thought, Oh, like one of these days I really want to learn
random forest. Random forest is very simple. All it is is if you have
a big data set and you’re planning on building a decision tree,
instead, what you can do is you can split that data set, you know,
end different ways and build end different decision trees.

[01:04:56] And, you know, because of that randomness, I talked
earlier about where, where you’re randomly trying different splits,
even if the, the, the, the distributions of the data or the type of
the data is the same in each of those groups, you’re still gonna end
up with different decision trees. and then once you have all of these
decision trees, when you want to make a decision in the future, you
can actually ask all of them, and then you can either do some kind of
voting, or you can take the average, or what have you.

[01:05:28] Patrick Wheeler: So
Jason already spoiled our next topic, but if binary trees have, two
children at each node, if you generalize that and instead allow sort
of more children, there are a variety of things you can come up with,
but one of them is a b-tree. And so b-trees say that each node can,
and there’s some variance here, but basically each node can contain
multiple values.

[01:05:55] And then the chil– however many values it has, you have
that many children plus one. So let’s say you had two values stored
there instead of just one, then things before the lowest value, you
keep them sorted, and then the thing below the lowest value you would
have reference to the next child there. Between the two values, you
would have a child, and to the right, the bigger, the biggest larger
than the tube, the bigger you would have a child to your right.

[01:06:26] So in that case, you had two values in the node and three
children, and you could see this expanding to, various sizes four or
five, six, seven, and there’s a lot of varieties and some techniques
for how you keep them balanced. But the interesting thing about here
is when you visit a node, rather than simply making a single
decision, do I use this value? Do I go to left or right. You sort of
can consult multiple values. And then also you make, by doing that,
you make your tree shallower. So you don’t have as, as many levels of
children as you would, if you used a binary tree, because you’re
putting more, more data, in the note.

[01:07:04] Now, the other thing that I already hinted at as well,
where this starts to matter, and this is one of those things where,
when I’m doing interviews with people and we do some sort of, you
know, questions, we’re working through a problem and then I’ll often
ask them, you know, Oh, what is, what is sort of the run time? And
they start scratching their head, and this is different for everyone,
but always express to them, look, I’m actually not that interested in
sort of the academic, asymptotic runtime, because it turns out like,
in my life, most of the time you’re dominated by other factors. So
I’m looking for you to just express to me like, which parts of this
algorithm, about how many times would this take, where are your
bottlenecks?

[01:07:43] And so one of the things that b-trees really excel at is,
if you imagine, which was true, maybe a lot more true five, 10 years
ago than is true today. But if you go back 10 years, RAM was really
small, like CPU caches weren’t really like they are today. And things
were stored on sectors on hard drives.

[01:08:04] And if you were going to go access something on the hard
drive, the hard drive is going to spin up, move the little arm out to
the right spot on the moving piece of metal with magnetised bits on
it, and read in a whole bunch of data in a sector, and bring that
into memory. And that was an extremely slow thing.

[01:08:21] And so if you were going to do an on disc search for data,
you wanted to bring in, sort of as much in one go as you can. And if
you imagine a binary tree where at each block, you have one and then
the next block is, who knows where, each time you go to the next
node, you are spending a lot of time waiting to get the next node
into memory or getting into the CPU.

[01:08:42] And these b-trees became very valuable by instead saying
we’re going to store a whole bunch of data in the sector. Then we’re
going to analyze all that data, increase our chances at any given
node of finding ours or at least, cutting down the search set
dramatically. So the number of different nodes we have to visit is as
small as possible.

[01:09:00] So for things like file system and file system metadata,
for things like databases and indexes and databases, like, these
b-trees get used heavily because, you can tune the number of children
and you can do sort of more work per node visitation. And if node
visitation is a dominating factor, then you would want to choose a
b-tree. And then there’s techniques for making sure that you keep all
the data at a certain spot that you know how to keep it ordered and
organized and well balanced.

[01:09:30] And so there’s a whole body of work around b-trees, but
it’s enormously valuable in this sort of broadening the scope out
from just, you know, one value and two children to allowing a more
general form and realizing that that may play better with an actual,
computer architecture.

[01:09:49] Jason Gauci: Yeah.
Really well said. Yeah, that really covers it. And so, yeah, as
Patrick said to me, pretty much any database that you look at is
going to have a b-tree implementation in it. I mean, all of them,
they all use b-trees in some way, shape or form.

[01:10:04] So now we’ll move on to spatial trees. And as we, you
know, motivated earlier, you know, spatial trees often aren’t
functionally, you know, that different or, or, you know, in terms of
their idea, but they’re just taking advantage of some domain
knowledge, in this case, the fact that, that, that, it’s operating
over some, you know, some, some space or some field, right?

[01:10:28] And so the simplest one of these that I know of is a k-d
tree. I don’t actually know where the name k-d came from, but, but
effectively it’s a binary tree where every split is done on a single
axis. And so if you imagine, like, so like picture in your mind, you
know, a graph like just with an X and a Y, right, graphing some
function. If you just have a line, right. You can describe a line
just by looking at one of the two letters.

[01:11:01] So if you look at just a horizontal or a vertical line,
you can do that just by looking at one of the two variables. Right?
So if I have a line like Y equals X or a parabola, like Y equals X
squared, I need to be thinking about Y and X at the same time.,
bacause they kind of relate to each other. So Y equals X squared, you
know, as, as X is increasing, Y is really increasing. And so you have
this like parabola, right? This line that like just shoots upwards.
Right?

[01:11:28] But if I have a, just a vertical line, that’s just like X
equals two and I want all the Y, right? That’s a vertical line. Or if
I have a horizontal line that would be, you know, like Y equals four.
And so, and I just want all the exes that are all points on that
line. So vertical and horizontal lines are kind of the easiest to
express. Right? And so k-d tree uses this to, you know, to, to have a
very simple division of, of, of the space.

[01:11:58]So what a k-d tree will do when you’re building one is,
you’ll look over all the points and let’s just keep it at two
dimensions, just to keep it simple. So you look over at all these
points and then you’ll calculate the spread. In other words, you
calculate the difference between the smallest point and the biggest
point on that dimension.

[01:12:18] So if you were imagining like, you know, a bunch of
points, but, but they’re all kind of around the same height, but
there are some that are really far to the left. Some that are really
far to the right. You have this really large, horizontal spread, but
not a very large vertical spread. And so whichever dimension has the
largest spread that one’s going to be chosen as your split dimension.

[01:12:43] So you’re going to choose that dimension and then you’re
going to split it right in the middle. Now, when I say in the middle,
I don’t mean like in the middle of the extremes, but you’re going to
split it such that half the points go on the left and half the points
go on the right. And so while you’re computing the spread and you can
also be, you know, finding that middle, finding that median point.

[01:13:06] So if you imagine the root node, the root node is going to
look at your entire dataset, find which dimension has the largest
spread. And then slice that dimension, such that half the points go
to one child and half the points go to the other child. And then all
that root, no needs to keep track of is which dimension it was split
on.

[01:13:25] And where in that dimension, the split was. Now, then each
of the children will do the same thing. And so you’ll keep doing this
until you get to a node where there aren’t that many children. At
that point, you’ll say, well, there’s no point in me splitting again.
I’m just going to have like, just a list of points at this, at that
level.

[01:13:47] And so k-d trees are super, super important, because,
there’s a really, really cool trick you could do at them. In machine
learning. You have this challenge, right, where let’s say you’re
Amazon, right. And someone types in batteries. And so you need to
return back a list of items that you think that person would be
interested in. Right?

[01:14:14] But the problem is Amazon has like a billion items, right.
Or maybe even if you take it even workstream, let’s say someone just
goes to amazon.com. They don’t even put a search. So you need to show
them some items you think they would like. And there’s just so many
items, probably a billion skews in Amazon’s catalog. Right?

[01:14:34] So you can do this trick. Let’s say you had a vector, a
vector, just like a set of numbers. Let’s say you had a set of
numbers to describe a person. Right. And so, you know, that, that
might be sort of like some way of capturing, like their history and
the things you think they like, and you were to sort of what’s called
embed that, or create just like a single point for that person.

[01:15:00] And then you also do this for all your different products.
So for all your different products, you have kind of like, a point or
a vector, a list of numbers, or a point in a space somewhere
describing that product. So now what you need to do something called
nearest neighbors. So you need to say like, what are the nearest
products, the nearest points, product points to this person point
that I’ve created.

[01:15:27] And it turns out if you use a k-d tree, you can do that
very, very quickly. Things like nearest neighbor search can happen
extremely quickly in k-d tree, because for example, look at that
first split, that first split might be like so far away from where
the person point is, that you could say anything on the other side of
that split.

[01:15:48] There’s no way that any of those points are my nearest
neighbor. And so that’s, right away, that’s half the data you don’t
have to look at. Right. And so you can kind of take that, that sort
of intuition. Now basically. Yeah, you can kind of follow the k-d
tree down to the final part of the k-d tree that has your, your
person in it, your person pointed it and look at the products there.

[01:16:15] And then maybe look at like some of the products, you
know, higher up in the tree, but you definitely don’t have to look at
the entire tree. You can ignore 99% of the tree. And so this is how
Amazon does, at the end of the day, this is how they can show you
stuff so quickly, even though they have so many items.

[01:16:33] And so there’s a lot of work that goes into like, the
embeddings and how you create the tree and everything, but
extensively, you know, they just have a giant k-d tree that they’ve
implemented. And when you come to Amazon, they find the nearest
things to you in that tree. That’s how it works.

[01:16:50] Patrick Wheeler: So to
highlight one difference and then talk about one final thing. I think
when Jason is describing like this nearest neighbor search. On
multidimensions, which, which we sort of called these spatial trees,
because that tends to be one way of thinking about it. But when we’re
talking up front about b-trees and binary trees, we’re talking about
a single number line, basically, where all of your elements live on.

[01:17:13] And when we talk about multi-dimensional, it’s having at
least two or more dimensions, and the problem there becomes there,
isn’t direct way of viewing. Like I’m just going to go in dimension
one and then dimension two, like that turns out to be really
inefficient. So both k-d, Jason and things I’m going to talk about,
and some others, try to divvy up the space in a way that moves back
and forth between the dimensions. And as Jason was saying, using the
spread, you might divide on the X line, the X line, but then you’ll
go by the Y line. Right. And you’re sort of intermixing the two
dimensions. and trying to sort of interleave so that you can get to
your answer a little bit faster and when you’re traversing, the other
interesting thing is you may end up having to go through multiple
branches in order to find the nearest neighbor.

[01:18:01] So once you go down one branch, you know how far away the
split was from you, and if your answer ends up being further away
than that split was you actually have to go visit the stuff on the
other side of that split. And that’s true as well for a variety of
these facial trees and doing that nearest neighbor search.

[01:18:21] And the other thing that both his k-d tree explanation and
my, oh man, I say to this out of order, think I’m about to talk about
also support, which is very similar, is for clearing ranges. Or if
you think about in 2d, it would be rectangles or boxes. Right? So if
you drew a rectangle and said, I want everything inside of this
rectangle, they need to be efficient at doing that.

[01:18:42] And it’s a little hard to describe over audio, but I mean,
both of them are well-suited to being able to do that. So both Jason
talked about splitting the data on, you know, one of the axes at each
level. So instead of looking at your data and sort of splitting based
on what the data says, instead, if you come up with predefined splits
based on your space, you come up with a different, spacial tree
called a quadtree for two dimensions or an octree for three
dimensions. I don’t know what it would be for four dimensions. I’ve
never heard of someone doing that, but maybe you could.

[01:19:16] And so if you imagine in two dimensions having, let’s just
say a square, right. And you divide that square once in the middle,
up and down and once in the middle left and right. then you end up
with four quadrants of that space.

[01:19:30] And now you see why it’s called a quadtree. So the root
node would be the base sort of square. Then the first set of
children, there would be four and one would be the upper left. One
would be the upper, right. I’m going to be the bottom left and one
would be the bottom. Right. And what that does is that sort of
dimension mixing, I was talking about you get it, right?

[01:19:49] So as you go, you know, child zero one, two, three, you’re
actually traversing, both dimensions sort of intermixed, but the
quadtree, what it does is say, if I have a set of points scattered
around in my square, I’m going to keep subdividing my space until I
get, you could say just one theme in each square. So the disadvantage
is that as you’re cutting down and down and down, if you have two
points really close to each other, you might need a lot of splits
before you get to the split that separates the two.

[01:20:24] And so you could have a lot of depth, right. But, in
traversing, it actually ends up working really similar to how the k-d
tree does. The advantage of a quadtree is that I can figure out where
in the tree it goes from the start. So if I know the level, I want to
go to, like, let’s say level five split, I can compute in closed
form, which traversal of the tree I would need to place that element
in the tree there.

[01:20:50] The other nice thing is that if you have dynamic data
where your data is moving around, so imagine like someone shoots a
laser beam out of your spaceship and your game, and you have your
world game split up in a quadtree or fits in three dimensions, an
octree, which is the same thing. But with eight children, if you
imagine that laser bolt moving through space and needing to do these
nearest neighbor queries, which is what you would want to do, if you
wanted to see, like, if I hit something in my current box, then this
traversal you can figure out and sort of a more direct, closed form
on computation and do the management and a sort of much cheaper way,
rather than reshuffling and potentially needing to re split, like you
would need to, for k-d to your other kinds of spacial trees that
would be used.

[01:21:31] So they’re similar in actually the way you use it. And
once you start looking at algorithms between them, like once you
figured it out once. It kind of ends up being pretty similar for all
of them and how to do these range searches and nearest neighbos
searches.

[01:21:44] I find that these quadtrees and octrees are used a lot in
games for, for dynamic data and the quadtree, k-d tree, there’s also
one more this worth mentioning, I guess, which is like an r-tree,
which is taking a group of data and drawing a rectangle around it,
and then building a tree of rectangles over multiple rectangles. And
I won’t go into it more than that.

[01:22:06] And you’ll see that also used a lot in sort of mapping
data, geographical or geographic information systems, GIS systems.
We’ll use these a lot in databases and stuff. Also, I think k-d trees
can also be used in video games. I’ve seen them used for like
splitting up a level and understanding, which polygons you want to
draw or not because the level itself, like the environment tends to
be static.

[01:22:31] And so you can, a priori before you’re like, when you’re
making your level, you can do the split, and have it stored so that
when you’re trying to figure out which polygons to render you just
traverse this pre-made tree rather than having to build it at
runtime.

[01:22:44] Jason Gauci: Yeah,
totally. Yeah. I think you really hit the nail on the head. I think
k-d trees and r-trees, the structure of the tree is dependent on the
data. So, you know, as Patrick said, if, if your data is like really
wide, you might have a lot of, a lot of vertical splits before you
start seeing some horizontal splits. If data is really narrow, it’s
going to be the opposite.

[01:23:08] And yeah. In the case of the r-tree, you know, if there’s
a part of the space, that’s very dense. I mean, imagine building an
r-tree of the US, right? You’re going to have like a ton of
rectangles around like New York City, San Francisco, Los Angeles.
Right? ‘Cause I mean, I imagine you’re building an r-tree on like
over like businesses or addresses in the US, right?

[01:23:28] There’s just a lot more addresses in a tiny space in New
York city. Right? And so the structure of the tree will, you know,
even all the way up to the decisions made at the very top, will be
influenced heavily by the distribution of the data, versus like in
the case of a quadtree, you know, now there might be nodes that exist
or don’t exist because of the data.

[01:23:54] But the structure, like the way that the splits are done
is totally immutable and it has nothing to do with, with the data,
right? And so, you know, that’s sort of like a double-edged sword,
right on one hand, If you’re not splitting in a, in a informed way,
then you’re not going to be very efficient. And so if you’re doing
something just once, like if you’re creating a tree off some data
that’s not changing and then using it a lot of times, like that’s
what Amazon is doing.

[01:24:23] Amazon will create this giant tree. and that might take a
lot of time, but then they’re going to swap it out with the old tree,
and then they’re going to use that new tree, you know, billions and
billions of times. And so they know they can afford to have this sort
of frozen set, right? And so, and so they’ll use like a k-d tree or
an r-tree or something like that.

[01:24:48] But for games, you know, the content is moving all the
time. I mean, there’s, there’s there’s, as Patrick said, like if you
have, people walking around on a map, shooting laser beams and all
these things, you know, then, then you would, you can’t have the
structure of the tree dependent on these things that are constantly
moving around. And so for games, they’ll use these octrees and
quadtrees.

[01:25:09] And my guess is, and I think you alluded to this, Patrick,
is your games will probably need both, because the level doesn’t
move, unless you’re playing like Minecraft or something, but the
level doesn’t, geometry doesn’t change. And so that would be much
better served by something like a k-d tree or r-tree.

[01:25:26] And, and there’s actually more like exotic trees for
certain domains. There’s like a BSP tree. There’s a, you know,
vantage point trees. And so they’ll use something like that. And, but
then for actually storing all of the dynamic content, they’ll use
something like an octree.

[01:25:44] Patrick Wheeler: That
was a lot of fun. Yeah, totally.

[01:25:46] Jason Gauci: I totally
got the geek out on trees. If we missed any trees, let us know. Or if
we…

[01:25:52] Pine trees. Oak trees.

[01:25:53] Yeah, that’s right. Birch. Yeah. Minecraft taught me a lot
about trees. Been playing, playing that a lot with the kids. And I
learned that Birch is a thing. So, I don’t quite know, like the
order, the big O-notation of a Birch. I’ll have to figure that one
out.

[01:26:11] But thank you so much, everyone for, all of your support.
let us know what you think about the duo episodes. We were bringing
them back. We still have, a lot of really awesome interviews lined
up. So, you know, looking forward to that. But we’ll be kind of
intermixing some of these, you know, duo episodes in there.

[01:26:32] And definitely give us some feedback. We really appreciate
all the feedback you have been giving and just keep it up. Let us
know what you think about the show. We definitely look at all of
them. we’ve gotten a lot of our show ideas from listeners. This was
one that we, we really wanted to do ourselves, but, but we’ve taken a
lot of really great show topics from listeners and that’s all because
of you and, you know, continuing support and feedback.

[01:26:54] So we appreciate it.

[01:26:56] Patrick Wheeler: Yeah.
Thanks everyone.

[01:26:57] Jason Gauci: See you
later.

[01:26:59] Music by Eric Barndollar

[01:27:02] Programming Throwdown is distributed under Creative
Commons, Attribution ShareAlike 2.0 license. You’re free to share,
copy, distribute, transmit the work, to remix, and adapt the work,
but you must provide attribution to Patrick and I, and sharealike in
kind.