자 간단한게, x의 값이 소수인지 판별하는 함수인지 판별하는 함수를 만들어 보자.
const isPrime = (num) => {
let count = 0
for(let i = 2; i <= num; i++) {
console.log('tested')
if(num % i === 0) count++
if(count > 1) return false
}
return count === 1
}
1을 제외하고 나누어서 나머지가 0이 되는 것이 자기 자신 인 경우만 해당하는 것이 소수의 정의이기 때문에, 간단하게 구현해보면 위와 같은 형태로 만들 수 있을 것이다.
자 여기서 생각해보자, 2357이라는 숫자가 소수인것을 판단하기위해 몇번의 연산을 진행할까?
당연하게도 소수이기 때문에, 소수인 경우 판단하고자 하는 숫자의 -1 회 만큼 연산을 진행하게 된다. 그러면 또 한번 수행하게되면 어떨까?너무나도 자명하게 2356 * 2회 만큼 연산을 수행 하였다. 이미 판별한 값임에도 말이다.
이 불합리함을 없애보도록 하자!
const memo = new Map()
const isPrime = (num) => {
if(memo.has(num)) {
console.log('from memo')
return memo.get(num)
}
let count = 0
for(let i = 2; i <= num; i++) {
console.log('tested')
if(num % i === 0) count++
if(count > 1) break
}
const res = count === 1
memo.set(num, res)
return res
}
함수의 결과를 리턴하기전에, 저장해두고, 함수 첫 실행 시 이미 수행 했었는지를 확인해보는 코드로 수정하였다. 아주 간단하게 최적화 할 수 있다.
그리고 효과는 대단했다. :)
댓글
댓글 쓰기