Empirical Evaluation of Algorithms

알고리즘 스터디 중 기억하면 좋을 내용을 블로깅 해봅니다.

실제 개발시에 complexity를 고려하는 tip 입니다.

책은 Python algorithms(Magnus Lie Hetland) 입니다.

• Empirical Evaluation of Algorithms(Practical Tips)
  • Tip1 : If possible, don't worry about it.
    
    • 먼저 구현해보고, 알고리즘이 적당한지 확인해라.

  • Tip2 : For timing things, use timeit.

    Python 2.7.5 (default, Mar  9 2014, 22:15:05) [GCC 4.2.1 Compatible Apple LLVM 5.0 (clang-500.0.68)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> import timeit >>> timeit.timeit("x = 2 + 2") 0.028252840042114258 >>> timeit.timeit("x = 2 + 2") 0.030072927474975586   /* time a function */ python -m timeit -s"import mymodule as m" "m.myfunction()"

  • Tip3 : To find bottlenecks, use a profiler.

    import cProfile cProfile.run("main()")

  • Tip4 : Plot your results.
    
    • matplotlib: http://matplotlib.org/
  • Tip5 : Be careful when drawing conclusions based on timing comparisons.
    • 다른 임의적인 변수대신, 여러번 시간 측정을 통해 더 나은 구현을 선택하면 된다.
  • Tip6 : Be careful when drawing conclusions about asymptotics from experiments.
    • 여러번의 실험을 통해 asymptotics이 맞는지 검증하라.