3 ms·

When people talk about learning algorithms, what do they mean? I recently spent a few hours reading about and implementing A* for the NPCs in a video game I'm

When people talk about learning algorithms, what do they mean? I recently spent a few hours reading about and implementing A* for the NPCs in a video game I'm working on. Are you talking about being able to write A* and other algorithms from scratch with no reference material?

VLM 12y ago
Some aspects of this in the culture are disturbingly binary and the world has WAY too many people who don't know the engineering application of A* so they just make something up. Knowing that it exists and has certain (detailed) characteristics is probably 95% of the use. Why didn't you use B* (rhetorical question, whats important is you have an answer not what it is) Folks who don't know path algos probably think I'm making up B* but it really exists and was invented just before I started programming and I have a memory for "new" stuff vs old. Its useful to have a steel beam and know how to apply it to construction. Knowing how its made and the metallurgy and how that impacts the application levels you up. Then there's a whole sea of lower level construction vocational laborers who don't know steel beams exist and they'll just bodge something together with stuff from the junk yard and when it collapses, well, there's no guarantees in life and it was cheap and the academics never know anything anyway so stop complaining, and last but not least the social butterflies who heard the Jones's next door, who are billionaires, built their wall out of recycled plastic so we'll use that to hold up the roof instead of proletarian wood or even this steel beam stuff.
aidos 12y ago
I can't speak for anyone else but I think the important thing is understanding the tradeoffs of different ways of accessing data. At it's simplest you have things like checking for existence using linear scans of arrays. Anyone with experience sees that as a bad thing to do because they understand that it's inefficient for any sort of sizeable array. But those who don't understand algorithms or data structures won't even know there's an issue. And that's the simplest case really. When you have a list and you need to efficiently add and remove items from both ends - then you want some sort of double-ended queue. I know where to find the one in my std lib and I know when I need to use it - which it turns out is almost never - I thought I did the other day, then I found a simpler way, which was actually a bit disappointing :) Then, as you say, you have things like A* or R-trees. The more of these you have an handle on - even just to know they exist, the better position you'll be in when you need them. But I don't even think that's the most important part of knowing data structures and algorithms (and really, I'm sure none of that's news to you if you're implementing A* searching). For me it's more about understanding efficient patterns for data access. So much of the work I do is about efficiently pushing data around in different forms. Often having a core chunk of data and then a couple of different indexing structures to allow me to interrogate it depending on the info I need.
pron 12y ago
> Are you talking about being able to write A* and other algorithms from scratch with no reference material? No, I mean knowing what algorithms/data-structures are available, what their characteristics are, and how to tweak them. This way you can say stuff like: with those data access patterns, we'll need a B+-tree with links for concurrency, modified to not delete depleted nodes until such-and-such. Or, something like: doing that efficiently requires an optimization that's NP-hard because the problem reduces to graph partitioning, but we can use an approximate solution that should work well-enough in this case.
coldtea 12y ago
First of all, you should know that there exists an A* , and what it can be used for. Second, you should know when to use A* or something else, the trade-offs etc. Third, you should know how to implement A* , when needed, with reference material (you'd be surprised how many programmers can't read/understand the reference material even when its given to them, or don't know enough programming to put it in code). Of course you could get by with never using A* or tries or whatever advanced algorithm, not even in some ready-made API form. E.g. if you just do some CRUD or some simple web programming. But for the kind of programmers we're talking here, those three are paramount. The thing you mention, implementing it from scratch with no reference material might be impressive, but it's more of a circus act.
- danenania 12y ago
  Aside from as a learning experience or display of prowess, what's the point of implementing A* yourself? In my experience, knowing which prebuilt algorithms and data structures to reach for matters more than being able to implement them myself. Not saying there isn't value in learning or that it doesn't help flex the problem solving muscles, but in most software domains, I think that practically speaking there are more important skills to focus on after you've mastered the basics of time and space complexity.
  - coldtea 12y ago
    >Aside from as a learning experience or display of prowess, what's the point of implementing A yourself?* Because for people working in those kinds of problems we're talking about (we started from Valve and games IIRC, but it could also be Google, Facebook engineers etc) you don't just download some off the shelf API. You'll need to create something of your own to: - have the whole IP - mold it specifically to the domain logic you need - take control of it's memory and performance characteristics based on your constraints - implement it in the language your company uses, for which no ready made A* (or some other algorithm) is available - you'll need to make it talk to different infrastructure, libs etc - you might be the one writing the library API yourself As I said, this is not about what a CRUD programmer will need. But as you can see everyday in HN, people write these and other algorithms all the time in their jobs doing more serious engineering.

VLM 12y ago

Some aspects of this in the culture are disturbingly binary and the world has WAY too many people who don't know the engineering application of A* so they just make something up. Knowing that it exists and has certain (detailed) characteristics is probably 95% of the use. Why didn't you use B* (rhetorical question, whats important is you have an answer not what it is) Folks who don't know path algos probably think I'm making up B* but it really exists and was invented just before I started programming and I have a memory for "new" stuff vs old. Its useful to have a steel beam and know how to apply it to construction. Knowing how its made and the metallurgy and how that impacts the application levels you up. Then there's a whole sea of lower level construction vocational laborers who don't know steel beams exist and they'll just bodge something together with stuff from the junk yard and when it collapses, well, there's no guarantees in life and it was cheap and the academics never know anything anyway so stop complaining, and last but not least the social butterflies who heard the Jones's next door, who are billionaires, built their wall out of recycled plastic so we'll use that to hold up the roof instead of proletarian wood or even this steel beam stuff.

aidos 12y ago

I can't speak for anyone else but I think the important thing is understanding the tradeoffs of different ways of accessing data. At it's simplest you have things like checking for existence using linear scans of arrays. Anyone with experience sees that as a bad thing to do because they understand that it's inefficient for any sort of sizeable array. But those who don't understand algorithms or data structures won't even know there's an issue. And that's the simplest case really. When you have a list and you need to efficiently add and remove items from both ends - then you want some sort of double-ended queue. I know where to find the one in my std lib and I know when I need to use it - which it turns out is almost never - I thought I did the other day, then I found a simpler way, which was actually a bit disappointing :) Then, as you say, you have things like A* or R-trees. The more of these you have an handle on - even just to know they exist, the better position you'll be in when you need them. But I don't even think that's the most important part of knowing data structures and algorithms (and really, I'm sure none of that's news to you if you're implementing A* searching). For me it's more about understanding efficient patterns for data access. So much of the work I do is about efficiently pushing data around in different forms. Often having a core chunk of data and then a couple of different indexing structures to allow me to interrogate it depending on the info I need.

pron 12y ago

> Are you talking about being able to write A* and other algorithms from scratch with no reference material? No, I mean knowing what algorithms/data-structures are available, what their characteristics are, and how to tweak them. This way you can say stuff like: with those data access patterns, we'll need a B+-tree with links for concurrency, modified to not delete depleted nodes until such-and-such. Or, something like: doing that efficiently requires an optimization that's NP-hard because the problem reduces to graph partitioning, but we can use an approximate solution that should work well-enough in this case.

coldtea 12y ago

First of all, you should know that there exists an A* , and what it can be used for. Second, you should know when to use A* or something else, the trade-offs etc. Third, you should know how to implement A* , when needed, with reference material (you'd be surprised how many programmers can't read/understand the reference material even when its given to them, or don't know enough programming to put it in code). Of course you could get by with never using A* or tries or whatever advanced algorithm, not even in some ready-made API form. E.g. if you just do some CRUD or some simple web programming. But for the kind of programmers we're talking here, those three are paramount. The thing you mention, implementing it from scratch with no reference material might be impressive, but it's more of a circus act.

danenania 12y ago
Aside from as a learning experience or display of prowess, what's the point of implementing A* yourself? In my experience, knowing which prebuilt algorithms and data structures to reach for matters more than being able to implement them myself. Not saying there isn't value in learning or that it doesn't help flex the problem solving muscles, but in most software domains, I think that practically speaking there are more important skills to focus on after you've mastered the basics of time and space complexity.
- coldtea 12y ago
  >Aside from as a learning experience or display of prowess, what's the point of implementing A yourself?* Because for people working in those kinds of problems we're talking about (we started from Valve and games IIRC, but it could also be Google, Facebook engineers etc) you don't just download some off the shelf API. You'll need to create something of your own to: - have the whole IP - mold it specifically to the domain logic you need - take control of it's memory and performance characteristics based on your constraints - implement it in the language your company uses, for which no ready made A* (or some other algorithm) is available - you'll need to make it talk to different infrastructure, libs etc - you might be the one writing the library API yourself As I said, this is not about what a CRUD programmer will need. But as you can see everyday in HN, people write these and other algorithms all the time in their jobs doing more serious engineering.