경험적 알고리즘

Empirical algorithmics

컴퓨터 과학에서 경험적 알고리즘(또는 실험적 알고리즘)은 경험적 방법을 사용하여 알고리즘의 동작을 연구하는 관행이다. 알고리즘 개발과 실험을 결합한 실천요강: 알고리즘은 단순히 설계되었을 뿐만 아니라 다양한 상황에서 구현되고 시험된다. 이 프로세스에서 알고리즘의 초기 설계를 분석하여 알고리즘이 단계적 방식으로 개발될 수 있도록 한다.[1]

개요

경험적 알고리즘의 방법은 알고리즘 분석을 위한 이론적 방법을 보완한다.[2] 특히 통계로부터 경험적 방법의 원칙적인 적용을 통해 이론적 분석이 불가능한 (현재) 하드 결합 문제에 대한 고성능 휴리스틱 알고리즘과 같은 알고리즘의 행동에 대한 통찰력을 얻을 수 있는 경우가 많다.[3] 또한 경험적 방법은 알고리즘 효율성의 상당한 개선을 달성하는 데 사용될 수 있다.[4]

미국의 컴퓨터 과학자인 캐서린 맥거치는 경험적 알고리즘의 두 가지 주요 분과를 파악하는데, 첫 번째(경험적 분석이라고 함)는 알고리즘의 동작에 대한 분석과 특성화를 다루고, 두 번째(알고리즘 설계 또는 알고리즘 엔지니어링이라고 함)는 알고리즘의 성능 향상을 위한 경험적 방법에 초점을 맞추고 있다. 알고리즘.[5] 전자는 종종 통계에서 나오는 기법과 도구에 의존하는 반면 후자는 통계, 기계 학습 및 최적화의 접근법에 기초한다. 동적 분석 도구는 일반적으로 성능 프로파일러로서 다양한 맥락에서 사용할 수 있도록 다양한 유형의 알고리즘의 선택과 정교화를 위한 경험적 방법을 적용할 때 사용된다.[6][7][8]

경험적 알고리즘에 관한 연구는 ACM Journal on Experimental Alogramics(JEA)와 JAIR(Journal of Infrastructive Intelligence Research) 등 여러 학술지에 게재된다. 캐서린 맥거치 외에도 경험적 알고리즘 분야에서 잘 알려진 연구자들로는 베르나르 모어트, 주세페 F가 있다. 이탈리아어, 홀거 H. Hohs, David S. Johnson, Roberto Battiti.[9]

복잡한 알고리즘 설계에서의 성능 프로파일링

경험적 알고리즘이 없는 경우, 알고리즘의 복잡성 분석은 알고리즘을 사용할 수 있는 다양한 상황에 적용할 수 있는 다양한 이론적 방법을 포함할 수 있다.[10] 메모리 및 캐시 고려사항은 종종 주어진 목적을 위해 복잡한 알고리즘의 이론적 선택 또는 최적화 접근법에서 고려해야 할 중요한 요소들이다.[11][12] 성능 프로파일링은 일반적으로 전체 응용프로그램 코드의[13][14][15] 병목현상을 찾아 분석하거나 전체 응용프로그램을 분석하여 성능이 떨어지는 코드를 식별하는 데 사용되는 동적 프로그램 분석 기법이다.[16] 프로파일러는 응용 프로그램의 성능 문제와 가장 관련 있는 코드를 밝힐 수 있다.[17]

프로파일러는 특정 상황에서 한 알고리즘을 다른 알고리즘보다 선택할 시기를 결정하는 데 도움이 될 수 있다.[18] 복잡성 분석과 마찬가지로 개별 알고리즘이 프로파일링될 때, 메모리 및 캐시 고려사항은 명령 수나 클럭 주기보다 종종 더 중요하다. 그러나 프로파일러의 발견은 알고리즘이 사용하는 명령의 수보다는 데이터에 액세스하는 방법에 비추어 고려할 수 있다.[19]

프로파일링은 성능 결과를 시각적 표현으로 공개함으로써 알고리즘의 행동에[20] 대한 직관적인 통찰력을 제공할 수 있다.[21] 예를 들어 와일드카드를 매칭하는 알고리즘을 개발하는 동안 성능 프로파일링이 적용되었다. 리치 살츠의 와일드매트 알고리즘과 같은 와일드카드를 매칭하기 위한 초기 알고리즘은 일반적으로 재귀에 의존했는데,[22] 이 기술은 성능을 이유로 비판받았다.[23] 와일드카드와 일치하는 Krauss 알고리즘은 성능 프로파일링을 통해 제안된 최적화에 이어 테스트 사례를[24] 사용하여 비재발적 대안을 수립하려는 시도에 기초하여 개발되었으며,[25] 다른 고려사항과 함께 프로파일링을 고려하여 고안된 새로운 알고리즘 전략이 도출되었다.[26] 기본 블록[27] 수준에서 데이터를 수집하거나 하드웨어 지원에[28] 의존하는 프로파일러는 소프트웨어 개발자가 특정 컴퓨터 또는 상황에 대한 알고리즘을 최적화하는 데 도움을 줄 수 있을 정도로 정확한 결과를 제공한다.[29] 성능 프로파일링은 개발자가 임의의 시험 기반 문제에 적용되는 공진화 알고리즘과 같이 복잡한 상황에서 적용되는 복잡한 알고리즘의 특성을 이해하는 데 도움을 줄 수 있으며, 설계 개선으로 이어질 수 있다.[30]

