java list removeall vs clear : 언제 쓰는지 정확하게 알아봅시다.

 안녕하세요. 이 글에서는 List의 removeAll 메소드에 대한 질문이 와서 이에 대해 써 보도록 하겠습니다. 콜렉션에 대해서 입문하셨다면, clear와 혼동하기 매우 쉽습니다. 이 둘은 쓰이는 용도가 다릅니다. 어떻게 용도가 다른지, 정확한 복잡도는 어떻게 되는지 언급해 보겠습니다.

 

---

 list에 0부터 99999까지 추가합니다. 다음에, list m에도 0부터 99999까지 추가합니다. 다음에 removeAll 메서드를 호출하였습니다.

 

 그러면 내부적으로 batchRemove 함수를 호출합니다. 일괄 처리할 때 그 batch입니다. 이로 미루어 보았을 때, Collection에 있는 삭제할 원소 하나 하나를 하나의 작업 단위로 보고 처리한다는 말이 되어 버립니다. 즉, 어떤 원소 m개를 삭제하려고 할 때 쓰게 됩니다. 이것이 어떻게 동작할까요?

 

 배치 데이터를 list로 넘겨주었다면, list의 contains가 동작할 겁니다. 

 

 그러면, indexOf를 호출하는데요.

 

 

 size만큼 돌면서 equals 메소드로 내용이 같은지를 검사합니다. 만약에 같으면, 해당 위치를 리턴합니다.

 

 예를 들어, batch성 데이터에 33이 있는 것을 찾는다면 어떨까요? 최악의 경우에 batch 크기만큼 걸릴 겁니다. 맨 끝까지 가서 찾아야 하기 때문입니다.

 

 

  c.contains는 뭔가요? c는 배치성 데이터를 의미합니다. 제거할 원소를 모아놓은 집합입니다. elementData, 즉 list를 돌면서, 리스트의 모든 원소들에 대해서, 배치성 데이터에 해당 원소가 있는지를 계속 검사합니다.

 

 

 예를 들어, list에 80이 n개 있고, 배치성 데이터에, 즉 제거해야 할 원소 데이터가 m개 있었다고 합시다. 만약에, 배치성 데이터에 80이 없다면 끝까지 계속 찾다가, 이 원소는 제거하지 말아야 한다고 할 겁니다. 즉, 복잡도가 O(nm)이 됩니다. 타겟 리스트의 크기가 n이고, 배치로 넘겨준 데이터의 크기가 m이라면. 그런데 스택 오버플로우 답변에 나온 대로 무조건 O(nm)이냐. 그건 또 아닙니다.

 

---

batch 데이터를 ArrayList가 아닌 HashSet으로 넘겨봅시다.

 

 이 때에는 어떨까요? Integer는 Comparable이 구현되어 있고, equals, hashCode가 구현되어 있으므로, 최악의 경우에도 배치 데이터에서 contains를 호출해도 O(log(m))이 보장됩니다.

 

 

 contains를 n회 호출하므로, 시간 복잡도는 최악의 경우에도 O(nlog(m))이 됩니다. Comparable이 구현되지 않고, 충돌이 매우 많이 일어난다면, contains 복잡도가 O(m)이라 최종 시간 복잡도가 O(nlog(m))이 아닌 O(nm)이 된다는 것이 주의하세요. 이는 관련 타래에서 확인하실 수 있습니다.

 

[관련글]

java hash 계열 자료구조는 충돌이 많이 일어날 때 복잡도가 어떻게 될까요?

 

---

 그러면 언제 clear를 쓸까요?

 

 리스트에 있는 모든 원소를 제거할 때 씁니다.

 

 

 시간 복잡도는 어떻게 될까요? 모든 원소를 돌면서 null 대입하기 때문에 list 크기가 n이라면 O(n)입니다.