Skip to content

Files

Latest commit

Apr 15, 2025
563eabc · Apr 15, 2025

History

History

regexp

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Jun 8, 2023
Jun 8, 2023
Jun 8, 2023
Apr 15, 2025
Jun 8, 2023
Jun 8, 2023

README.md

정규식

목표

OCaml 에서 정규식을 효율적으로 다루면서 성능을 최적화 할 수 있어야 한다.

구현

./regex [길이]를 실행하면 먼저 해당 개수만큼 무작위 정수를 원소를 갖는 List 타입의 값을 생성한 후, 각 숫자를 문자열 형태로 바꾼다. 그리고 난 후 각 문자열 중 특정한 정규식(".*9.9.")을 만족하는 원소만 골라내는 코드가 구현되어 있다.

OCaml에서 정규식은 Str.regexp 함수를 사용하여 만든다. 하지만 많이 반복 생성하는 경우 매우 비효율적이다.

이를 해결하기 위하여, 효율적으로 정규식을 이용하는 filter_opt 함수를 작성하라. 이 모듈은 ./regexp -opt [길이]로 실행할 수 있다.

규칙

  • 반복문은 재귀 호출로 구현하고 for 문을 사용하지 않는다.
  • 원소 천만 개를 생성하고 검사하는 데 5초를 넘지 않아야 한다. 참고로, Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz 에서 아래와 비슷한 성능이 나온다.
$ time ./regexp 10000000
1496356
./regex 10000000  21.35s user 0.41s system 99% cpu 21.759 total
$ time ./regexp -opt 1000000
1496356
./regex 10000000 -opt  3.50s user 0.33s system 99% cpu 3.835 total