regexp

정규식

목표

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