글 읽기 - (자바) 객체 배열 보다 리스트가 더 빠른 이유가 궁금합니다

wwad 2년 전 0

자바 내장함수를 따라 들어가 보니

Arrays.sort는 기본타입일 경우 듀얼피벗

객체일 경우 팀소트나 머지소트를 사용하여 정렬하고

Collections.sort 는 리스트롤 배열로 변환 후

Arrays.sort를 호출 해서 팀소트나 머지소트를 사용하여 정렬하고

다시 배열을 리스트로 변환합니다

객체일 경우 데이터 삽입이나 정렬 둘 다 리스트가 배열보다 빠를 이유가 전혀 없어 보이는데도

리스트를 사용한 코드가 배열을 사용한 코드보다 약 1000 ms 더 빠릅니다

어떤 부분에서 이런 차이가 발생 하는지 궁금합니다

//리스트 사용 약 1500 ms

import java.util.*;
import java.io.*;

class Main {

	static class Node {
		int s,e;
		public Node(int s, int e) {
			this.s = s;
			this.e = e;
		}
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		List<Node> list = new ArrayList<>();
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			list.add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
		}
		Collections.sort(list, (a,b) -> a.s-b.s);
        int s = -(int)1e9, e = -(int)1e9, ans = 0;
		for(Node cur : list) {
			if(cur.s > e) {
				ans += e-s;
				s = cur.s;
				e = cur.e;
			}else e = Math.max(e, cur.e);
		}
		System.out.println(ans+e-s);
	}
}

//객체배열 사용 약 2700 ms

import java.util.*;
import java.io.*;

class Main {

	static class Node {
		int s,e;
		public Node(int s, int e) {
			this.s = s;
			this.e = e;
		}
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		Node node[] = new Node[n];
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			node[i] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		Arrays.sort(node, (a,b) -> a.s-b.s);
        int s = -(int)1e9, e = -(int)1e9, ans = 0;
		for(Node cur : node) {
			if(cur.s > e) {
				ans += e-s;
				s = cur.s;
				e = cur.e;
			}else e = Math.max(e, cur.e);
		}
		System.out.println(ans+e-s);
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(자바) 객체 배열 보다 리스트가 더 빠른 이유가 궁금합니다

wwad 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말