[javascript] 정렬 된 숫자 배열에 숫자를 삽입하는 효율적인 방법?

정렬 된 JavaScript 배열이 있고 배열에 하나 이상의 항목을 삽입하여 결과 배열이 정렬 된 상태로 유지하려고합니다. 간단한 퀵 정렬 스타일 삽입 기능을 확실히 구현할 수있었습니다.

var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
  array.splice(locationOf(element, array) + 1, 0, element);
  return array;
}

function locationOf(element, array, start, end) {
  start = start || 0;
  end = end || array.length;
  var pivot = parseInt(start + (end - start) / 2, 10);
  if (end-start <= 1 || array[pivot] === element) return pivot;
  if (array[pivot] < element) {
    return locationOf(element, array, pivot, end);
  } else {
    return locationOf(element, array, start, pivot);
  }
}

console.log(insert(element, array));

[경고] 이 코드는 배열의 시작 부분에 삽입하려고 할 때 버그가 insert(2, [3, 7 ,9]있습니다.

그러나 Array.sort 함수를 구현하면 잠재적 으로이 작업을 수행 할 수 있음을 알았습니다.

var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
  array.push(element);
  array.sort(function(a, b) {
    return a - b;
  });
  return array;
}

console.log(insert(element, array));

두 번째 구현에서 첫 번째 구현을 선택해야 할 이유가 있습니까?

편집 : 일반적인 경우 O (log (n)) 삽입 (첫 번째 예에서 구현 된)은 일반 정렬 알고리즘보다 빠릅니다. 그러나 이것이 반드시 JavaScript의 경우는 아닙니다. 참고 :

  • 여러 삽입 알고리즘의 가장 좋은 경우는 O (n)이며, 이는 여전히 O (log (n))와 크게 다르지만 아래 언급 된대로 O (n log (n))만큼 나쁘지는 않습니다. 사용 된 특정 정렬 알고리즘으로 넘어갑니다 ( Javascript Array.sort 구현? 참조 )
  • JavaScript의 정렬 메소드는 기본 함수이므로 잠재적으로 큰 이점을 얻는 잠재적 인 큰 이점을 실현할 수 있습니다. 합당한 크기의 데이터 세트의 경우 O (n)보다 훨씬 큰 계수를 갖는 O (log (n))가 여전히 더 나쁠 수 있습니다.


답변

단일 데이터 포인트와 마찬가지로, 킥을 위해 Windows 7에서 Chrome을 사용하는 두 가지 방법을 사용하여 1000 개의 임의 요소를 10 개의 사전 정렬 된 숫자 배열에 삽입하여 이것을 테스트했습니다.

First Method:
~54 milliseconds
Second Method:
~57 seconds

따라서 적어도이 설정에서 기본 방법은 그것을 보완하지 못합니다. 작은 데이터 세트의 경우에도 1000 개의 배열에 100 개의 요소를 삽입합니다.

First Method:
1 milliseconds
Second Method:
34 milliseconds


답변

단순 ( 데모 ) :

function sortedIndex(array, value) {
    var low = 0,
        high = array.length;

    while (low < high) {
        var mid = (low + high) >>> 1;
        if (array[mid] < value) low = mid + 1;
        else high = mid;
    }
    return low;
}


답변

매우 흥미로운 토론으로 매우 좋고 놀라운 질문입니다! 또한 Array.sort()수천 개의 객체가있는 배열에서 단일 요소를 푸시 한 후 함수를 사용하고있었습니다 .

locationOf복잡한 객체가 있기 때문에 목적에 따라 함수 를 확장해야 하므로 다음과 같은 비교 함수가 필요합니다 Array.sort().

function locationOf(element, array, comparer, start, end) {
    if (array.length === 0)
        return -1;

    start = start || 0;
    end = end || array.length;
    var pivot = (start + end) >> 1;  // should be faster than dividing by 2

    var c = comparer(element, array[pivot]);
    if (end - start <= 1) return c == -1 ? pivot - 1 : pivot;

    switch (c) {
        case -1: return locationOf(element, array, comparer, start, pivot);
        case 0: return pivot;
        case 1: return locationOf(element, array, comparer, pivot, end);
    };
};

// sample for objects like {lastName: 'Miller', ...}
var patientCompare = function (a, b) {
    if (a.lastName < b.lastName) return -1;
    if (a.lastName > b.lastName) return 1;
    return 0;
};


답변

코드에 버그가 있습니다. 읽어야합니다.

function locationOf(element, array, start, end) {
  start = start || 0;
  end = end || array.length;
  var pivot = parseInt(start + (end - start) / 2, 10);
  if (array[pivot] === element) return pivot;
  if (end - start <= 1)
    return array[pivot] > element ? pivot - 1 : pivot;
  if (array[pivot] < element) {
    return locationOf(element, array, pivot, end);
  } else {
    return locationOf(element, array, start, pivot);
  }
}

이 수정이 없으면 코드는 배열의 시작 부분에 요소를 삽입 할 수 없습니다.


