프론트 엔드 원에는 항상 오해가 있었던 것 같습니다. 프론트 엔드는 알고리즘 지식을 사용할 수 없습니다. 오랫동안 모든 사람 이이 진술의 영향을 받았을 수도 있습니다. 얼마 전에 제품 수요가 발생할 때까지, 나는 이것이 사실이 아니라는 것을 뒤돌아 보았습니다.
프론트 엔드 분류
프론트 엔드 분류 시나리오
프론트 엔드는 분류 조건을 요청 매개 변수로 백엔드로 전달하고 백엔드는 분류 결과를 프론트 엔드에 대한 요청 응답으로 반환합니다. 이는 일반적인 설계입니다. 그러나 일부 제품에는 적합하지 않습니다.
시나리오를 상상해보십시오 : 식품 앱을 사용할 때는 종종 분류 방법을 전환하고 가격별로 정렬 한 다음 등급별로 정렬합니까?
실제 생산에서 서버 비용과 같은 요소로 인해 단일 데이터 쿼리가 전반적인 성능 병목 현상이되면 프론트 엔드로 정렬하여 성능을 최적화하는 것으로 간주됩니다.
정렬 알고리즘
나는 이것을 소개 할 필요가 없다고 생각합니다. 컴퓨터 과학의 기본 알고리즘으로 설명은 Wikipedia 에서 직접 복사됩니다.
이 단락은 여기에 순전히 첫 번째 (사람)과 두 번째 (SHU)를 물려 받기 위해 존재합니다.
자바 스크립트 분류
프론트 엔드 분류에 대해 이야기하기 때문에 자연스럽게 JavaScript의 기본 인터페이스 Array.prototype.sort 생각합니다.
이 인터페이스는 ECMAScript 1st Edition 이후에 존재했습니다. 최신 사양에서 설명이 어떻게 보이는지 봅시다.
Array.prototype.sort 사양
Array.prototype.sort(compareFn)
코드 사본은 다음과 같습니다.
이 배열의 요소는 정렬됩니다. 정렬은 안정적으로 필요하지 않습니다 (즉, 동일하게 비교하는 요소가 반드시 원래 순서로 남아있는 것은 아닙니다). 비교가 정의되지 않은 경우 두 인수 x와 y를 받아들이고 x <y 인 경우 x = y 인 경우 x = y 인 경우 음수 값을 반환하는 기능이어야합니다.
분명히, 사양은 내부적으로 구현 된 sort 알고리즘의 내용을 제한하지 않습니다. 인터페이스의 구현조차도 안정적으로 정렬 될 필요는 없습니다. 이것은 매우 중요하며 다음에 여러 번 관여 할 것입니다.
이러한 맥락에서, 프론트 엔드 정렬은 실제로 각 브라우저의 특정 구현에 따라 다릅니다. 그렇다면 주류 브라우저는 어떻게 정렬을 구현합니까? 다음으로 Chrome , Firefox 및 Microsoft Edge를 각각 간단히 비교합니다.
크롬에서의 구현
Chrome의 JavaScript 엔진은 V8입니다. 오픈 소스이므로 소스 코드를 직접 볼 수 있습니다.
전체 array.js는 JavaScript 언어로 구현됩니다. 분류 방법 부분은 내가 본 빠른 정렬보다 훨씬 더 복잡하지만 핵심 알고리즘은 여전히 빠른 정렬입니다. 복잡한 알고리즘의 이유는 V8이 성능 고려 사항을 위해 많은 최적화를 만들었 기 때문입니다. (다음에 대해 이야기 할게)
Firefox에서 구현
Firefox의 JavaScript 엔진이 사용할 배열 분류 알고리즘을 결정할 수 없습니다. [3]
기존 정보에 따르면 SpiderMoney는 내부적으로 정렬을 합병합니다.
Microsoft Edge에서의 구현
Microsoft Edge의 JavaScript Engine Chakra 코드의 핵심 부분은 2016 년 초 Github에 공급되었습니다.
소스 코드를 살펴보면 차크라의 배열 정렬 알고리즘도 빠른 정렬을 구현한다는 것을 알 수 있습니다. V8과 비교하여 V8의 성능 최적화가 전혀없는 순전히 빠른 분류만을 구현합니다.
JavaScript 배열 정렬 문제
우리 모두가 알고 있듯이 빠른 정렬은 불안정한 정렬 알고리즘이며, Merge 정렬은 안정적인 정렬 알고리즘입니다. 다른 엔진의 알고리즘 선택의 차이로 인해 프론트 엔드는 Array.Prototype.sort 인터페이스에서 구현 된 JavaScript 코드에 의존하며 브라우저에서 수행되는 실제 정렬 효과는 일치하지 않습니다.
문제가 발생하기 전에 정렬 안정성의 차이는 특정 시나리오에 의해 트리거되어야합니다. 대부분의 경우 불안정한 정렬에는 영향을 미치지 않습니다.
실제 프로젝트 개발에서 배열 분류에 안정성이 필요하지 않은 경우 실제로이를 볼 수 있으며 브라우저 간의 구현 차이는 그리 중요하지 않습니다.
그러나 프로젝트가 정렬이 안정적이어야한다면 이러한 차이의 존재는 수요를 충족시키지 못할 것입니다. 우리는 이것을 위해 몇 가지 추가 작업을해야합니다.
예를 들어:
특정 도시의 자동차 라이센스 경매 시스템에 대한 최종 승리 규칙은 다음과 같습니다.
1. 가격별로 정렬하십시오.
2. 입찰 명령 (즉, 가격 제출 시간)에 따라 동일한 가격이 긍정적으로 정렬됩니다.
정렬이 프론트 엔드에서 수행되면 빠른 정렬을 사용하여 브라우저에 표시되는 승자는 기대치와 일치하지 않을 수 있습니다.
차이점을 탐색하십시오
해결책을 찾기 전에 문제의 이유를 탐색해야합니다.
Chrome이 빠른 정렬을 사용하는 이유
실제로이 상황은 처음부터 존재했습니다.
Chrome Beta는 2008 년 9 월 2 일에 출시되었지만 출시 직후 일부 개발자는 Chromium Development Group에 #90 버그 피드백을 제출했습니다. V8의 배열 정렬 구현은 안정적이지 않습니다.
이 버그 문제 토론은 많이 있습니다. 2015 년 11 월 10 일까지 개발자는 여전히 V8의 배열 분류 구현에 대해 언급했습니다.
동시에, 우리는 또한 문제가 종료되었음을 알았습니다. 그러나 2013 년 6 월 개발 팀원들이 ECMAScript 다음 사양에 대한 논의에 대한 참조로 다시 문을 열었습니다.
그리고 ES-Discuss의 마지막 결론은입니다
코드 사본은 다음과 같습니다.
변하지 않습니다. 안정적인 것은 불안정의 하위 집합입니다. 그 반대도 마찬가지로, 모든 불안정한 알고리즘은 일부 입력에 대해 안정적인 결과를 반환합니다. Mark의 요점은“항상 불안정 해지는 것”을 요구하는 것은 어떤 언어를 선택하든 의미가 없다는 것입니다.
/안드레아스
이 기사의 앞부분에서 인용 된 최종 ECMAScript 2015 사양에 설명 된 바와 같이.
시대의 특성
IMHO,이 문제는 Chrome의 출시가 시작될 때보고되었으며, The Times의 특별한 특성이있을 수 있습니다.
위에서 언급 한 바와 같이, Chrome의 첫 번째 버전은 2008 년 9 월에 출시되었습니다. Statcounter의 통계에 따르면, 그 기간 동안 시장 점유율이 가장 높은 두 브라우저는 IE (IE6 및 IE7 만)와 Firefox이며 시장 점유율은 각각 67.16% 및 25.77%에 이릅니다. 다시 말해, 두 브라우저의 시장 점유율은 90%를 초과합니다.
다른 브라우저 정렬 알고리즘 통계에 따르면, 90% 이상의 시장 점유율을 가진이 두 브라우저는 안정적인 배열 분류를 채택합니다. 따라서 Chrome의 출시가 시작될 때 개발자가 의문을 제기하는 것이 합리적입니다.
사양을 준수하십시오
버그 문제 토론에서 우리는 엔진 구현의 빠른 정렬을 사용하여 개발 팀 구성원의 고려 사항을 대략 이해할 수 있습니다.
이 중 하나는 엔진이 ECMAScript 사양을 준수해야한다고 생각한다는 것입니다. 사양에는 안정적인 정렬에 대한 설명이 필요하지 않기 때문에 V8의 구현이 사양과 완전히 일치한다고 생각합니다.
성능 고려 사항
또한 V8 설계에서 중요한 고려 사항은 엔진의 성능이라고 생각합니다.
빠른 정렬은 병합 분류보다 전반적인 성능을 향상시킵니다.
컴퓨팅 효율이 높아집니다. 실제 컴퓨터 실행 환경에서 빠른 정렬은 동시에 복잡성을 가진 다른 분류 알고리즘보다 더 빠릅니다 (최악의 조합에 도달하지 않는 경우)
더 낮은 공간 비용. 전자는 후자의 O (n) 공간 복잡성에 비해 O (n) 공간 복잡성만을 가지고 있으며, 런타임 중 메모리 소비는 적습니다.
배열 정렬 알고리즘에서 V8의 성능 최적화
V8은 엔진 성능에 매우 관심이 있으므로 배열 분류에서 무엇을 하는가?
소스 코드를 읽음으로써 나는 여전히 몇 가지 기본 지식을 배웠습니다.
혼합 삽입 정렬
빠른 분류는 큰 배열을 분해하고 분해하고 층으로 레이어를 다시 묶는 아이디어입니다. 그러나 재귀 깊이가 너무 커지면 재귀 콜 스택의 메모리 자원 소비도 매우 커집니다. 최적화가 좋지 않으면 스택 오버플로가 발생할 수도 있습니다.
V8의 현재 구현은 임계 값을 설정하고 가장 낮은 층에서 10 이하의 작은 배열에 대한 삽입 분류를 사용하는 것입니다.
Wikipedia의 코드 주석 및 설명에 따르면, 삽입 정렬의 평균 시간 복잡성은 O (n²)이지만 빠른 정렬 O (NN)의 것보다 나쁩니다. 그러나 실행중인 환경에서는 작은 배열의 삽입 분류 효율이 빠른 정렬보다 효율적이므로 여기에서 확장되지 않습니다.
v8 코드 예제
var QuickSort = function QuickSort (a, from, to) {...... while (true) {// 삽입 정렬은 짧은 배열의 경우 더 빠릅니다. if (to -from <= 10) {insertionsort (a, from, to); 반품; } ......} ......};세 숫자가 있습니다
알려진 바와 같이, 빠른 분류 아킬레스 힐은 알고리즘이 최악의 배열 조합으로 퇴보한다는 것입니다.
빠른 정렬 알고리즘의 핵심은 피벗을 선택하고 후속 재귀에 대한 참조에 따라 비교 및 2 개의 숫자 영역으로 교환 된 배열을 분해하는 것입니다. 이미 주문한 배열의 경우, 기준 요소가 선택 될 때마다 첫 번째 또는 마지막 요소가 항상 선택되면 매번 비어있는 숫자 영역이 있고 재귀적인 층이 N에 도달하여 결국 A (n²)에 대한 알고리즘의 시간 복잡성 저하로 이어질 것입니다. 따라서 피벗의 선택은 매우 중요합니다.
V8은 median-of-three 의 최적화를 사용합니다. 시작과 끝의 두 요소 외에도 벤치 마크 요소의 경쟁에 참여하기 위해 다른 요소가 선택됩니다.
세 번째 요소에 대한 선택 전략은 대략입니다.
배열의 길이가 1000보다 작거나 같으면 반 위치의 요소를 대상 요소로 선택하십시오.
배열의 길이가 1000을 초과하면 200-215 거리에서 하나의 요소를 선택하여 (고정되지 않은, 배열의 길이에 따라 변경) 후보 요소의 배치를 먼저 결정하십시오. 그런 다음이 배치에 후보 요소를 정렬하고 결과 중앙값을 대상 요소로 사용하십시오.
마지막으로, 세 요소의 중간 값을 피벗으로 사용하십시오.
v8 코드 예제
var getThirdIndex = function (a, from, to) {var t_array = new InternalArray (); // 피벗 후보를 결정하려면 'From'과 'to'를 모두 사용하십시오. var 증분 = 200 + ((to -from) & 15); var j = 0; += 1에서; -= 1; for (var i = from; i <to; i += xcrement) {t_array [j] = [i, a [i]]; J ++; } t_array.sort (function (a, b) {return compralfn (a [1], b [1]);}); var Third_Index = t_array [t_array.length >> 1] [0]; return Third_index;}; var quicksort = function QuickSort (a, to) {...... while (true) {...... if (to -from> 1000) {Third_index = getThirdIndex (a, from, to); } else {thred_index = from + ((to -from) >> 1); }} ......};제자리에 정렬하십시오
빠른 정렬 알고리즘을 검토하는 동안 인터넷에서 JavaScript를 사용하여 구현의 많은 예를 보았습니다.
그러나 코드 구현의 대부분은 다음과 같습니다.
var quicksort = function (arr) {if (arr.length <= 1) {return arr; } var pivotindex = math.floor (arr.length / 2); var pivot = arr.splice (pivotindex, 1) [0]; var 왼쪽 = []; var right = []; for (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} return QuickSort (왼쪽) .concat ([pivot], QuickSort (오른쪽));};위 코드의 주요 문제는 다음과 같습니다. 왼쪽 및 오른쪽 의 두 숫자 영역을 사용하여 재귀 서브 어레이를 저장하므로 O (N)의 추가 저장 공간이 필요합니다. 이것은 이론적 평균 공간 복잡성 O (N)에 비해 큰 차이입니다.
추가 공간 오버 헤드는 실제 런타임의 전체 속도에도 영향을 미칩니다. 이것은 또한 빠른 분류가 같은 수준의 시간 복잡성을 넘어 실제 런타임에서 수행 할 수있는 이유 중 하나입니다. 따라서 일반적으로 더 나은 성능으로 빠른 분류는 내면의 정렬을 채택합니다.
V8 소스 코드의 구현은 원래 배열에서 요소를 교환하는 것입니다.
Firefox가 병합 정렬을 사용하는 이유
그 뒤에도 이야기가 있습니다.
실제로, 처음에 Firefox가 릴리스되었을 때, 잘 문서화 된 배열 정렬을 구현하기 위해 안정적인 정렬 알고리즘을 사용하지 않았습니다.
원래 버전의 Firefox (Firebird)에서 구현 한 배열 정렬 알고리즘은 힙 분류였으며 불안정한 정렬 알고리즘이기도합니다. 따라서 누군가는 나중에 버그를 제출했습니다.
Mozilla Development 팀은이 문제에 대한 일련의 토론을 수행했습니다.
토론 과정에서 몇 가지 요점을 그릴 수 있습니다
1. 같은 기간 동안 모질라의 경쟁자는 IE6였습니다. 위의 통계에서 IE6은 정렬에 안정적임을 알 수 있습니다.
2. JavaScript의 아버지 인 Brendan Eich는 안정성이 좋다고 생각합니다.
3. Firefox는 힙 분류 전에 빠른 정렬을 사용합니다
개발 그룹 구성원이 안정적인 정렬 알고리즘을 구현하는 경향이 있다는 주요 전제를 바탕으로, Firefox3는 새로운 배열 분류 구현으로 병합 분류를 취합니다.
정렬 안정성의 차이를 해결하십시오
나는 주로 각 브라우저의 분류 구현의 차이점을 말하고 이러한 차이가 존재하는 더 피상적 인 이유를 설명하기 위해 주로 위에 있다고 말했다.
그러나이 글을 읽은 후에도 독자들은 여전히 질문이있을 수 있습니다. 내 프로젝트가 안정적인 정렬에 의존 해야하는 경우 어떻게해야합니까?
해결책
실제로이 문제를 해결한다는 아이디어는 비교적 간단합니다.
브라우저는 다양한 고려 사항을 위해 다른 정렬 알고리즘을 선택합니다. 일부는 극도의 성능을 추구하는 경향이있는 반면, 다른 일부는 좋은 개발 경험을 제공하는 경향이 있지만 따라야 할 규칙이 있습니다.
현재 알려진 상황에서 판단하면 모든 주류 브라우저 (IE6, 7, 8 포함)는 기본적으로 배열 분류 알고리즘의 구현을 열거 할 수 있습니다.
1. 정렬/팀 소트를 병합합니다
2. 빠른 정렬
따라서 빠른 정렬을 안정적인 정렬로 변환 할 수 있습니까?
일반적으로 객체 배열에 불안정한 정렬을 사용하면 결과에 영향을 미칩니다. 다른 유형의 배열 자체는 안정적이거나 불안정한 정렬 결과를 사용하지만 동일합니다. 따라서 계획은 다음과 같습니다.
정렬 할 배열을 전처리하고 객체의 다른 속성과 충돌하지 않도록 정렬 할 각 객체에 자연 순서 속성을 추가하십시오.
사용자 정의 분류 비교 방법 Comparnfn은 사전 판단이 동일 할 때 두 번째 판단 차원이므로 항상 자연 순서를 사용합니다.
병합 분류와 같은 구현에 직면 할 때 알고리즘 자체가 안정적이므로 추가 자연 차수 비교는 분류 결과를 변경하지 않으므로 체계 호환성이 더 좋습니다.
그러나 정렬 할 배열을 수정하는 것이 포함되며 자연 순서 특성을 저장하려면 추가 공간이 필요합니다. V8과 같은 엔진은 유사한 방법을 사용해서는 안된다는 것은 생각할 수 있습니다. 그러나 개발자가 사용자 정의하는 정렬 계획으로 실현 가능합니다.
체계 코드 예제
'strict'; const index = symbol ( 'index'); 함수 getComparer (compare) {return function (왼쪽, 오른쪽) {let result = compar (왼쪽, 오른쪽); 반환 결과 === 0? 왼쪽 [색인] - 오른쪽 [색인] : 결과; };} function sort (array, compare) {array = array.map ((item, index) => {if (typeof item === 'object') {item [index] = index;} return item;}); return array.sort (getComparer (compare));}위의 내용은 안정적인 정렬을 만족시키는 간단한 알고리즘 수정 예일뿐입니다.
간단한 이유는 실제 생산 환경에서 배열 입력으로 데이터 구조가 복잡하기 때문에 실제 상황에 따라 더 많은 유형의 선주문이 필요한지 판단해야합니다.
꼬리표
1. 프론트 엔드는 이제 비교적 광범위한 개념입니다. 이 기사의 프론트 엔드는 주로 브라우저를 캐리어로 사용하고 JavaScript를 프로그래밍 언어로 사용하는 환경을 나타냅니다.
2.이 기사는 알고리즘 전체를 포함하지 않습니다. 일반적인 정렬 알고리즘을 진입 점으로 사용하고 싶습니다.
3. Firefox 어레이 분류에 의해 구현 된 알고리즘을 확인하면 SpiderMoney에서 정렬 관련 버그가 발견되었습니다. 일반적으로 논의하는 동안 누군가는 합병 분류를 대체하기 위해 극단적 인 사례에서 더 나은 성능을 가진 Timsort 알고리즘을 사용하는 것을 제안했지만 Mozilla 엔지니어들은 Timsort 알고리즘의 라이센스 승인 문제로 인해 Mozilla의 소프트웨어에서 알고리즘을 직접 사용하고 상대방의 후속 답변을 기다릴 수있는 방법은 없다고 말했습니다.
요약
위는 프론트 엔드 분류에서 발생하는 문제에 대한 요약 및 해결책입니다. 최근 몇 년 동안 점점 더 많은 프로젝트가 풍부한 고객 애플리케이션으로 변화하고 있으며 프로젝트의 프론트 엔드 비율이 증가했습니다. 향후 브라우저 컴퓨팅 성능이 더욱 향상되면서보다 복잡한 계산이 가능합니다. 책임이 바뀌면서 프론트 엔드 형태는 몇 가지 주요 변화를 겪을 수 있습니다. 세상을 걷는 경우 항상 기술이 있어야합니다.