자바스크립트 크롬의 불안정한 배열 정렬 문제 - Javascript chrome-v8 Unstable sorting problem

아래 내용은 좀 오래된 내용으로 오늘(2020.11.26) 아래 Array.sort가 수정되었다는 걸 알려주셔서 먼저 이 문제는 수정이 된 상태라고 한다. 

 

@팅기지마세요 : 
크롬 계열 브라우저가 사용하는 V8 엔진은 v7.0 이후로 stable sort(같은 크기여도 순서가 바뀌지 않는)를 지원하는 Timsort 알고리즘을 Array#sort에 사용합니다. 이러한 변경사항은 2018-10-15에 배포되었고, 크롬 버전 70.0.3538부터 적용된 것으로 보이는데 V8 엔진 배포 후 하루나 이틀 뒤에 배포되었습니다. Array#sort 관련 자료를 조사하다가 글을 보게되어 댓글을 남깁니다

아마도 제가 이 글을 적은 시점은 18년 이전 이었을 거고.. 그 후에 저 시점에 패치가 된 것으로 보인다. 아래 내용은 먼 과거 얘기고 크롬 70 이전 버전을 사용하는 곳은 상당히 적을 것이기 때문에 해당 문제는 거의 발생하지 않는다고 생각이 된다. 

 

하지만 혹시라도 비슷한 문제가 발생한다면 70버전인지를 체크해봄이 좋겠다...

 

Javascirpt

최근 내 개인 프로젝트 내에 이것저것 기능을 추가하며 공부까지 겸하고 있는데 자바스크립트의 Array.sort를 사용하다가 멘탈에 금이가는 걸 겪으며 해결했던 걸 정리해본다. 앞으로 개발쪽의 글은 1차적으로 개인적인 공부를 하며 정리 하는 목표와 2차적으로 이글을 보는 개발자에게 도움이 되었으면 한다.

 

Array.sort(func)는 아시다시피 정렬을 하는 함수다. 그런데 브라우저 별로 사용하는 정렬 알고리즘이 다르단다. ECMAScript에서 정렬 알고리즘을 자체를 규제 하지 않고 각 구현하는 브라우저 벤더에 맡긴단다. ( 이... 이게 표준임? 표준을 표방하면서 왜 동작이 다르게 되는건데...? )

 

Mozilla는 MergeSort

Safari는 SelectionSort

Chrome v8은 Quicksort를 쓰는데 웃긴게 배열 10개 이하는 InsertionSort이고 초과된 경우만 QuickSort다. 황당해서 github까지 찾아들어가봤다.

 

 

chrome-v8 github 소스 정렬쪽.

if(to - from <= 10 ) InsertionSort(...);

 

 

물론 성능상으로는 그만큼 크롬이 압도적이다. 그... 근데 정렬같은 경우 수천,수만개 이상을 브라우저에서 처리해야해서 속도에 문제가 있다면 그건 애초에 프로그램 아키텍처를 다시 잡을 문제이지.. 알고리즘의 문제라고 할수 있을까? 이런건 브라우저 모두 다 통일해주었으면 하는 바램이다.

 

 

 

그래서 나타나는 현상은?

그래서... 크롬 브라우저(안드로이드 모바일도 포함)에서 10개의 정렬까진 위치가 맘대로 변하진 않지만 10개를 초과하면 값이 같은 경우 위치가 맘대로 바뀌어버리는 현상이 생긴다. 보통 우리는 정렬 요소의 값이 같을 때 일관된 정렬을 원한다. 내가 80점이고 개똥이가 80점이라면 그 순서는 동일하게 나와야 한다는 것이다.

 

근데 이놈의 크롬은...

이렇게도 나왔다가 나 : 80, 개똥 : 80

이렇게도 나온다 개똥 : 80, 나 : 80

그런데 요소가 10개일때는 괜찮다가 딱 11개가 되는 순간 문제가 발생하니 맨탈에 금이 가는 수밖에 없었다... 구글을 통해서 미친듯이 찾았으나 브라우저의 특성이라고 생각하지 못해 찾는데 너무 오래 걸렸다. 오랜검색 끝에 구글에서는 'chrome stable sort' 정도로 검색하면 나오더라...

 

그렇다면 해결방법은?

 

array 배열 속성에 각각 인덱스를 심어놓고 정렬값이 같은 경우 위치를 보고 정렬을 해주면 된다. 무슨 말이냐면...소스로 보면 더욱 간단하다. 검색을 하다보면 수많은 갖가지 솔루션들이 나오지만 이 방법이 가장 명쾌하더라...

 

var sort = function (a, b) { 
	if (a.key === b.key) return a.position - b.position; 
    if (a.key < b.key) return -1; return 1; 
};

인덱스를 심으려면 아래와 같이......

array.map((o, i) => { o.idx = i ; return o; }).sort(func);