코테 공부중인데 시간이 이렇게 많이 차이나는 이유가 궁금합니다

Question

언어는 Java구요 두 ArrayList<String>의 요소들을 비교해서 일치하면 체크 후 횟수를 계산하는 코드인데첫번째 방법으로 테스트할떈 15.79ms의 시간이 걸리던게두번째 방법으로 할땐 1.89ms까지 줄어들더라구요근데 왜이렇게까지 극적으로 개선이되는지 잘 이해가 되지않아 궁금해서 질문합니다고수님들 알려주세요 ㅠㅠ//수정 전 for(int i &#61; 0; i < list1.size(); i&#43;&#43;){ for(int j &#61; 0; j < list2.size(); j&#43;&#43;){ if(list1.get(i).equals(list2.get(j))){ count&#43;&#43;; list2.set(j, &#34;a&#34;); break; } } } //수정 후 for(int i &#61; 0; i < list1.size(); i&#43;&#43;){ String target &#61; list1.get(i); if(list2.remove(target)){ count&#43;&#43;; } }

Clickin · Answer

ms 단위의 시간에서 10배 차이는 그리 극적이진 않긴 한데요. 차이가 날만한 부분이라면 set부분에 있습니다.일단 openjdk 소스코드 원본을 먼저 보고오실 필요가 있는데요. 링크 참조해보세요https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/ArrayList.java#L472public E set(int index, E element) { Objects.checkIndex(index, size); E oldValue &#61; elementData(index); // (E) elementData[index] 를 호출 elementData[index] &#61; element; return oldValue; }elementData 호출하는 부분에서 형변환이 일어나는데 이게 문제되는 이유를 차근차근 알아봅시다.1. 자바의 캐스팅 오버헤드먼저 자바의 캐스팅 오버헤드에 대해서 알아봅시다.자바에는 크게봐서 두가지 형변환이 있습니다. 업캐스팅이랑 다운캐스팅이죠.업캐스팅은 크게 오버헤드랄 게 없습니다. 부모 타입이 되기 위해 필요한 정보는 자식 타입이 다 가지고 있으니까요.다운캐스팅은 해당 오브젝트가 자식 타입이 되기 위한 모든 정보를 다 가지고 있는지 검사하고 만약 불충분하다면 ClassCastException 에러를 띄워야합니다. 이건 JVM 내부에서 작동하기 때문에 눈에는 보이지 않지만 모든 필드와 가상함수 테이블을 검사해야하다보니 꽤 비싼 작업이죠.2. 컬렉션 프레임워크 내부 동작작성자님이 작성하신 소스코드상에서는 String이겠지만 자바의 제네릭 구현 특성상 런타임에는 타입이 지워지고 Object로 저장됩니다. 이걸 컬렉션 프레임워크 내부에서 바깥으로 내보낼 때 타입 캐스팅하면서 사용합니다.즉 콜렉션 프레임워크 내부에서 객체를 가져오려면 반드시 다운캐스팅이 발생한다는 겁니다.ArrayList::set 은 ArrayList::add 와 다르게 집어넣은 object를 반환합니다. 이 과정에서 다운캐스팅이 발생하고 이건 한눈에 소스코드만 보고서 빅-O 계산법에 포함시키기 어려운 런타임 오버헤드를 유발합니다.3. 어떻게 해야하는가?실무에서는 컬렉션 프레임워크를 더 자주 사용함에도 불구하고 코딩테스트 책이나 강의들을 보면 다들 순수한 배열을 쓰고있는 이유가 다 있습니다. 저런 런타임 오버헤드가 아까운거죠.코딩테스트에서는 C 계열 언어들을 배려하기 위해서 반드시 입력 데이터 크기가 특정되기 때문에 특별한 사유가 있는 게 아니라면 웬만해서는 그냥 배열을 씁시다.

공지사항 · Answer

수정후는 발견하면 지우고 다음으로 넘어가잖아요 수정전은 무조건 전부다 돌잖아요 그래서 시간복잡도의 최선,최악,평균을 알면 좋습니다. remove연산의 경우 최선의 경우: O(n) (모든 요소가 list2의 앞쪽에 있을 때)최악의 경우: O(n^2) (모든 요소가 list2의 뒤쪽에 있거나 없을 때)평균적인 경우: O(n^2)에 가까움 인 반면, 수정전 코드는 무조건 O(n^2)이기 때문에 수정후가 더 좋을수밖에 없습니다 그런데 remove 특성상 요소가 앞으로 이동하는 작업이 있기 때문에 요소가 커지면 커질수록 성능이 오히려 저하될 수 있습니다.

Clickin · Answer

대충 테스트 코드 작성해봤는데 15ms 나오시는거 보면 n이 작아보이네요. 이런 경우에는 사실 O(n)이나 O(n^2)나 별 차이가 나지 않을 수 있습니다.원본 테스트 데이터가 없어서 확실하진 않은데 형변환으로 인한 문제인지 확인하려면 다음과 같이 작성하면 됩니다. 한번 동일한 환경에서 테스트해보세요.// 수정 전을 수정. set(j, "a")는 remove(j)와 add(j, "a")로 동일한 결과가 나옴. for(int i = 0; i < list1.size(); i++){ for(int j = 0; j < list2.size(); j++){ if(list1.get(i).equals(list2.get(j))){ count++; //list2.set(j, "a"); list2.remove(j); list2.add(j, "a"); break; } } }제가 테스트 데이터 만들어서 해본 결과는 10배 차이까진 안나네요. 테스트 코드입니다.class Scratch { public static void main(String[] args) { List orglist1 = generateArr(1000); List orglist2 = generateArr(1000); List list1 = new ArrayList<>(orglist1); List list2 = new ArrayList<>(orglist2); int count = 0; long start, end; start = System.nanoTime(); //수정 전 for(int i = 0; i < list1.size(); i++){ for(int j = 0; j < list2.size(); j++){ if(list1.get(i).equals(list2.get(j))){ count++; list2.remove(j); list2.add(j, "a"); break; } } } end = System.nanoTime(); System.out.println((end - start) / 1000000); //수정 후 list1 = new ArrayList<>(orglist1); list2 = new ArrayList<>(orglist2); start = System.nanoTime(); for(int i = 0; i < list1.size(); i++){ String target = list1.get(i); if(list2.remove(target)){ count++; } } end = System.nanoTime(); System.out.println((end - start) / 1000000); } public static List generateArr(int size) { List retArr = new ArrayList<>(size); Random random = new Random(); for (int index = 0; index < size; index++) { int leftLimit = 98; // numeral 'b' int rightLimit = 122; // letter 'z' int targetStringLength = 10; String generatedString = random.ints(leftLimit, rightLimit + 1) .filter(i -> (i <= 57 || i >= 65) && (i <= 90 || i >= 97)) .limit(targetStringLength) .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append) .toString(); retArr.add(generatedString); } return retArr; } }

코테 공부중인데 시간이 이렇게 많이 차이나는 이유가 궁금합니다

3개의 답변

Q&A 목록