3 ms·

Re-invent the wheel. You should implement the most common data structures in your language of choice. [...] While I agree that it helps a lot underst

by mweibel 13y ago

Re-invent the wheel. You should implement the most common data structures in your language of choice. [...] While I agree that it helps a lot understanding those data structures by implementing them, it might be good to add "Don't use them in production!" paragraph.

drawkbox 13y ago
Agreed. Working in games you really do get to work with smart people, yet with the power of C++ everyone wants to recreate their own String class, data structures etc. Game industry largely hates STL. There is also a distain for boost, another large collective of reviewed and hardened standard libraries (POCO is another nice one). The ego is immense at places like this. Programmers feel like they have to do this to compete or deliver over shipping and delivering products that work. Granted there are reasons for doing this such as keeping memory allocations through a common engine library to reduce memory and fragmentation but in most cases it is a moot point. Performance does mean the most many times in this field for the AAA games out there, but not for most games. In web or app development if you are using custom data structures instead of native, in most cases that is wrong. How about consistent data structures that have been built and tested outside the company? The thing is though when the programmer that makes your 5th string class and data structures moves on it will be rehashed by the next, as other developers won't be as effective with them and recreate. It is much more important to understand what data structures to use when and what impact they have on performance. Most of all can the developer ship and understand what is best for the product (not the ego or what will make them look like the hardest programmer of all time -- i.e. Rewriting the string class again and it is 10% faster, even though that is not a problem at all). I have seen some horrible, leaky, buggy data structures in situations like this, because they thought that was the job as led on by the interviewing. I have only really seen this while working in the game industry which I love but it is a problem with shipping product when this bike shedding happens over improvements to the game, engine or real custom needs i.e. the UI libs, event/messaging systems, naming/conventions are typically horrible in situations like this. I also blame consoles for many of these problems as the libs are so jacked, incomplete and old that performance becomes a huge issue and you have to have custom structures just to use the hardware right especially in graphics, physics + networking libs. Yet mobile I have seen less of this problem even though there is less hardware to work with. The next time you play a game and the networking totally sucks, or a game takes forever or simply doesn't ship, understand the culture of the company and the industry might have something to do with it.
kyllo 13y ago
Yeah, the funny thing about all the data structures & algorithms quizzes is that the simplest solution is usually a recursive one, and the big-O performance is sort of irrelevant because chances are you're using a language that doesn't have tail-call optimization and you're going to blow the stack frame for any large value of n anyway.
- gizmo686 13y ago
  Many recursive algorithms only require log(n) entries in the stack. Even if you do start overflowing the stack, it is simple to take a recursive implementation and turn it into an 'iterative' one, where you just manage the stack yourself.

by mweibel 13y ago

drawkbox 13y ago

Agreed. Working in games you really do get to work with smart people, yet with the power of C++ everyone wants to recreate their own String class, data structures etc. Game industry largely hates STL. There is also a distain for boost, another large collective of reviewed and hardened standard libraries (POCO is another nice one). The ego is immense at places like this. Programmers feel like they have to do this to compete or deliver over shipping and delivering products that work. Granted there are reasons for doing this such as keeping memory allocations through a common engine library to reduce memory and fragmentation but in most cases it is a moot point. Performance does mean the most many times in this field for the AAA games out there, but not for most games. In web or app development if you are using custom data structures instead of native, in most cases that is wrong. How about consistent data structures that have been built and tested outside the company? The thing is though when the programmer that makes your 5th string class and data structures moves on it will be rehashed by the next, as other developers won't be as effective with them and recreate. It is much more important to understand what data structures to use when and what impact they have on performance. Most of all can the developer ship and understand what is best for the product (not the ego or what will make them look like the hardest programmer of all time -- i.e. Rewriting the string class again and it is 10% faster, even though that is not a problem at all). I have seen some horrible, leaky, buggy data structures in situations like this, because they thought that was the job as led on by the interviewing. I have only really seen this while working in the game industry which I love but it is a problem with shipping product when this bike shedding happens over improvements to the game, engine or real custom needs i.e. the UI libs, event/messaging systems, naming/conventions are typically horrible in situations like this. I also blame consoles for many of these problems as the libs are so jacked, incomplete and old that performance becomes a huge issue and you have to have custom structures just to use the hardware right especially in graphics, physics + networking libs. Yet mobile I have seen less of this problem even though there is less hardware to work with. The next time you play a game and the networking totally sucks, or a game takes forever or simply doesn't ship, understand the culture of the company and the industry might have something to do with it.

kyllo 13y ago

Yeah, the funny thing about all the data structures & algorithms quizzes is that the simplest solution is usually a recursive one, and the big-O performance is sort of irrelevant because chances are you're using a language that doesn't have tail-call optimization and you're going to blow the stack frame for any large value of n anyway.

gizmo686 13y ago
Many recursive algorithms only require log(n) entries in the stack. Even if you do start overflowing the stack, it is simple to take a recursive implementation and turn it into an 'iterative' one, where you just manage the stack yourself.