공집합

목표

OCaml 에서 빈 자료구조(빈 리스트나 공집합 등)을 효율적으로 다루면서 성능을 최적화 할 수 있어야 한다.

구현

./empty [길이]를 실행하면 먼저 해당 개수만큼 정수 리스트를 원소를 갖는 List 타입의 값을 생성한다. 각 원소는 빈 리스트, 혹은 원소 10000 개짜리 리스트 중 무작위로 선택된다. 그리고 나서, 모든 원소 중 빈 리스트의 개수가 몇개 인지를 세는 코드가 이미 구현되어 있다.

OCaml에서 빈 리스트인지를 검사하는 원시적인 방법은 해당 리스트의 길이가 0인지 검사하는 것이다. 하지만 이는 저수준 사고방식이며 원소 개수가 많을 때 매우 비효율적이다.

이를 해결하기 위하여, 리스트의 각 원소 중 빈 리스트의 개수를 세는 empty_opt 함수를 효율적으로 작성하라. 이 모듈은 ./empty -opt [길이]로 실행할 수 있다.

규칙

• 순환문은 재귀 호출로 구현하고 for 문을 사용하지 않는다.
• 천만개 원소를 생성하고 처리하는 데 수 초를 넘지 않아야 한다. 참고로, Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz 에서 아래와 비슷한 성능이 나온다.

$ time ./empty 10000000
4999630
./empty 10000000  67.36s user 0.59s system 99% cpu 1:07.95 total
$ time ./empty -opt 10000000
4999630
./empty 10000000 -opt  1.41s user 0.18s system 99% cpu 1.589 total