[Java] Iterator의 속도

Question

안녕하세요. 궁금증이 생겨 고수님들의 의견을 듣고 싶어 질문 올립니다.제가 BFS 알고리즘을 사용한 코딩테스트 문제를 풀 때 생긴 문제로, Queue에서 for문을 써서 문제를 풀려고 시도했는데, 계속 시간 초과가 떠서 foreach 문으로 수정하였더니 풀린 문제입니다.기존 코드(시간 초과)는 아래와 같습니다. 참고로 리스트 배열을 사용하였습니다.for(int i&#61;0; i<graph[now].size(); i&#43;&#43;) {int next &#61; graph[now].get(i); if(!v[next]) {q.add(next);cnt&#43;&#43;;v[next] &#61; true;}}아래는 변경된(해결) 코드입니다.for(int next : graph[now]) {if(v[next]) continue;q.offer(next);&#43;&#43;cnt;v[next] &#61; true;}foreach의 성능상 이점이 있을거라 생각하고 찾아보는데 https://siyoon210.tistory.com/99 에서 LinkedList를 사용할 때는 내부적으로 iterator를 사용하기 때문에 속도에서 for < foreach 라는 블로그분의 말씀이 있었습니다.iterator에 대해 찾아보는 데 다른 블로그분은 https://3colored.tistory.com/5 for > iterator 라는 분이 있으시네요.결론적으로 궁금증들은 다음과 같습니다.foreach가 for문보다 빠른 게 맞나요?foreach &#61;&#61; iterator 라고 가정한 제가 잘못한건가요?아니면 이 모든 문제가 아닌 다른 문제인가요?읽어주셔서 감사드리고 답변 부탁드리겠습니다!!

JethroHolic · Accepted Answer

다 알지는 못해, 답변 할 수 있는 부분만 답변하면...foreach의 성능상 이점이 있을거라 생각하고 찾아보는데 https://siyoon210.tistory.com/99 에서 LinkedList를 사용할 때는 내부적으로 iterator를 사용하기 때문에 속도에서 for < foreach 라는 블로그분의 말씀이 있었습니다.Linked List에서는 for문 내에서 get할 때 매번 head에서 부터 해당 index에 이르기까지 계속 next를 타고 가기 때문에 당연하게 느린게.. 정상입니다. Iterator는 내부적으로 현재 위치를 기억하고 있어서 next/previous가 불리었을때 head에서부터 출발 안 하고 바로 인접한 노드로 가서 빠른게 정상입니다. 해당 결과는 Linked List를 신중히 사용해야하는 걸 보여주는 거지, 일반적으로 'for < foreach'이다. 라는 결과를 보여주는 것 같지는 않네요.. (덧붙여서 PS에선 왠만해선.. Linked List가 필요한 경우가 아니라, 그냥 List만 필요할 땐 ArrayList를 사용하는게 더 좋을 꺼에요.)근데 일반적으로 foreach보다는 그냥 for문이 더 빠를꺼에요. (그렇게 추정하는건 아래 적을게요)https://imgur.com/a/oJi1SYZ간단한 코드와, 이를 디컴파일 했을 때의 결과인데 (컴파일러마다 최적화가 달라서 디컴파일 결과는 사람마다 다를 순 있어요)foreach == iterator 라고 가정한 제가 잘못한건가요?Collection에서 foreach를 iterator로 구현해야한다.라는 jvm 규약이 있는 지는 배움이 짧아 모르겠지만, 사용해보았을 때 collection에선 iterator로 최적화해주더라고요. 음... 그리고 정상적인 사용에서 foreach보다 for문이 더 빠른건, arraylist에서 get을 보면 범위 내인지 확인하고 단순히 내부에 있는 동적 배열에서 해당 index를 꺼내주는데, iterator의 next는 iterator 내에 저장되어 있는 cursor 가지고 오고, 그 위치가 유효한 범위 내인지 확인하고 커서 옮기고 반환하는데 저런 부가적인 코드가 존재해서 조금 느릴 수 밖에 없을 꺼에요.. (근데 iterator 한번 편하게 쓰기 시작하면, 너무 편해져서...)반면 linked list는 get은 매번 head/tail에서부터 해당 index를 찾아가는데, https://imgur.com/a/xuZ9AeA iterator에서는 단순하게 다음이 있는 지만 보고 넘겨주면 되서 iterator 방식이 더 빠를 수 밖에 없습니다.Linked List는 foreach 문이 아니더라도, 특정 위치의 값이 필요한게 아니라 구간의 값들이 필요하면(연속적으로 데이터를 봐야한다던가하면...) iterator 쓰는게 훨씬 좋아요.

캐티 · Answer

위의 코드는 .size() 계산을 반복적으로 수행하기 때문에 최종 수량이 변동되지 않는 경우에 캐싱 하는 편이 좋으며 변동이 있다면 foreach가 적절합니다.

[Java] Iterator의 속도

2개의 답변

Q&A 목록