YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 03-08 Splay Tree Example

03-08 Splay Tree Example

Get Embed Code
1 Language

Showing Revision 2 created 07/16/2014 by Udacity Robot.

  1. So here is what the splay tree code in an editor called Emaxx,
  2. and this is my personal editor of choice.
  3. It's doing syntax highlighting and indenting, very much likely Udacity online IDE would do for you.
  4. But here what I'm doing is running this on my local PC here.
  5. And so we can see is, we have a splay tree class, it's a port and insert method.
  6. The remove method, this takes a key out of the tree or couple of other operations.
  7. So insert, remove, and look out for the basic operations supported by any binary search tree,
  8. but many implementations support additional operations.
  9. So find the look out for operation for this tree.
  10. And then there's the splay operation and what the splay does is,
  11. it moves a particular key up to the root of the binary search tree up to the root of the splay tree.
  12. This serves as both the balancing operation for the splay tree and also the look up.
  13. So, the splay routine involves a couple of screenfuls of codes but it's still fairly simple.
  14. And now, let's look quickly at the test suite first.
  15. So the author of this open source splay tree for the test suite.
  16. In this test suite, you can see imports the Python module unit test
  17. And what unit test does is basically provides a little bit of infrastructure for running unit tests.
  18. And so, what it's going to do is automatically call these different functions,
  19. which are defined for an object inherited from the case test framework
  20. And you can see here, that what we do is for example,
  21. we have a setup routine that initializes a list of keys.
  22. We make ourselves a new splay tree and insert those 10 elements into the tree.
  23. We have a test insert function which loops over
  24. all of the elements of the tree and asserts that they're found.
  25. We have a remove test function which is going to be called last in our test suite.
  26. The functions beginning with a string TEST are called in alphabetical order,
  27. and this happens through the last one.
  28. This is going to remove all of the keys from the tree.
  29. Then finally, we have a function which is going to insert a large number of elements in the tree.
  30. It's going to insert 40,000 elements into the tree.
  31. It's going to make sure that they get staggered by a gap of 307.
  32. This is basically going to end up stress testing our splay tree a little bit.
  33. Finally, we have a routine that tests whether the tree correctly knows that it's empty.
  34. Okay, so this is our sort of minimal unit test.
  35. What we can do is, we can run this and this is going to take just a couple of seconds to run.
  36. Okay, so all of those tests took about 1.6 seconds to run
  37. and what I'm going to do now is run the same test under a code coverage string.
  38. So, I'm doing here is erasing code coverage date which has been previously stored in this directory.
  39. Running the splay test under the coverage framework
  40. which is basically going to run an instrument and version of the code
  41. and we'll talk about how this all works a little bit later and what it means,
  42. and then we're going to generate some HTML.
  43. So, what you can see is it ran quite a bit slower this time because
  44. instrumenting the code to measure a coverage
  45. has a lot of instructions to the code and this takes extra time.
  46. Okay, now we're going to look at the output.
  47. Here we are looking at the output of the code coverage tool
  48. and what it's telling us is that when we run the splay tree on it's own unit test,
  49. out of the 98 statements in the file, 89 of them got run, 9 of them failed to run,
  50. and we'll talk about this excluded business later.
  51. So, the language didn't get run are marked in red.
  52. And so this first one we're going to skip over for now and let's look at the second example.
  53. So, the second line that didn't get run is in the splay trees insert function,
  54. but what we can see is that the test suite failed to test the case
  55. where we inserted an element into the tree and it was already there.
  56. And if you look at this, this looks fairly harmless, we're just erroring out but we're not going to worry about this one right now.
  57. So, let's move on a little bit.
  58. So, here we got something a little bit more interesting.
  59. So here we're in the splay tree's removing function.
  60. So, we're going to remove an element from the tree.
  61. And so what you can see is that the first thing this function does is,
  62. splays the tree based on the key to be removed,
  63. and so this is intended to draw that key up to the root note of the tree.
  64. If the root note of the tree does not have the key that we're looking for,
  65. then we're going to raise an exemption saying that this key wasn't found.
  66. But the thing's noticed here is that this wasn't tested.
  67. If we look below here and go on to the body of the delete function,
  68. we see a pretty significant chunk of code that wasn't tested, probably want to go back and revisit this.
  69. And so, let's take a step back and think about what coverage tool is telling us here.
  70. It's basically showing us what we didn't think to test with the unit test that we wrote so far.
  71. So, what we're going to do is go ahead and fix the unit test a little bit in order to test this case.
  72. In order to test the case of removing an element from the tree where it's not there,
  73. so let's go ahead and do that.