cache의 data structure에 따른 성능 차이 #418
Answered
by
HC-kang
highballplz
asked this question in
도움요청
-
decode-ways 문제를 복습하는 과정에서 질문이 있어 드립니다. 코드 1과 2를 보시면 알고리즘은 dfs로 같고, cache를 map으로 뒀는지(1) array로 뒀는지(2)에서만 차이가 있습니다. 그런데 leetcode를 돌려보면 1은 40 ~ 50ms 근방으로 나오고, 2는 70 ~ 80ms가 나와 두 배까지 차이가 납니다. map이든 array든 read와 write는 O(1)인데 왜 이런 결과가 나오는지 궁금합니다. 그리고 저는 map이 dynamic하게 hashing해가면서 저장하고 읽어오기 때문에 1이 오히려 더 오래 걸릴 거라고 생각했습니다. 감사합니다 ^^ (1)
(2)
|
Beta Was this translation helpful? Give feedback.
Answered by
HC-kang
Sep 4, 2024
Replies: 1 comment 1 reply
-
@highballplz 안녕하세요 하이볼님! 위쪽 함수의 경우 위의 경우 값이 0인 경우에도 해당 값을 재활용하지만, 아래의 경우에는 |
Beta Was this translation helpful? Give feedback.
1 reply
Answer selected by
highballplz
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@highballplz 안녕하세요 하이볼님!
제 생각에는 두 함수의 로직에 차이가 있어보입니다.
위쪽 함수의 경우
if (cache.has(i)) return cache.get(i);
를 사용하고아래쪽 함수의 경우
if (cache[i]) return cache[i];
를 사용하는데,위의 경우 값이 0인 경우에도 해당 값을 재활용하지만, 아래의 경우에는
cache[i] = 0
인 경우, false 처리되어 메모를 활용하지 못하고 다시 계산을 하게되는것으로 보입니다.해당 내용 수정해서 테스트 결과 4~50ms정도로 유사하게 나오네요!