English 字幕

← Bitwise Implementation - Software Testing



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

  1. All of that was just introducing these two functions, and so the deal is,
  2. is this really easy to write straightforward code for this?
  3. Let's take a quick look. So, here's highcommonbits.
  4. All we're going to do is walk through the bits in the input here. I'm assuming a 64-bit input.
  5. We're going to walk through the input, reversed, so from 63 to 0.
  6. And every time we see 2 bits being the same in a and b, we copy that bits to the output.
  7. As soon as we see 2 bits at the same position that are different in a and b,
  8. we set that bit position in the output and return it, and lowcommonbits are just the same.
  9. The only thing that is different is we looped from 0 to 63 instead of 63 to 0,
  10. but we do exactly the same thing we're copying bits in the output
  11. as long as they are common between a and b.
  12. And as soon as we see a difference, setting the bit and return it.
  13. What we have here is a really slow implementation.
  14. Even if we translate this implementation straightforwardly to see,
  15. it's still going to be really slow compared to optimized implementation.
  16. Optimized implementations of this are going to be potentially more complicated
  17. and potentially harder to get it right, but it might execute in just a handful of clock cycles
  18. as opposed to maybe a hundred clock cycles for the optimized C versions
  19. and probably thousands of clock cycles for the Python.
  20. Of course, performances are really going to be our concern here.
  21. We're just using this to illustrate initially that comes up and extremely optimize chart codes.
  22. The factor we're trying so hard to optimize these codes means
  23. we're going to have some concerns about whether they are correct or not.
  24. Let's talk about how we're going to deal with that.
  25. What we're probably going to do is write a random tester.
  26. The reason we're going to write a random tester is with 64-bit inputs,
  27. the input demand for either of these functions is going to contain
  28. 220 elements so it's far too big, too exhaustible test.
  29. We're going to be forced to do some sort of either systematic testing or random testing.
  30. There's is no way out of partial testing of these functions.
  31. The most obvious kind of random tester array
  32. would be make a random 64-bit integer, make another one.
  33. Now assert that our super super optimized highcommonbits function called with a and b
  34. returned the same results as a reference implementation
  35. that showed through Python version but sort of simple incredibly obvious code
  36. and maybe reference implementation at C, it doesn't really matter.
  37. We're just going to randomly test all sorts of configuration of the function.
  38. The question we're going to ask is, is this a good random tester?
  39. And what we might do is run the code coverage tool so let's go ahead and do that.