DiffUtil은 두개의 리스트를 비교해서 차이가 있으면 두번째 리스트에 차이점을 업데이트 해주는 유틸리티 class 이다. 리사이클러뷰의 어댑터가 업데이트될때 사용된다. 백그라운드 스레드에서 DiffUtil을 쉽게 사용할 수 있는 ListAdapter와 AsyncListDiffer 클래스를 살펴보길 바란다.
DiffUtil은 Eugene W.Myer의 최소한의 횟수로 리스트를 수정해줄 수 있는 알고리즘을 사용해서 리스트를 변경해준다.
(유진 마이어의 Diffing Algorithm을 의미한다. 한국어로 하면 비교 알고리즘이다.)
Myer의 알고리즘은 변동된 아이템을 관리하지 않기 때문에 DiffUtil은 결과에 대해 두번째 통과를 통해서 이동된 항목을 감지한다.
(아마 differece algorithm 이 동작하는 원리를 간략하게 얘기하려고 하는듯 하다.)
ListAdapter 와 AsyncListDiffer에서 DiffUtil클래스는 사용되는동안 list가 사용되서는 안된다는 점을 명심해야 한다. 이는 일반적으로 두 리스트가 스스로 그리고 리스트의 요소가(아니면 적어도, 리스트 요소의 속성이 가 diffing 되는 동안 사용되야 한다. ) 스스로가 바로 변경이 일어나서는 안된다는 것을 의미한다. 대신, 새로운 리스트는 언제든지 변경된 내용을 제공 받을 수 있어야 한다.
DiffUtil로 전달된 lists는 변경되지 않은 요소를 공유하는 것이 일반적이므로 DiffUtil을 사용하기 위해 모든 데이터를 다시 로드할 필요는 없다.
만약 lists 가 거대하다면, 이 계산은 오래걸릴 수 있으니 개발자는 백그라운드 스레드에서 이 작업을 진행할 수 있게끔 설정할 수 있고, 백그라운드 스레드에서 작업을 진행 시켰다면 DiffResult 를 메인 스레드의 리사이클러뷰에 적용시켜서 사용하면 된다.
비교 알고리즘은 O(N)공간을 사용해서 두 리스트 사이에서 차이점을 최소한의 경우의 수로 찾아낸다.
예상 시간 성능은 O(N + D^2)이며, 여기서 D는 편집 스크립트(이게 뭘 의미하는 거지?)의 길이이다.
움직임이 감지되면(아마 리스트에 변경이 일어나는 경우를 의미하는듯), 추가적인 O(MN)시간이 쓰인다. M은 추가된 총 아이템의 개수를 의미하고 N은 삭제된 총 아이템의 개수를 의미한다.
만약 당신의 lists가 같은 제약에 의해서 이미 분류가 되었다면(예. 리스트에 게시된 타임스탬프), 성능향상을 위해서 당신은 동작 감지를 종료시킬 수 있다.
알고리즘의 실제 실행 시간은 list의 데이터가 얼마나 바꼈는지와 당신이 만든 비교 함수가 어떻냐에 따라 달라진다.
(리스트의 차이점을 찾아내서 수정하는데 까지 걸리는 최단 시간이 얼마나 효율적인지는 list가 얼만큼 바꼈는지, 내가 직접 만든 비교 함수가 어떤지에 따라 크게 달라진다는 말이다.)
아래 내용은 연산을 했을때 평균적으로 걸리는 시간이다. : 테스트 list는 무작위의 문자열 UUID로 구성되고 Nexus5 M 에서 실행됐다.)
-
100 items and 10 modifications: avg: 0.39 ms, median: 0.35 ms
-
100 items and 100 modifications: 3.82 ms, median: 3.75 ms
-
100 items and 100 modifications without moves: 2.09 ms, median: 2.06 ms
-
1000 items and 50 modifications: avg: 4.67 ms, median: 4.59 ms
-
1000 items and 50 modifications without moves: avg: 3.59 ms, median: 3.50 ms
-
1000 items and 200 modifications: 27.07 ms, median: 26.92 ms
-
1000 items and 200 modifications without moves: 13.54 ms, median: 13.36 ms
(이정도면 일반 사용자 입장에서 불편하다고 느끼지도 않을 것 같다. 정말 대단하구만..)
구현하는데 제약인 부분이 있어서 , list의 최대 크기는 2^26이다.
'안드로이드' 카테고리의 다른 글
| Hilt를 이용한 ViewModel 객체 생성 (0) | 2024.02.15 |
|---|---|
| viewPager2 Indicator 예제 (0) | 2024.02.01 |
| 리사이클러뷰 데이터가 꼬일때 해결하는 방법 (2) | 2023.11.15 |
| Handler, Looper 핸들러와 루퍼의 의미 (0) | 2023.10.16 |
| Handler, Looper, Message (0) | 2023.10.13 |