참고 항목

참조

  1. ^ Fleischer, Rudolf; et al., eds. (2002). Experimental Algorithmics, From Algorithm Design to Robust and Efficient Software. Springer International Publishing AG.
  2. ^ Moret, Bernard M. E. (1999). Towards A Discipline Of Experimental Algorithmics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Vol. 59. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. pp. 197–213. doi:10.1090/dimacs/059/10. ISBN 9780821828922. S2CID 2221596.
  3. ^ Hromkovic, Juraj (2004). Algorithmics for Hard Problems. Springer International Publishing AG.
  4. ^ Guzman, John Paul; Limoanco, Teresita (2017). "An Empirical Approach to Algorithm Analysis Resulting in Approximations to Big Theta Time Complexity" (PDF). Journal of Software. 12 (12).
  5. ^ McGeoch, Catherine (2012). A Guide to Experimental Algorithmics. Cambridge University Press. ISBN 978-1-107-00173-2.
  6. ^ Coppa, Emilio; Demetrescu, Camil; Finocchi, Irene (2014). "Input-Sensitive Profiling". IEEE Transactions on Software Engineering. 40 (12): 1185–1205. doi:10.1109/TSE.2014.2339825.
  7. ^ Moret, Bernard M. E.; Bader, David A.; Warnow, Tandy (2002). "High-Performance Algorithm Engineering for Computational Phylogenetics" (PDF). The Journal of Supercomputing. 22 (1): 99–111. doi:10.1023/a:1014362705613.
  8. ^ Zaparanuks, Dmitrijs; Hauswirth, Matthias (2012). Algorithmic Profiling. 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM Digital Library. pp. 67–76. CiteSeerX 10.1.1.459.4913.
  9. ^ "On experimental algorithmics: an interview with Catherine McGeoch and Bernard Moret". Ubiquity. ACM Digital Library. 2011 (August). 2011.
  10. ^ Grzegorz, Mirek (2018). "Big-O Ambiguity". performant code_.
  11. ^ Kölker, Jonas (2009). "When does Big-O notation fail?". Stack Overflow.
  12. ^ Lemire, Daniel (2013). "Big-O notation and real-world performance". WordPress.
  13. ^ "Finding Application Bottlenecks". dotTrace 2018.1 Help. JetBrains. 2018.
  14. ^ Shmeltzer, Shay (2005). "Locating Bottlenecks in Your Code with the Event Profiler". Oracle Technology Network JDeveloper documentation. Oracle Corp.
  15. ^ Shen, Du; Poshyvanyk, Denys; Luo, Qi; Grechanik, Mark (2015). "Automating performance bottleneck detection using search-based application profiling" (PDF). ISSTA 2015 Proceedings of the 2015 International Symposium on Software Testing and Analysis. ACM Digital Library: 270–281. doi:10.1145/2771783.2771816. ISBN 9781450336208.
  16. ^ "Performance & Memory Profiling and Code Coverage". The Profile Learning Center. SmartBear Software. 2018.
  17. ^ Janssen, Thorben (2017). "11 Simple Java Performance Tuning Tips". Stackify Developer Tips, Tricks and Resources.
  18. ^ O'Sullivan, Bryan; Stewart, Don; Goerzen, John (2008). "25. Profiling and optimization". Real World Haskell. O'Reilly Media.
  19. ^ Linden, Doug (2007). "Profiling and Optimization". Second Life Wiki.
  20. ^ Pattis, Richard E. (2007). "Analysis of Algorithms, Advanced Programming/Practicum, 15-200". School of Computer Science, Carnegie Mellon University.
  21. ^ Wickham, Hadley (2014). "Optimising code". Advanced R. Chapman and Hall/CRC.
  22. ^ Salz, Rich (1991). "wildmat.c". GitHub.
  23. ^ Cantatore, Alessandro (2003). "Wildcard matching algorithms".
  24. ^ Krauss, Kirk (2008). "Matching Wildcards: An Algorithm". Dr. Dobb's Journal.
  25. ^ Krauss, Kirk (2014). "Matching Wildcards: An Empirical Way to Tame an Algorithm". Dr. Dobb's Journal.
  26. ^ Krauss, Kirk (2018). "Matching Wildcards: An Improved Algorithm for Big Data". Develop for Performance.
  27. ^ Grehan, Rick (2005). "Code Profilers: Choosing a Tool for Analyzing Performance" (PDF). Freescale Semiconductor. 반면에, 만약 당신이 당신의 코드를 미세하게 정확하게, 개별적인 기계 지시를 미세하게 조정해야 한다면, 사이클 카운팅을 가진 능동 프로파일러는 이길 수 없다.
  28. ^ Hough, Richard; et al. (2006). "Cycle-Accurate Microarchitecture Performance Evaluation". Proceedings of Workshop on Introspective Architecture. Georgia Institute of Technology. CiteSeerX 10.1.1.395.9306.
  29. ^ Khamparia, Aditya; Banu, Saira (2013). Program Analysis with Dynamic Instrumentation Pin and Performance Tools. IEEE International conference on Emerging trends in Computing, Communication and Nanotechnology. IEEE Xplore Digital Library.
  30. ^ Jaskowski, Wojciech; Liskowski, Pawel; Szubert, Marcin Grzegorz; Krawiec, Krzysztof (2016). "The performance profile: A multi-criteria performance evaluation method for test-based problems" (PDF). Applied Mathematics and Computer Science. De Gruyter. 26: 216.