Skip to content

Files

Latest commit

 

History

History

empty

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

구현

./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