Comparable를 구현한 방식과 comparing을 구현한 방식간 성능차이

자바에서 객체를 정렬시키기 위해서는 Comparable or Comaparator 인터페이스를 사용합니다.

정렬을 해야하는 객체의 경우 해당 클래스에 Comparable을 구현하여 compareTo 메소드를 정의하면 되는데요.

 

이펙티브 자바에서는 compareTo 메소드의 정의규칙을 다음과 같이 설명합니다.

• Comparable을 구현한 클래스는 모든 x, y에 대해 x.compareTo(y) == y.compareTo(x)여야 한다.
• Comparable을 구현한 클래스는 추이성을 보장해야한다. (x.compareTo(y) > 0 && y.compareTo(z) > 0 이면 x.compareTo(z) > 0이다.)
• Comparable을 구현한 크래스는 모든 z에 대해 x.compareTo(y) == 0이면 x.compareTo(z) == y.compareTo(z)이다.
• (x.compareTo(y) == 0) == (x.equals(y))여야한다. 이 사항을 지키지 않으며 Comparable을 구현한 클래스는 해당 사실을 명시해야한다. 일부 컬렉션(Collection, Set, Map) 클래스에서 동작이 엇박자가 발생할 수 있다.

다음은 정의규칙을 기반으로 구현한 코드입니다.

 

public class User implements Comparable<User>{
	
	int age;
	String name;
	
	public User() {
		
	}
	
	public User(int age, String name) {
		this.age = age;
		this.name = name;
	}
	
	@Override
	public int compareTo(User o) {
		if(Integer.compare(this.age, o.age) == 0) {
			return this.name.compareTo(o.name);
		}

		return Integer.compare(this.age, o.age);
	}

	public int getAge() {
		return age;
	}

	public void setAge(int age) {
		this.age = age;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	@Override
	public String toString() {
		return "User [age=" + age + ", name=" + name + "]";
	}

}

 

User 객체의 비교하고자하는 기준 순서는 age, name입니다. age를 비교한 후 age가 같다면 name을 비교하게끔 구현하였습니다. 구현한 객체를 가지고 정렬을 해보겠습니다.

 

		List<User> list = Arrays.asList(new User(20, "Lee"),
										new User(21, "Hong"),
										new User(20, "Kim"),
										new User(22, "YUN"));
	
		
		Collections.sort(list);
		list.stream().forEach(System.out::println);

 

실행결과

 

 

age순으로 정렬 후, age가 같다면 name순으로 정렬되는 것을 확인하였습니다. 

객체를 정렬하기 위해서는 Comaprable을 구현해야한다고 했는데요. 만약 Comparable을 구현하지 않은 객체가 Collections or Arrays에서 정렬을 하고 싶다면 반드시 구현해야 정렬이 가능한가?라는 의문이 생겼습니다.

 

 

 

API 문서를 확인해보면 Comparable을 구현한 객체만이 정렬할 수 있다고 나와있네요. 그렇다고 정렬할 방법이 없는건 아닙니다. 

 

다음과 같이 스트림을 이용하여 Comparator를 지정하여 정렬시킬 수 있습니다.

 

		List<User> list = Arrays.asList(new User(20, "Lee"),
										new User(21, "Hong"),
										new User(20, "Kim"),
										new User(22, "YUN"));
	
		Function<User, Integer> sortedAge = user->user.getAge();
		Function<User, String> sortedName = user->user.getName();
		
		list.stream().sorted(comparing(sortedAge).thenComparing(sortedName)).forEach(System.out::println);

 

실행결과

 

만약 Comparable을 구현한 방법과 스트림과 Comparator를 이용한 방법 간 성능차이가 없다면 스트림과 Comparator 방법이 간결하여 선호될 것 같은데요. 두 방법 간 성능차이가 존재하는지 테스트를 진행해봤습니다.

 

테스트 케이스 100만 건

 

1. Comparable 구현방법

 

		List<User> users = new ArrayList<User>();
		
		Random rand = new Random();
		
		for(int i=0; i<1000000;i++) {
			int age = rand.nextInt(70) + 20;
			User user = new User(age, RandomUtil.getRandomString(3));
			users.add(user);
		}

		long start = System.currentTimeMillis();

		Collections.sort(users);

		long end = System.currentTimeMillis();
		
		System.out.println((end-start));

 

10번정도 실행해봤을 때 평균 약 1초 걸렸습니다. 

 

2. Comparator 구현방법

 

		List<User> users = new ArrayList<User>();
		
		Random rand = new Random();
		
		for(int i=0; i<1000000;i++) {
			int age = rand.nextInt(70) + 20;
			User user = new User(age, RandomUtil.getRandomString(3));
			users.add(user);
		}

		long start = System.currentTimeMillis();

		Function<User, Integer> sortedAge = user->user.getAge();
		Function<User, String> sortedName = user->user.getName();
		
		users.stream().sorted(Comparator.comparing(sortedAge).thenComparing(sortedName)).collect(Collectors.toList());
		
		long end = System.currentTimeMillis();
		
		System.out.println((end-start));

 

마찬가지로 약 1.3초가 걸렸습니다.

 

Comaprator 방식이 20~30% 성능저하가 발생한다는 것을 알 수 있었습니다. 정렬 알고리즘의 차이라기보다는 스트림 최적화 문제로 예상되네요.

 

* 자바에서 정렬알고리즘은 Tim Sort 알고리즘을 사용하고 있습니다.

 

참조

• 이펙티브 자바