답변

나는 이것이 이미 답을 가지고있는 오래된 질문이라는 것을 알고 있으며, 다른 괜찮은 대답이 많이 있습니다. O (log n)에서 올바른 삽입 색인을 찾아서이 문제를 해결할 수 있다고 제안하는 답변이 있습니다.하지만 할 수는 있지만 배열을 부분적으로 복사해야하기 때문에 그 시간에 삽입 할 수 없습니다 우주.

결론 : 실제로 정렬 된 배열에 O (log n) 삽입 및 삭제가 필요한 경우 배열이 아닌 다른 데이터 구조가 필요합니다. B- 트리를 사용해야합니다 . 대용량 데이터 세트에 B-Tree를 사용하면 얻을 수있는 성능 향상으로 인해 여기에서 제공하는 개선 사항이 뒤 떨어질 수 있습니다.

배열을 사용해야하는 경우 나는 배열이 이미 정렬 된 경우에만 작동하는 삽입 정렬을 기반으로 다음 코드를 제공합니다 . 이것은 모든 인서트 후에 의지해야 할 경우에 유용합니다.

function addAndSort(arr, val) {
    arr.push(val);
    for (i = arr.length - 1; i > 0 && arr[i] < arr[i-1]; i--) {
        var tmp = arr[i];
        arr[i] = arr[i-1];
        arr[i-1] = tmp;
    }
    return arr;
}

O (n)에서 작동해야합니다. 당신이 할 수있는 최선이라고 생각합니다. js가 다중 할당을 지원하면 더 좋을 것입니다.
다음은 함께 연주하는 예입니다.

최신 정보:

이것은 더 빠를 수 있습니다.

function addAndSort2(arr, val) {
    arr.push(val);
    i = arr.length - 1;
    item = arr[i];
    while (i > 0 && item < arr[i-1]) {
        arr[i] = arr[i-1];
        i -= 1;
    }
    arr[i] = item;
    return arr;
}

JS Bin 링크 업데이트


답변

삽입 함수는 주어진 배열이 정렬되어 있다고 가정하고, 일반적으로 배열의 몇 가지 요소 만보고 새 요소를 삽입 할 수있는 위치를 직접 검색합니다.

배열의 일반적인 정렬 기능은 이러한 단축키를 사용할 수 없습니다. 분명히 배열의 모든 요소를 ​​검사하여 이미 올바르게 정렬되어 있는지 확인해야합니다. 이 사실만으로도 삽입 기능보다 일반 정렬 속도가 느려집니다.

일반적인 정렬 알고리즘은 일반적으로 평균 O (n ⋅ log (n)) 이며 구현에 따라 배열이 이미 정렬 된 경우 실제로 최악의 경우 일 수 있으며 O (n 2 )의 복잡성을 초래 합니다. 삽입 위치를 직접 검색하는 대신 O (log (n)) 의 복잡성이 있으므로 항상 훨씬 빠릅니다.


답변

소수의 항목의 경우 그 차이는 매우 사소합니다. 그러나 많은 항목을 삽입하거나 매우 큰 배열을 사용하는 경우 삽입 할 때마다 .sort ()를 호출하면 엄청난 오버 헤드가 발생합니다.

나는이 정확한 목적을 위해 꽤 매끄러운 바이너리 검색 / 삽입 기능을 작성하여 공유 할 것이라고 생각했습니다. while재귀 대신 루프를 사용하기 때문에 추가 함수 호출에 대해 들리지 않았으므로 원래 게시 된 메소드 중 어느 것보다 성능이 더 좋을 것이라고 생각합니다. 그리고 기본적으로 기본 Array.sort()비교기를 에뮬레이트 하지만 원하는 경우 사용자 정의 비교기 기능을 허용합니다.

function insertSorted(arr, item, comparator) {
    if (comparator == null) {
        // emulate the default Array.sort() comparator
        comparator = function(a, b) {
            if (typeof a !== 'string') a = String(a);
            if (typeof b !== 'string') b = String(b);
            return (a > b ? 1 : (a < b ? -1 : 0));
        };
    }

    // get the index we need to insert the item at
    var min = 0;
    var max = arr.length;
    var index = Math.floor((min + max) / 2);
    while (max > min) {
        if (comparator(item, arr[index]) < 0) {
            max = index;
        } else {
            min = index + 1;
        }
        index = Math.floor((min + max) / 2);
    }

    // insert the item
    arr.splice(index, 0, item);
};

다른 라이브러리를 사용할 수있는 경우 lodash는 루프 대신 사용할 수있는 sortedIndexsortedLastIndex 함수를 제공합니다 while. 두 가지 잠재적 단점은 1) 성능이 내 방법만큼 좋지 않다는 것입니다 (얼마나 나빠지는지는 잘 모르겠습니다) .2) 사용자 정의 비교기 기능을 받아들이지 않고 비교할 가치를 얻는 방법 만 (기본 비교기를 사용하여 가정합니다).