English subtitles

← Sally Goldman - Design of Computer Programs

Get Embed Code
2 Languages

Showing Revision 2 created 05/24/2016 by Udacity Robot.

  1. Hey, welcome back.
  2. I'm very happy to be here today with Sally Goldman.
  3. Sally is a professor at Washington University and is also a researcher at Google.
  4. We'd like to talk mostly about the process of choosing the right algorithm and data structure
  5. and how your programs are so much tied to that choice.
  6. [Sally Goldman, Professor, Washington Univ.]The big picture, I think, in terms of what we focused in the book
  7. is if I'm looking at a data structure for a problem, there are broad classes of data structures.
  8. Some data structures are very good just searching something with a unique ID.
  9. Other things may be good at finding--like I want to find if the word CAT, that substring,
  10. is part of a word, and so there's this broad class of data structures.
  11. Really, the encapsulation is as important as to understand these abstract data types or ADTs
  12. and understand which one of those fits your problem,
  13. because that is a fundamental decision, and there is fewer of them so it's easier.
  14. First of all, an invariant is something typically about your data that holds all the time.
  15. If I have something called search_tree, I may say that if I'm at a certain node
  16. everything on the left half is smaller and everything on the right half is bigger.
  17. Again, I think it helps just in understand and designing the data structure
  18. to remember the this is an important thing and I need to make sure that all the methods
  19. and all the operations I do preserve this.
  20. In that particular case, it allows me to search quickly.
  21. Without that invariant, I'd lose it, but at the same time it lets you formally prove correctness.
  22. It's a pretty good dual.
  23. I think it helps you reason about it informally and let's you formally, in fact, prove
  24. that you haven't forgotten any cases.
  25. How do you know you have the right answer?
  26. Certainly it's good to prove you're always going to have the right answer,
  27. but that proof is about the technique that you created.
  28. It doesn't say that your code is right.
  29. I think you actually want to prove rather informally at least that you're going
  30. to always have the right answer, but you need tests.
  31. Without unit tests bug will creep in.
  32. The book we wrote we have a couple thousand unit tests,
  33. and I'll tell you there are times in the end I'm like, oh, I can make this a little simpler.
  34. I didn't need this case, and all the unit tests start going red.
  35. Then I'd put a sentence about why you needed it.
  36. I think you actually need testing in the code to make sure the code actually
  37. really implemented what you intended and testing at the algorithmic level.
  38. Looking at the difference in dealing with algorithmic complexity,
  39. making sure you actually cover all the cases of the input,
  40. and dealing with the complexity of the code and different operating systems, different windows.
  41. Yeah, it's tricky and also everyone wants to try out different things,
  42. and so you have these different variations and the code gets a lot of cruft built into it
  43. that kind of can get it out of hand.
  44. I think that industry code is also important to keep that in check.
  45. What makes for good code?
  46. Clean--it should be fairly modular. You don't want the two-page method.
  47. You definitely want to make sure that commonly used blocks are reused
  48. and have some documentation on the methods whether in a separate file
  49. like if it's a C++ with an H file or something where it's all together.
  50. You definitely want to really say what the method is doing.
  51. In the end good code is code that other people can come and change and adapt.