149: Algorithms
00:00:00
◼
►
Welcome to Under the Radar, a show about independent iOS app development.
00:00:03
◼
►
I'm Mark O'Arment.
00:00:04
◼
►
And I'm David Smith.
00:00:06
◼
►
Under the Radar is never longer than 30 minutes, so let's get started.
00:00:10
◼
►
So this past weekend I had the privilege of attending a friend of mine's PhD dissertation
00:00:18
◼
►
And congratulations, Carl, he passed.
00:00:21
◼
►
And this was computer science, right?
00:00:23
◼
►
This is computer science, and specifically he was – he did his PhD in machine learning.
00:00:29
◼
►
So his dissertation was something that I understood maybe half of, but the half that I didn't
00:00:35
◼
►
understand prompted a few interesting conversations that I had with him over the weekend, just
00:00:40
◼
►
about the way in which we used computers to solve problems, and the ways that his dissertation
00:00:47
◼
►
and what he was doing is solving these really complicated, deep problems in this really
00:00:54
◼
►
interesting way that uses lots of computation and all these types of things.
00:00:58
◼
►
And for certain kinds of problems, that's what you have to do.
00:01:01
◼
►
But more fundamentally, I think what he and I were talking a lot about was just about
00:01:06
◼
►
sort of algorithms.
00:01:07
◼
►
And it's interesting, I find, that I think any introduction to computer science, like
00:01:12
◼
►
one of the first courses you have to take is almost certainly going to be some variant
00:01:17
◼
►
on introduction to algorithms.
00:01:22
◼
►
There's going to be this sort of this fundamental thing, and they walk you through the set of
00:01:26
◼
►
problems usually, like the classic ones are things like sorting.
00:01:30
◼
►
You have a list of numbers and you need to put them in order.
00:01:33
◼
►
How do you do that?
00:01:34
◼
►
And you kind of start with the maybe what you would call "naive" solutions, things
00:01:38
◼
►
like bubble sort and insertion sort, and then you start to get into the way more complicated
00:01:43
◼
►
ones where you start using quicksort or merge sort and radix sorting and all these really
00:01:49
◼
►
kind of clever, esoteric things.
00:01:53
◼
►
And usually I think that's presented as the algorithm that you start with, those naive
00:01:59
◼
►
solutions are like the, you know, it's like, well, they're the ones for the babies that
00:02:04
◼
►
when you're starting out, you use those solutions.
00:02:07
◼
►
And then you graduate to these really cool special ones.
00:02:10
◼
►
And in practice, obviously, like for sorting things, the reality is you don't actually
00:02:14
◼
►
ever use these algorithms ever again, because almost any collection framework just has a
00:02:20
◼
►
sort option on it and it'll sort it for you.
00:02:23
◼
►
But I think most of what they're trying to teach you when you're doing that is that,
00:02:28
◼
►
you know, understand that to solve an algorithm, which is probably worth defining, is an algorithm
00:02:34
◼
►
is probably best thought of just as a series of steps to solve a problem.
00:02:39
◼
►
And you define ahead of time what those steps are.
00:02:42
◼
►
So it's sort of like if you have a recipe for baking a cake, you know, like the goal
00:02:46
◼
►
is to bake a cake, and you have a series of steps that you have to do.
00:02:50
◼
►
And when you define a computer algorithm, that's really all you're doing is saying,
00:02:54
◼
►
you know, here's this series of steps of operations that you have to do in order to complete and
00:03:00
◼
►
do that task.
00:03:02
◼
►
I think it differs also from like, you know, like you can have like a lot of computer code
00:03:07
◼
►
that just does things that's basically like moving data around or doing simple things.
00:03:11
◼
►
I think when like, you know, if you're like, you know, populating a web page with like
00:03:15
◼
►
the results of the rows in a database, like I don't think most of the things you're
00:03:19
◼
►
going to do there are going to be what most people consider an algorithm.
00:03:23
◼
►
Whereas an algorithm, like I consider it, and the way I think most people consider it
00:03:25
◼
►
is like a method of solving some kind of interesting or non-trivial computing task of, you know,
00:03:33
◼
►
not just like moving data from one place to another or not just like basic math, like,
00:03:37
◼
►
you know, addition of things, but some kind of like slightly more complicated problem,
00:03:43
◼
►
like you know, as you said, sorting a list or something more complicated like detecting
00:03:46
◼
►
what's in an image, you know, like there's all sorts of things you can do.
00:03:49
◼
►
But like I think it has to kind of be like above just, you know, moving things from place
00:03:53
◼
►
A to place B to display them.
00:03:56
◼
►
It's something, some kind of method to solve a more complicated problem or accomplish a
00:04:00
◼
►
more complicated task.
00:04:01
◼
►
Yeah, I think that's fair.
00:04:02
◼
►
And I think, and certainly like when you're early, like the complexity of the problem
00:04:07
◼
►
that you're solving is, you know, will typically increase the more advanced of a developer
00:04:14
◼
►
You know, I think there are some problems that were hard for me to solve when I was
00:04:17
◼
►
young and like the, you know, like I try to take some algorithms for granted now that
00:04:21
◼
►
I just, I know how to do something and so I do it.
00:04:25
◼
►
But it's, yeah, there's usually some sense of solving a novel or interesting problem,
00:04:30
◼
►
you know, by creating a series of steps that you apply to do that.
00:04:36
◼
►
And sometimes algorithms are very prescriptive, you know, like that it's this very straightforward,
00:04:40
◼
►
like do step A, step B, step C.
00:04:43
◼
►
And sometimes they can become very non prescriptive.
00:04:45
◼
►
And this is where you start to get into things like machine learning and neural networks
00:04:49
◼
►
and probabilistic things or heuristics where it's much more squishy.
00:04:55
◼
►
And like, you don't really know what's going on.
00:04:56
◼
►
Like a lot of what it seems like machine learning is, is like you are trying to train this magic
00:05:01
◼
►
black box to do magic black box stuff.
00:05:04
◼
►
But it's not an algorithm in the sense that you have like a specific set of things that
00:05:09
◼
►
that box is doing.
00:05:11
◼
►
It's much more you have to train and orient that box to do some task.
00:05:16
◼
►
But it's, you know, it's still used to solve a problem in that way.
00:05:22
◼
►
So in practice, though, I think what is interesting is what I find in the day to day work of being
00:05:27
◼
►
a software engineer is that usually most of the work I do, probably 80% of the work I
00:05:33
◼
►
do is the kind of work you were describing that isn't an algorithm that is these this
00:05:36
◼
►
kind of basic moving data around just sort of just shuffling things back and forth.
00:05:43
◼
►
It's making a web request, getting back a JSON object, parsing it, displaying that in
00:05:48
◼
►
a table view like that's like 50% of iOS is used for that.
00:05:53
◼
►
And then maybe another 30% is the like saving stuff to disk or doing kind of basic operations
00:05:58
◼
►
with that data.
00:05:59
◼
►
But what is interesting, I find is that we still, though, have situations where we have
00:06:06
◼
►
to invent a new algorithm to do something and maybe invent is the wrong word.
00:06:11
◼
►
Like sometimes these exist in the world, and we're kind of adapting them to our own use.
00:06:16
◼
►
But honestly, there are some times that I've had to invent something that I'm kind of making
00:06:21
◼
►
And maybe the solution to this exists in a more concrete and authoritative way in the
00:06:26
◼
►
universe, but I typically don't spend my time when I have a problem I need to solve like,
00:06:31
◼
►
okay, let me go to the journals and research all of the past work that people have done
00:06:37
◼
►
in this area.
00:06:38
◼
►
Like, more often than not, for better or worse, I tend to just not, you know, I start with
00:06:43
◼
►
a straightforward solution.
00:06:45
◼
►
And if I hit a wall, like I hit a place that I can't do something, or I'm trying to solve
00:06:49
◼
►
a problem that's too sophisticated, maybe I'll go and try and kind of research something.
00:06:53
◼
►
But typically, I kind of just start doing the basic, what I think my computer science
00:06:58
◼
►
professor would always call the naive solution.
00:07:01
◼
►
And I start there, and then I expand out from there.
00:07:05
◼
►
And what's interesting, I found is that in practice, the naive solution is often good
00:07:10
◼
►
The naive solution is often what I end up keeping with.
00:07:15
◼
►
Not necessarily because I like, usually the naive solution isn't as performant for whatever
00:07:20
◼
►
that means for what you're doing.
00:07:23
◼
►
But often, the nice thing about a naive solution is that it's often really clear and understandable.
00:07:29
◼
►
And the clever solution is often really complicated.
00:07:32
◼
►
Like if you look at sorting a list, like this canonical example of an algorithm, I can explain
00:07:39
◼
►
to someone how insertion cert works, which is essentially, you take an item off the list,
00:07:45
◼
►
and then you move along the list and see where it needs to go.
00:07:49
◼
►
And you look, take the next one, and you move your way along.
00:07:51
◼
►
And you kind of, you can very straightforward, like the actual code for an insertion sort
00:07:56
◼
►
is very straightforward.
00:07:58
◼
►
Trying to explain to someone how quicksort works, which I understand like myself, where
00:08:03
◼
►
it's like you're partitioning the data into log n partitions, and in each of those you
00:08:09
◼
►
sort and then you combine them back together in a clever way.
00:08:12
◼
►
Like it's clever, and it's more performant, and I'm glad that my collection framework
00:08:18
◼
►
But in practice, it's not very maintainable or easy to understand.
00:08:22
◼
►
And the analog of those and things that I actually use in my day to day life, I often
00:08:26
◼
►
find that the naive solution can actually sometimes be better.
00:08:29
◼
►
And I have a few examples that we'll get into in a bit of places where I've run into
00:08:32
◼
►
this recently.
00:08:33
◼
►
But it's just kind of an interesting thing to think about where sometimes you don't
00:08:37
◼
►
have to have a clever algorithm, you can just need to have an effective algorithm and either
00:08:42
◼
►
your performance will be fine, or even if it's a bit slow, it might be easier to maintain
00:08:49
◼
►
and overall be more reliable.
00:08:51
◼
►
- Oh yeah, and that's ultimately more important.
00:08:54
◼
►
Hardware these days is really, really fast.
00:08:58
◼
►
And so it's always, this is like the kind of the root of all evil being premature optimization
00:09:03
◼
►
kind of thing.
00:09:04
◼
►
It's always good to try the naive solution first, because chances are it'll probably
00:09:12
◼
►
There's been very few cases where I've had to get really clever.
00:09:15
◼
►
Like normally I just try to do something in a straightforward way, because as you said,
00:09:18
◼
►
it is better for things like maintainability and especially code readability.
00:09:23
◼
►
If you write something really clever and you come back to it in two months, are you going
00:09:27
◼
►
to understand what it's doing and be able to debug it or expand it or maintain it?
00:09:32
◼
►
Whereas if something is very straightforwardly done in a naive looking way, it's actually
00:09:38
◼
►
really easy to read and really easy to understand.
00:09:39
◼
►
So that's better long term for maintainability.
00:09:42
◼
►
But also just like, the hardware is just so fast, don't underestimate it.
00:09:48
◼
►
Don't assume until you've actually tried the naive solution first, don't assume that
00:09:51
◼
►
it will be too slow.
00:09:53
◼
►
That being said, one of the most valuable things I learned in my computer science algorithms
00:09:58
◼
►
class is the concept of algorithmic complexity.
00:10:02
◼
►
This is basically the rate at which the performance or memory usage gets affected as the size
00:10:11
◼
►
of the input grows.
00:10:13
◼
►
So this is the big O notation in computer science stuff and stuff like that.
00:10:17
◼
►
And so the idea basically is if you have two nested loops, first iterate over all the things
00:10:23
◼
►
on the outside, and then for each iteration of all the things, iterate over all the things
00:10:27
◼
►
again and do something with whatever you find.
00:10:30
◼
►
That grows exponentially with the size of the input because for every value in the input,
00:10:36
◼
►
it has to do that value or the number of values squared number of operations.
00:10:41
◼
►
Whereas if you can do something in one pass, that's only doing number of values type of
00:10:47
◼
►
And so the idea of designing algorithms to say only do something in a single pass or
00:10:54
◼
►
to only do something in place instead of needing a whole bunch of memory or things like that,
00:10:59
◼
►
that does have value to me more frequently than I think because there's simple things.
00:11:06
◼
►
I can design my app in Overcast.
00:11:10
◼
►
I only usually have about 10 to 30 unplayed podcast episodes.
00:11:16
◼
►
And so I can design the app such that it works fine for people who have 10 to 30 unplayed
00:11:20
◼
►
episodes because that's what I'm living with and that's kind of what I can test as being
00:11:23
◼
►
fast in my own day-to-day usage of it.
00:11:26
◼
►
But there are some people who have 500 unplayed episodes or 10,000 unplayed episodes.
00:11:31
◼
►
Yes, I know it sounds crazy, but we've done episodes on this before about like extreme
00:11:36
◼
►
users or extreme conditions.
00:11:38
◼
►
And so I actually had to make a test account that subscribed to like a thousand podcasts
00:11:43
◼
►
and didn't listen to any episodes for a year.
00:11:45
◼
►
So it has this massive back catalog and I have to test things on that because sometimes
00:11:49
◼
►
like the assumptions I make when I'm dealing with a really small input size like 20 or
00:11:54
◼
►
30 simply are not performance enough or not even usable or might crash if you have like
00:12:01
◼
►
a couple hundred or a couple thousand of something.
00:12:04
◼
►
And so it is like the algorithmic complexity does end up mattering in those extreme cases.
00:12:11
◼
►
If you have something that grows very quickly, some kind of very complicated method like
00:12:15
◼
►
my playlist sorting method is exponential and it doesn't matter when you have 30, but
00:12:20
◼
►
it does matter when you have a thousand.
00:12:23
◼
►
And that makes the whole app basically unusable.
00:12:26
◼
►
So I had to do things to fix that and I had to measure it with instruments and figure
00:12:31
◼
►
out what was slow and then I found this one method.
00:12:33
◼
►
It was again, it was like a nested loop and it was like, "Oh boy, that's going to be real
00:12:37
◼
►
And like you don't notice it when it's a small amount of input, but it becomes a problem
00:12:41
◼
►
when it's a big amount.
00:12:42
◼
►
- Yeah, and I think that's a good example where it's the, like sometimes you have to
00:12:48
◼
►
be clever and sometimes you have to go to literature or have to go to places to find
00:12:53
◼
►
the clever solution that someone has invented a method for doing this in a more performant
00:12:59
◼
►
But it's a lovely, I love the approach though of just not starting there and not trying
00:13:04
◼
►
to be too clever.
00:13:05
◼
►
And I recently, and this is, I think actually a good concrete example to kind of make this
00:13:10
◼
►
So I've been, as we'd mentioned a few episodes ago, I've been making watch faces recently.
00:13:14
◼
►
And one of the things that's always bugged me about the Apple Watch is that if you look
00:13:18
◼
►
at the time, or you're trying to look at the date, at certain times of the day you won't
00:13:24
◼
►
be able to see it because the date is covered by the hour hand or the minute hand, which
00:13:30
◼
►
is silly because this isn't a physical object.
00:13:33
◼
►
This is something that can move things around.
00:13:37
◼
►
- By the way, for the record, physical objects that have this problem usually have hands
00:13:41
◼
►
shaped such that it's not a problem.
00:13:44
◼
►
And also because they're three dimensional, you can usually just tilt the object to the
00:13:48
◼
►
side slightly and see under the hand.
00:13:50
◼
►
- An excellent point.
00:13:51
◼
►
So the digital version is worse than the physical version, which just annoys me at so many levels.
00:13:58
◼
►
And so in all my watch faces, what I wanted to do is if I show the date, I want to make
00:14:02
◼
►
sure that it's never hidden by the hands.
00:14:05
◼
►
And so I needed to come up with a method for moving the date around.
00:14:09
◼
►
So essentially, and I'll have a link in the show notes to a kind of a video of showing
00:14:13
◼
►
this in action.
00:14:14
◼
►
But so what I want to do is as the hands sweep along, if either of the hands is going to
00:14:21
◼
►
cover the date, I want to move the date out of the way so that it is still visible.
00:14:28
◼
►
And the reality is you don't have to actually move the date very much in order to accomplish
00:14:32
◼
►
this because in practice, it's very, very subtle arcs that you're having to move it
00:14:39
◼
►
So it doesn't actually even look really weird because it'll snap back into place.
00:14:43
◼
►
But that was my goal.
00:14:44
◼
►
And so I need to kind of in this context, I need to make an algorithm to reposition
00:14:48
◼
►
this and work out where the date should be displayed at any given time.
00:14:52
◼
►
And I started down the road and this is like, this is why this topic came into my head was
00:14:56
◼
►
I forgot the lesson of starting simple, instead complicated, because I've been doing so much
00:15:01
◼
►
trigonometry and math and all these kind of clever things to for some of my layouts in
00:15:06
◼
►
watch design, you have to do a tremendous amount of trigonometry, like it's just it's
00:15:11
◼
►
But the I started down this road of like, okay, can I kind of come up with this system
00:15:15
◼
►
of equations and constraints that I'm opting to kind of optimize over to work out when
00:15:20
◼
►
I'm going to be over something and then it was easy to handle the case of one hand because
00:15:25
◼
►
I can easily detect if the date areas, you know, being overlapped by one thing, but then
00:15:30
◼
►
the tricky thing is, well, if I move it, then it may intersect the other thing.
00:15:35
◼
►
And then do I move where do I move it from there, because I could then potentially move
00:15:38
◼
►
it back if I didn't add me if I didn't have a clever equation for that.
00:15:43
◼
►
So I have all this complexity, and I can't get anywhere.
00:15:46
◼
►
And so I'm like, what is there a simple way to do this.
00:15:48
◼
►
And what I came up with was this like, pointlessly simple version of this algorithm that turned
00:15:54
◼
►
out in practice to work really well.
00:15:57
◼
►
And so all I do is I had the so you look at you look at the situation and say, the date
00:16:03
◼
►
is going to be in one of five places.
00:16:05
◼
►
It's either going to be in its normal, like the three o'clock position, like its home
00:16:10
◼
►
position, it's going to be just above or just below the minute hand or just above or just
00:16:16
◼
►
below the hour hand.
00:16:17
◼
►
Like necessarily, those are the five places that it can be, because it'll either be shifted
00:16:23
◼
►
just past or just above either of those hands.
00:16:26
◼
►
But those are the five places it can be like that.
00:16:30
◼
►
That's like my overall assumption.
00:16:32
◼
►
And I think that works.
00:16:33
◼
►
And then all I need to do is say of those five positions, are any of them covered by
00:16:40
◼
►
one of the hands?
00:16:41
◼
►
So that obviously, the is the home position or are one of the other hands covering the
00:16:47
◼
►
other hand essentially.
00:16:48
◼
►
So if you imagine like 315, where both hands are kind of over on the slide, then certain
00:16:53
◼
►
some of those positions are going to be a little complicated.
00:16:55
◼
►
If they are, ignore them.
00:16:57
◼
►
So I start with five, if any of them are have to be discounted, I discount them, you know,
00:17:02
◼
►
so maybe I'll end up with four or three possible locations.
00:17:05
◼
►
And for each of the locations, I just say which one is closest to the three o'clock position,
00:17:09
◼
►
whichever one it is, use that one.
00:17:12
◼
►
And that algorithm works.
00:17:14
◼
►
It's exact, it does exactly what you mean.
00:17:17
◼
►
It's super simple, though, like, and it's like the code for it is incredibly clear,
00:17:21
◼
►
because it's just like, here's five positions.
00:17:24
◼
►
You know, do any of them need to be excluded, which is a very easy, like straightforward
00:17:29
◼
►
operation to do, because I can just look at where it is and look at where the hand is
00:17:32
◼
►
based on the time and say, do they do the are these two things the same, you know, modulo,
00:17:37
◼
►
like the, the width of the hand.
00:17:39
◼
►
And then from that, just like do a quick, you know, distance, like linear, like literal
00:17:44
◼
►
distance between the between the the home position and those things, and which everyone
00:17:50
◼
►
is closest to us.
00:17:51
◼
►
And it works.
00:17:52
◼
►
And I loved that it was one of these things like that solution is a super simple algorithm,
00:17:58
◼
►
very understandable.
00:17:59
◼
►
Anybody could, you know, it's like I could, it took trivial to code up is very, very clear.
00:18:05
◼
►
And it works.
00:18:06
◼
►
And like, is it the most efficient?
00:18:07
◼
►
Is it the most optimal?
00:18:08
◼
►
Like, I don't know.
00:18:09
◼
►
But in this particular case, it works fine.
00:18:11
◼
►
And I love anytime I can find these solutions where it's like this really straightforward,
00:18:16
◼
►
simple algorithm for solving a clever problem, but not in a way that is going to hurt my
00:18:21
◼
►
head or in you know, in six months, if something good saying doesn't work quite right, or
00:18:25
◼
►
I change the shape of my watch or like something changes, and I have to debug something and
00:18:29
◼
►
it's like a complete nightmare because it's a big series of linear equations that I barely
00:18:34
◼
►
Like, there's always that thing where people say, you know, the problem with writing the
00:18:37
◼
►
cleverest code is that it's like debugging is twice as hard as coding.
00:18:42
◼
►
And so if you code at your limit of intellect, debugging is going to be impossible, but you
00:18:48
◼
►
have to code at half your intellect, so that when later when you're debugging it, you
00:18:52
◼
►
can use your full intellect and still solve the problem.
00:18:55
◼
►
I like that.
00:18:56
◼
►
That's a good one.
00:18:57
◼
►
We are brought to you this week by Linode.
00:19:00
◼
►
With Linode, you have access to a suite of powerful hosting options with prices starting
00:19:04
◼
►
at just $5 a month.
00:19:06
◼
►
You can be up and running with your own virtual server in the Linode cloud in under a minute.
00:19:10
◼
►
Whether you're just getting started with your first server or deploying a more complex system,
00:19:14
◼
►
like I mean, I host a bunch of stuff at Linode.
00:19:15
◼
►
I host all of my all of my web stuff there, including all of Overcast.
00:19:19
◼
►
And that is something like 25 servers at this point.
00:19:23
◼
►
And whether you have just one or whether you have 25, whether you have 100 Linode is a
00:19:27
◼
►
great choice.
00:19:28
◼
►
They have the fastest hardware and network.
00:19:31
◼
►
They have fantastic customer support behind it all if you need any help with anything.
00:19:35
◼
►
And it has just never been easier to launch Linode cloud server.
00:19:37
◼
►
They make it super easy.
00:19:38
◼
►
They have great documentation, great support, great help.
00:19:41
◼
►
And they guarantee 99.9% uptime for your server.
00:19:44
◼
►
Once your server is up, they intend to keep it that way.
00:19:47
◼
►
They also now offer additional storage, block storage is now out of beta.
00:19:51
◼
►
So Linode has fantastic pricing options available.
00:19:55
◼
►
Plans start at one gig of RAM for just $5 a month.
00:19:59
◼
►
And they offer high memory plans as well, starting at 16 gigs of RAM and lots of stuff
00:20:04
◼
►
As a listener of the show, you can get a $20 credit if you sign up at linode.com/radar.
00:20:09
◼
►
So that will support us.
00:20:10
◼
►
That will show your support for the show and Relay FM and you'll get $20 towards any Linode
00:20:16
◼
►
So if you get $5 a month, one gig plan, that could be four months for free.
00:20:19
◼
►
And with a seven day money back guarantee, there is nothing to lose.
00:20:22
◼
►
I love Linode.
00:20:23
◼
►
I highly suggest you check it out.
00:20:25
◼
►
It is the nicest web host I've ever used, bar none.
00:20:29
◼
►
And one of the nicest web apps I've ever used.
00:20:31
◼
►
It's really, really nice.
00:20:33
◼
►
So go to linode.com/radar to learn more and sign up and take advantage of that $20 credit
00:20:39
◼
►
or use promo code radar2018 at checkout.
00:20:42
◼
►
Thank you so much to Linode for supporting this show and Relay FM.
00:20:47
◼
►
So one thing I found, I love coming up with a clever algorithm, not in the sense that
00:20:52
◼
►
it's super complicated, but I love when I find something stupid that works.
00:20:56
◼
►
Something that's just like, I can't believe, when you can literally just say, I can't believe
00:21:02
◼
►
It's such an incredible pleasure as a programmer when you find some really dumb solution or
00:21:07
◼
►
work around that's like, you feel like you're getting away with something.
00:21:10
◼
►
This shouldn't be this easy.
00:21:12
◼
►
It shouldn't work.
00:21:14
◼
►
But yet it does.
00:21:16
◼
►
And that is one of the most satisfying things you do as a programmer.
00:21:20
◼
►
Yeah, no, absolutely.
00:21:21
◼
►
And I think there is something just so, and I think in many ways, those are my favorite
00:21:26
◼
►
moments of where you have these moments of insight where you're like, huh.
00:21:29
◼
►
Yeah, no, the super simple basic version actually works.
00:21:32
◼
►
I had another one that comes to mind for me of, I had, so in Sleepless Plus, I do automatic
00:21:37
◼
►
sleep tracking now, which at first I thought was gonna be this ridiculously complicated
00:21:42
◼
►
machine learning or have it to get into crazy algorithms problem to solve.
00:21:49
◼
►
And I sort of go in, but to start with, I was just like, well, it's just like, I've
00:21:53
◼
►
been collecting all this manual data.
00:21:54
◼
►
And so my manual sleep analysis where you use the actual accelerometer movements of
00:21:59
◼
►
your wrist during the night and use that to approximate your sleep.
00:22:02
◼
►
And I had all this data and I was like, well, let me just plot of all the data that's being
00:22:07
◼
►
collected currently by the system against the data that I already have and kind of see
00:22:14
◼
►
if there's vague correlations.
00:22:16
◼
►
And the, of course, the, there's this moment where I look at the data, I'm like, active
00:22:20
◼
►
calorie data aligns exactly with what I was calling restlessness previously.
00:22:28
◼
►
That's interesting.
00:22:29
◼
►
So instead of having to do, which makes sense, like intuitively for what they're measuring
00:22:34
◼
►
with active calories, that they're looking for movement as well as like heart rate data.
00:22:37
◼
►
But it was this funny thought of like, huh, so all that complicated stuff I was thinking
00:22:41
◼
►
I was going to have to do with like looking at your heart rate and doing all this analysis,
00:22:45
◼
►
you know, it probably is pretty much just like some kind of heuristics over active calories.
00:22:50
◼
►
And then it's, and then like magic, it works.
00:22:53
◼
►
And basically, that was what I did.
00:22:55
◼
►
And that's what happens.
00:22:56
◼
►
And it's like, I just remember, I still have a screenshot of it, of this, like, doing
00:22:59
◼
►
this little plot of like my data versus active calorie data, you know, because I tried with
00:23:04
◼
►
heart rate data, and that didn't really align very correctly.
00:23:07
◼
►
And it's just like, huh, these align perfectly.
00:23:09
◼
►
Like it's like 98% of exactly the same data.
00:23:12
◼
►
And all I have to do is solve that 2%.
00:23:14
◼
►
But it seems like I'm getting away with something because it's super simple and super
00:23:17
◼
►
straightforward.
00:23:18
◼
►
I didn't have to do like this crazy, like, okay, I need to encode all this data into
00:23:22
◼
►
some method.
00:23:23
◼
►
And I can throw it into core ML, whatever that means, I don't even know.
00:23:25
◼
►
And then like, do some magic.
00:23:26
◼
►
It's like, no, I can just take the data and just process it in a reasonable way using
00:23:31
◼
►
some clever heuristics.
00:23:32
◼
►
And, you know, I validate this against a lot of data and as long as it still works, then
00:23:38
◼
►
Yeah, my favorite hack algorithm is the fast inverse square root, which I've never had
00:23:45
◼
►
But I came across this and, you know, reading about it a long time ago, and it was something
00:23:49
◼
►
in Quake 3 Arena.
00:23:51
◼
►
And it was, it basically approximates the inverse square root by not doing any division
00:23:58
◼
►
at all and only by like doing this weird bit shift with this one special number.
00:24:03
◼
►
And like in the code, like in the Quake 3 source code, it even says like, you know,
00:24:08
◼
►
the spelled out version of WTF after this one line with this magic number.
00:24:11
◼
►
Like why does this even work?
00:24:13
◼
►
But it totally does.
00:24:15
◼
►
And so, yeah, that's like, I just love that feeling of like, either I can't believe this
00:24:19
◼
►
works and/or I don't understand why this works, but it does.
00:24:24
◼
►
Also like one area of algorithms that I find very satisfying is when you can make a jump
00:24:30
◼
►
in performance that is ridiculous.
00:24:32
◼
►
Like that feels like you're getting away with something there too.
00:24:35
◼
►
It's like not only in simplicity, but like if like a new tool becomes available to you
00:24:40
◼
►
or a new technique or new hardware becomes available to you, that takes something that
00:24:44
◼
►
used to be a very slow thing or a very complicated thing and makes it very, very fast.
00:24:48
◼
►
Like not getting like a 2x performance, but getting like a thousand x performance.
00:24:52
◼
►
And that kind of thing happens a lot of times, you know, as hardware advances, we get things
00:24:56
◼
►
like GPU acceleration, which I've never really had a use for directly, but like, you know,
00:25:02
◼
►
if you can, if you're doing something complicated on the CPU that the GPU could be doing for
00:25:07
◼
►
you, you can get like, you know, 10x, 100x, 1000x kind of improvements with GPU acceleration
00:25:12
◼
►
if it's the right kind of work.
00:25:14
◼
►
Where I find value in this is in vector operations.
00:25:17
◼
►
Like I've talked about this before, like the accelerate framework on iOS and Mac OS is
00:25:21
◼
►
just fantastic.
00:25:23
◼
►
And it doesn't apply to everything, but if you find yourself like frequently going through
00:25:28
◼
►
large arrays of numbers to do big batch operations on them, whether it's like, you know, multiplying
00:25:33
◼
►
them against each other or taking the absolute value of a big batch of numbers or doing any
00:25:38
◼
►
kind of like, you know, comparisons or merging or other like applying the same math operation
00:25:44
◼
►
to a big array of numbers.
00:25:46
◼
►
If you can find a way to either use the vector tools directly against your big batch of numbers
00:25:52
◼
►
or if you can find a way to restructure your need to use vector operations.
00:25:59
◼
►
So like even if you need to do a little bit of setup to like, okay, I was doing this big
00:26:03
◼
►
strip operation.
00:26:04
◼
►
If I can just put these numbers into an array of floats, then I can call this one function
00:26:09
◼
►
call on it that can do the entire job in way less time and therefore also using way less
00:26:17
◼
►
But like, you know, it's using vector units on the processor to also do it in way less
00:26:20
◼
►
time and that kind of thing.
00:26:23
◼
►
Like there a lot of times there's there's opportunity like that where like if you can
00:26:26
◼
►
just work your data a little bit to fit something that's a little bit different from what you
00:26:31
◼
►
were doing before, you can use a different kind of tool that might be orders of magnitude
00:26:37
◼
►
And I always find there I'm so satisfied using vector stuff because you know, I do a lot
00:26:42
◼
►
of audio processing and a lot of you know, you know, processing of large amounts of numbers
00:26:46
◼
►
and the vector stuff makes it so easy and so fast.
00:26:50
◼
►
Yeah, I think too it's what you're describing there is something that I've run into many
00:26:53
◼
►
times where sometimes a simple data transformation can radically change your performance or change
00:27:00
◼
►
the way that you can structure an algorithm to reason about data.
00:27:04
◼
►
And like one that I find myself doing a lot is sometimes you take an array and turn it
00:27:08
◼
►
into a dictionary where you if you if you're doing any kind of operation that requires
00:27:14
◼
►
you to kind of keep referencing elements in the array, but you have to go and find them
00:27:21
◼
►
essentially to do that operation.
00:27:24
◼
►
Like the number I can like in most so many of my apps, there's always so there's something
00:27:27
◼
►
where I take an array, I turned it into a dictionary, and then I can go and then reason
00:27:32
◼
►
about it much more performantly later.
00:27:34
◼
►
And sometimes this even comes into cases where you're trying to do some kind of database
00:27:42
◼
►
This is something where this is just a little performance optimization, I suppose, but like,
00:27:45
◼
►
I'm going to, you know, I'm rather than making five or 10 or 20 select queries, you make
00:27:50
◼
►
one that is the union of those, and then put them in a dictionary and kind of you can look
00:27:55
◼
►
look them up later.
00:27:57
◼
►
I often find that's way, way faster.
00:27:58
◼
►
But I think the key thing that you're describing there is that sense that it's so it's so often
00:28:03
◼
►
if you can, there's if there's some data transform you can do with what you're out what you're
00:28:07
◼
►
working on, that's somehow radically changes it and looking for those and being aware that
00:28:12
◼
►
this is a possible solution that you don't have to, you don't have to keep data in the
00:28:16
◼
►
form that you get it in can often just be a powerful tool to find a kind of a quick
00:28:21
◼
►
or clever or you know, like foolishly simple algorithm for processing it.
00:28:27
◼
►
And by the way, don't forget about wonderful unused foundation classes set and ordered
00:28:33
◼
►
And of course, they're mutable equivalents.
00:28:34
◼
►
Those are really helpful and things like that.
00:28:37
◼
►
But anyway, that's about all we have time for today.
00:28:39
◼
►
But I wish everyone the best with their algorithm finding and their the satisfaction and finding
00:28:44
◼
►
something really dumb that works.
00:28:47
◼
►
No, it is an absolutely delight.
00:28:48
◼
►
And I think it's one of the one of the funnest parts of computer science.
00:28:50
◼
►
And like, when it when you have those moments, like, relish them, enjoy them, because they
00:28:56
◼
►
don't come all that often.
00:28:57
◼
►
But you know, remember your what you learned in your first CS 101 class and it'll serve
00:29:02
◼
►
Thanks for listening and we'll talk to you next week.