>But building this taught me something that I think about constantly: technical correctness is worthless if you’re solving the wrong problem.
>You can write perfect code. You can build flawless systems. You can optimize the sh*t out of your cost function. And you can still end up with something that sucks.
>The important part isn’t the optimization algorithm. The important part is figuring out what you should be optimizing for in the first place.
>Most of the time, we don’t even ask that question. We just optimize for whatever’s easy to measure and hope it works out.
>Spoiler: it probably doesn’t.
As tech people, it's kinda hard to admit it, but it's totally correct. Sometimes you actually have to optimize for X, sometimes you don't. It's totally ok to optimize stuff just for passion or to try out new stuff, but if you expect external validation you should do this for things people actually care about.
As an aside, this is also related to the way random companies carry out technical interviews, cargo-culting FAANG practices.
FAANGs tend to care about optimizing a lot of stuff, because when you have billions of customers even the smallest things can pile up a lot of money.
If you are a random company, even a random tech company, in many domains you can go a long way with minimal tuning before you have to turn to crazy optimization tricks.
For example, one day has almost 100k seconds, so if you have 100k daily requests (which is still a lot!), even if you have 10x peaks during the day, you are most likely getting <= 10 requests per second. It's not that much.
You can take it one step further: imagine you live in a smallish country (10 million people).
If your market share is 10% of the population and they make 1 request per day, that is just 10 requests per second.
10% is a large market share for everyday use. So you can use 1% market share and 10 requests and it will still be just 10 reqs/sec.
In fact, 1% market share of 10 million people and you can use the number of requests each user makes as the number of requests that your server will get (on average) per second.
There is a lot of business in small countries that never need to scale (or business in narrow sectors, e.g. a lot of B2B).
>And having some hashmap added at one point because I know how stuff works properly doesn't cost me anything.
Sure if it costs nothing, go for it.
With that said,
1) time complexity is just one kind of complexity. In real life, you may be interested in space complexity, too. Hashmaps tend to use more "space" than regular arrays, which might be an issue in some cases. Also, some data have a lot of collisions when managed using hashmaps, which may not be ideal.
A well thought design with respect to performance and scalability relies on a few assumptions like these, which could lead to one solution or another.
2) a real-world application is not necessarily constrained (in space or time) by traversing an array or a hashmap. Unless your application is mostly processing, sorting,... data structures, this is probably not the case.
For example, consider a simple application which lets users click and reserve a seat at a theater/conference/stadium/train/whatever.
The application is essentially a button which triggers a database write and returns a 'Success' message (or maybe a PDF). In this case, you are mostly constrained by the time needed to write on that database and maybe the time needed for a PDF generation library to do its things. You are in fact interacting with two "APIs" (not necessarily Web, REST APIs!): the database API and the third-party PDF library API. I don't have any special knowledge about PDF libraries, but I suspect their performance depends on the amount of data you have to convert to PDF, which is more or less the same for every user. And when it comes to databases your performance is mostly limited by the database size and the number of concurrent requests.
If you think this is too simple, consider additional features like authentication, sending an email notification, or maybe choosing between different seat categories. In most cases, your code is doing very little processing on its own and it's mostly asking stuff to other libraries/endpoints and getting an answer.
Consider another example. You want to find out the distance between a user (which is assumed to have a GPS receiver) and a known place like Times Square or whatever. What you have is a mobile app which gets the GPS position from the phone and computes the distance between the user and the known coordinates, using a known formula. The input size is always the same (the size of the data structure holding GPS coordinates), the formula to compute the distance is always the same, so processing time is essentially constant.
Now let's say you have a bunch of well known places, let's say N. The app computes the distance for all N places, effectively populating an array or an array of dicts of whatever, with length N. Maybe the app also sorts the data structure to find the 5 closest places. How long will that take? How many places you need to compute and sort before a user notices the app is kinda slow (i.e. before, say, 200 milliseconds) or exceedingly slow (let's say above 1 second, or even 500 ms)?
There are a lot of scenarios and real-world applications where, using modern hardware and/or external APIs and reasonable expectations about clients (users don't care about microseconds, sending an email or push notification in one second is totally acceptable in most cases,...), you are not constrained by the data structure you are using unless you're working at a large scale.
The problem isn't so much finding the shortest path, but finding the right cost function that adequately matches human satisfaction. Not just distance, not just turns, but also knowing which areas are done, and other small factors.
That is exactly right as anybody who has done the work in a wrong way recognizes.
In a way, the computer science student may or may not have realized that he has stumbled upon one of the biggest problems in software development--the arrogance of ignorance.
Especially with lawn mowers, turns are highly weighted over distance. Also, if you are regularly mowing, then it's not so obvious what has been mowed and what not. So regularization and simplification of the path is even more important than turns so that you can discard whole plots in the to-do list.
Roomba's (RIP) don't have the same memory and turn weight function that humans do, of course.
For an employee the cost function is maximum wage for minimum work. Since at minimum wage, you're paid for your time, this means sweeping as badly and slowly as the minimum the manager accepts.
Hell, given that there is a social safety net, and you'll have costs to do the job (food, public transport, ...) you're probably even better off doing worse than that, and getting fired when the manager is "tired of your shit" or whatever.
Then you'll get unemployment, which is slightly less, but you can invest the time in cooking at home, and you'll eat better and have more money left over.
The best part about these sorts of problems is learning about heuristics. I spent years as a self-taught developer without using heuristics, and once I got the opportunity to use them, it made so many things make more sense, like why do Mathematicians and Physicists take shortcuts instead of doing all the work to do the problem correctly? Because you reduce time by limiting complexity! Big O notation never resonated with me, but I can look at loops, recursion, and just think about problems and say “That will take too long.” With heuristics, you eliminate that. It was eye-opening.
So, good for the author that they spent the time to learn path optimization. Now onto 3D bin packing!
This article even discounts that at minimum wage jobs, you're paid for your time, not the job you do. So this is doing the reverse of what's reasonable. You're better off sweeping the floor slower, because if you finish faster, there is no way any manager will let you go home, job well done. You'll get more work.
Put on headphones with music or a podcast or even youtube, and take 1-2 or even 4 hours more than you would normally do. Have an accident every few days.
Oh, and here's another problem with the best solution. Managers are idiots. They actually have zero clue what's a good time/performance for floor sweeping since they'd never stoop to the level of doing it themselves, even once. If you're going close to best possible, any slight disturbance will make a large difference in your performance, since that's what the manager actually measures. If you're doing a piss-poor job but by changing your speed a bit when something inevitably goes wrong, and you do about the same quality in about the same time every time, your manager will be more happy. Hell, it'll make it easier for him to organize the store so it may actually be better economically too.
The better you optimize this, the worse you're off. Hell, given that many consider you're better off on unemployment you should do worse than the worst the manager accepts (since you get unemployment if the manager fires you but not if you quit). Then you get a bit less money, but you have no costs (you have to pay for food, and public transport, every day, but only if working. Unemployed you can stay at home and cook)
So ... does this optimization tool have a way to accomplish the actual best outcome?
I think you are minmaxing to a cynical degree. Some people just want to do a good job, because somewhere down the line it probably will benefit them to know how to do it.
I don't get it. This entire article seems to be talking around the actual issue. You need to have a dynamics model inside your trajectory planner.
If you have non zero inertia, then refusing to model inertia isn't technically correct or optimal.
The turn penalty is a way to avoid having an explicit dynamics model, which is a nice hack that will probably return pretty good results.
There is also a missing reference to liquidity preference. People don't make expensive and costly plans, because they represent a commitment and obligation to follow the plan through. Unlike what economists say, people don't actually make lifelong commitments at birth and then just follow them. They usually make decisions on the spot with the information they learned during the course of their life.
One option one could use is eg. https://fields2cover.github.io/ but that doesn't work too well if there's lots of obstacles in the fields like in this case. I'm having the same issue at work right now in agricutrural robots, covering the area between rows and rows of trees. Some implements on our robot hang off to one side so paths can't be bidirectional, etc. Lots of interesting constraints.
What is funny to me is that once the plan was drawn, much of the usefull "hard" work was done.
Humans are not perfect like robot so it is pointless to try to find the "perfect" path, in any case, mistakes will be made.
It is also solving for the wrong thing, there is not much benefits travelling less distance, but minimising time spent on the task is the real problem. For those sort of tasks, it is very much like driving: the shortest path is not necesserally the fastest.
Another very important point is that ease of application is of prime importance, it's not very usefull if you need to think hard about which way you should go just to minimize distance, it increase task complexity tremendously for no real benefit.
Considering all that, it is obvious that the real winner solution would be just look at the map and draw a path by hand, using human intuition and heuristics as an algorithm. Even if you would have to make a few corrections, this could be done in minutes instead of hours.
But of course I understand that the point was really to find an application as an excuse to practice working with optimisation algorithms. In that sense, it is a well done job !
Now for how "normal" humans would do it: they would try a few ways and settle on an approximate optimun depending on how much time each pass took and how easy it was to complete. The thing about those sort of task is that they are not really uniform (some places are bound to be dirtier than others and it is easier to approach some features in a certain way), so a naive optimisation like that is unlikely to be what's truly needed even if the solution is technically perfect.
Loving this prime example of why I say we need to identify the genuine systems-theoretic needs of humans and our natural environments. And mathematically/experimentally define & verify them. Optimizing for anything outside of what's literally needed seems to be fundamental to oppression, intended or not.
"The important part is figuring out what you should be optimizing for in the first place.
Most of the time, we don’t even ask that question. We just optimize for whatever’s easy to measure and hope it works out.
Readit News
>You can write perfect code. You can build flawless systems. You can optimize the sh*t out of your cost function. And you can still end up with something that sucks.
>The important part isn’t the optimization algorithm. The important part is figuring out what you should be optimizing for in the first place.
>Most of the time, we don’t even ask that question. We just optimize for whatever’s easy to measure and hope it works out.
>Spoiler: it probably doesn’t.
As tech people, it's kinda hard to admit it, but it's totally correct. Sometimes you actually have to optimize for X, sometimes you don't. It's totally ok to optimize stuff just for passion or to try out new stuff, but if you expect external validation you should do this for things people actually care about.
As an aside, this is also related to the way random companies carry out technical interviews, cargo-culting FAANG practices.
FAANGs tend to care about optimizing a lot of stuff, because when you have billions of customers even the smallest things can pile up a lot of money.
If you are a random company, even a random tech company, in many domains you can go a long way with minimal tuning before you have to turn to crazy optimization tricks.
For example, one day has almost 100k seconds, so if you have 100k daily requests (which is still a lot!), even if you have 10x peaks during the day, you are most likely getting <= 10 requests per second. It's not that much.
You can take it one step further: imagine you live in a smallish country (10 million people).
If your market share is 10% of the population and they make 1 request per day, that is just 10 requests per second.
10% is a large market share for everyday use. So you can use 1% market share and 10 requests and it will still be just 10 reqs/sec.
In fact, 1% market share of 10 million people and you can use the number of requests each user makes as the number of requests that your server will get (on average) per second.
There is a lot of business in small countries that never need to scale (or business in narrow sectors, e.g. a lot of B2B).
Or you could still use multiple instances, not for scaling but for patching without downtime and so on.
Availability can be way more important than sheer performance or number of concurrent requests.
I would just never write code which struggles with n.
And having some hashmap added at one point because I know how stuff works properly doesn't cost me anything.
Sure if it costs nothing, go for it.
With that said,
1) time complexity is just one kind of complexity. In real life, you may be interested in space complexity, too. Hashmaps tend to use more "space" than regular arrays, which might be an issue in some cases. Also, some data have a lot of collisions when managed using hashmaps, which may not be ideal.
A well thought design with respect to performance and scalability relies on a few assumptions like these, which could lead to one solution or another.
2) a real-world application is not necessarily constrained (in space or time) by traversing an array or a hashmap. Unless your application is mostly processing, sorting,... data structures, this is probably not the case.
For example, consider a simple application which lets users click and reserve a seat at a theater/conference/stadium/train/whatever.
The application is essentially a button which triggers a database write and returns a 'Success' message (or maybe a PDF). In this case, you are mostly constrained by the time needed to write on that database and maybe the time needed for a PDF generation library to do its things. You are in fact interacting with two "APIs" (not necessarily Web, REST APIs!): the database API and the third-party PDF library API. I don't have any special knowledge about PDF libraries, but I suspect their performance depends on the amount of data you have to convert to PDF, which is more or less the same for every user. And when it comes to databases your performance is mostly limited by the database size and the number of concurrent requests.
If you think this is too simple, consider additional features like authentication, sending an email notification, or maybe choosing between different seat categories. In most cases, your code is doing very little processing on its own and it's mostly asking stuff to other libraries/endpoints and getting an answer.
Consider another example. You want to find out the distance between a user (which is assumed to have a GPS receiver) and a known place like Times Square or whatever. What you have is a mobile app which gets the GPS position from the phone and computes the distance between the user and the known coordinates, using a known formula. The input size is always the same (the size of the data structure holding GPS coordinates), the formula to compute the distance is always the same, so processing time is essentially constant.
Now let's say you have a bunch of well known places, let's say N. The app computes the distance for all N places, effectively populating an array or an array of dicts of whatever, with length N. Maybe the app also sorts the data structure to find the 5 closest places. How long will that take? How many places you need to compute and sort before a user notices the app is kinda slow (i.e. before, say, 200 milliseconds) or exceedingly slow (let's say above 1 second, or even 500 ms)?
There are a lot of scenarios and real-world applications where, using modern hardware and/or external APIs and reasonable expectations about clients (users don't care about microseconds, sending an email or push notification in one second is totally acceptable in most cases,...), you are not constrained by the data structure you are using unless you're working at a large scale.
In a way, the computer science student may or may not have realized that he has stumbled upon one of the biggest problems in software development--the arrogance of ignorance.
Especially with lawn mowers, turns are highly weighted over distance. Also, if you are regularly mowing, then it's not so obvious what has been mowed and what not. So regularization and simplification of the path is even more important than turns so that you can discard whole plots in the to-do list.
Roomba's (RIP) don't have the same memory and turn weight function that humans do, of course.
Hell, given that there is a social safety net, and you'll have costs to do the job (food, public transport, ...) you're probably even better off doing worse than that, and getting fired when the manager is "tired of your shit" or whatever.
Then you'll get unemployment, which is slightly less, but you can invest the time in cooking at home, and you'll eat better and have more money left over.
So, good for the author that they spent the time to learn path optimization. Now onto 3D bin packing!
Put on headphones with music or a podcast or even youtube, and take 1-2 or even 4 hours more than you would normally do. Have an accident every few days.
Oh, and here's another problem with the best solution. Managers are idiots. They actually have zero clue what's a good time/performance for floor sweeping since they'd never stoop to the level of doing it themselves, even once. If you're going close to best possible, any slight disturbance will make a large difference in your performance, since that's what the manager actually measures. If you're doing a piss-poor job but by changing your speed a bit when something inevitably goes wrong, and you do about the same quality in about the same time every time, your manager will be more happy. Hell, it'll make it easier for him to organize the store so it may actually be better economically too.
The better you optimize this, the worse you're off. Hell, given that many consider you're better off on unemployment you should do worse than the worst the manager accepts (since you get unemployment if the manager fires you but not if you quit). Then you get a bit less money, but you have no costs (you have to pay for food, and public transport, every day, but only if working. Unemployed you can stay at home and cook)
So ... does this optimization tool have a way to accomplish the actual best outcome?
If you have non zero inertia, then refusing to model inertia isn't technically correct or optimal.
The turn penalty is a way to avoid having an explicit dynamics model, which is a nice hack that will probably return pretty good results.
There is also a missing reference to liquidity preference. People don't make expensive and costly plans, because they represent a commitment and obligation to follow the plan through. Unlike what economists say, people don't actually make lifelong commitments at birth and then just follow them. They usually make decisions on the spot with the information they learned during the course of their life.
One option one could use is eg. https://fields2cover.github.io/ but that doesn't work too well if there's lots of obstacles in the fields like in this case. I'm having the same issue at work right now in agricutrural robots, covering the area between rows and rows of trees. Some implements on our robot hang off to one side so paths can't be bidirectional, etc. Lots of interesting constraints.
Considering all that, it is obvious that the real winner solution would be just look at the map and draw a path by hand, using human intuition and heuristics as an algorithm. Even if you would have to make a few corrections, this could be done in minutes instead of hours.
But of course I understand that the point was really to find an application as an excuse to practice working with optimisation algorithms. In that sense, it is a well done job !
Now for how "normal" humans would do it: they would try a few ways and settle on an approximate optimun depending on how much time each pass took and how easy it was to complete. The thing about those sort of task is that they are not really uniform (some places are bound to be dirtier than others and it is easier to approach some features in a certain way), so a naive optimisation like that is unlikely to be what's truly needed even if the solution is technically perfect.
"The important part is figuring out what you should be optimizing for in the first place.
Most of the time, we don’t even ask that question. We just optimize for whatever’s easy to measure and hope it works out.
Spoiler: it probably doesn’t."