숫자를 정렬된 숫자 배열에 삽입하는 효율적인 방법은 무엇입니까?
나는 정렬된 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));
[경고] 배열의 때를 들어 이 코 는 배 부 삽 버 있 때 습 니 다 가 그 할 입 드 에 분 시 열 의 작 니 다 있 습 ▁has ▁this , ▁when ▁e ▁a ▁trying ▁codeinsert(2, [3, 7 ,9]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(log(n))는 합리적인 크기의 데이터 세트의 경우 O(n)보다 훨씬 더 나쁠 수 있습니다.
단순(데모):
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;
}
단일 데이터 포인트로서 Windows 7에서 Chrome을 사용하여 100,000개의 사전 정렬된 숫자 배열에 1000개의 무작위 요소를 삽입하는 것을 테스트했습니다.
First Method:
~54 milliseconds
Second Method:
~57 seconds
따라서 적어도 이 설정에서는 네이티브 방식이 이를 보완하지 못합니다.이는 100개의 요소를 1000개의 배열에 삽입하는 작은 데이터 세트에도 해당됩니다.
First Method:
1 milliseconds
Second Method:
34 milliseconds
매우 흥미로운 토론과 함께 매우 좋고 놀라운 질문입니다!저는 또한 그것을 사용했습니다.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-Tree를 사용해야 합니다.대용량 데이터 세트에 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;
}
업데이트 2
@terrymorse는 댓글에서 javascriptsArray.splice 메서드가 미친 듯이 빠르며 시간 복잡성의 지속적인 개선 이상이라고 지적했습니다.링크드 리스트 마법이 사용되고 있는 것 같습니다.즉, 일반 배열과는 다른 데이터 구조가 여전히 필요합니다. 자바스크립트 배열은 기본적으로 다른 데이터 구조를 제공할 수 있습니다.
삽입 함수는 지정된 배열이 정렬되어 있다고 가정하고, 일반적으로 배열의 몇 가지 요소만 보고 새 요소를 삽입할 수 있는 위치를 직접 검색합니다.
배열의 일반 정렬 함수는 이러한 바로 가기를 사용할 수 없습니다.분명히 배열의 모든 요소가 이미 올바르게 정렬되었는지 확인하기 위해 최소한 검사를 수행해야 합니다.이 사실만으로도 삽입 함수보다 일반 정렬 속도가 느려집니다.
일반 정렬 알고리즘은 일반적으로 평균 O(n µ log(n))이며, 구현에 따라 배열이 이미 정렬되어 있으면 O(n2)의 복잡성으로 이어질 수 있습니다.대신 삽입 위치를 직접 검색하면 O(log(n))의 복잡성만 있으므로 항상 훨씬 더 빠릅니다.
여기 로다쉬를 사용하는 버전이 있습니다.
const _ = require('lodash');
sortedArr.splice(_.sortedIndex(sortedArr,valueToInsert) ,0,valueToInsert);
참고: 정렬됨인덱스는 이진 검색을 수행합니다.
적은 수의 항목의 경우, 차이는 매우 작습니다.그러나 항목을 많이 삽입하거나 매우 큰 배열로 작업하는 경우 삽입할 때마다 .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);
};
다른 라이브러리를 사용할 수 있는 경우 로다시는 정렬된 기능을 제공합니다.인덱스 및 정렬된 LastIndex 함수. 이 함수는 다음을 대신하여 사용할 수 있습니다.while루프. 두 가지 잠재적인 단점은 1) 성능이 내 방법만큼 좋지 않다는 것과 2) 사용자 지정 비교기 기능을 수락하지 않고 (기본 비교기를 사용하여) 비교할 값을 얻는 방법만 수락한다는 것입니다.
다음은 몇 가지 생각입니다.첫째, 코드의 런타임이 진심으로 걱정된다면, 내장된 함수를 호출할 때 어떤 일이 일어나는지 반드시 알아야 합니다!Javascript에서 아래에서 위로는 모르겠지만, 스플라이스 함수의 빠른 구글이 이것을 반환했습니다. 이것은 당신이 매번 호출할 때마다 완전히 새로운 배열을 만들고 있다는 것을 나타내는 것 같습니다!그것이 실제로 중요한지는 모르겠지만, 확실히 효율성과 관련이 있습니다.저는 브르타뉴가 논평에서 이미 이것을 지적했지만, 당신이 선택한 배열 조작 기능은 확실히 유효합니다.
어쨌든, 문제를 실제로 해결하기 위해서요.
당신이 정렬하기를 원한다는 것을 읽었을 때, 저는 삽입 정렬을 사용하는 것이 첫 번째 생각입니다!정렬되거나 거의 정렬된 목록에서 선형 시간으로 실행되므로 편리합니다.어레이에는 거의 정렬된 요소가 1개만 있기 때문에 이는 거의 정렬된 것으로 간주됩니다(크기가 2 또는 3인 어레이는 제외되지만 이 시점에서는 c'mon입니다).자, 그런 종류를 구현하는 것은 그리 나쁘지는 않지만, 여러분이 처리하고 싶지 않을 수도 있는 번거로운 일입니다. 다시 말하지만, 자바스크립트에 대해서는 아는 것이 하나도 없고, 그것이 쉬울지 어려울지 아니면 어려울지도 모릅니다.이것은 당신의 룩업 기능의 필요성을 제거하고, 당신은 (브레튼이 제안한 대로) 그냥 밀어냅니다.
두 번째로, 당신의 "quicksort-esque" 검색 기능은 이진 검색 알고리즘인 것 같습니다!그것은 직관적이고 빠른 매우 좋은 알고리즘이지만, 한 가지 단점이 있습니다: 그것은 정확하게 구현하기 어렵기로 악명 높습니다.당신의 것이 맞는지 아닌지 감히 말할 수는 없지만(물론 그러길 바래요! :), 만약 당신이 그것을 사용하고 싶다면 조심하세요.
어쨌든 요약: 삽입 정렬과 함께 "push"를 사용하면 선형 시간에 작동하며(배열의 나머지 부분이 정렬되었다고 가정함), 지저분한 이진 검색 알고리즘 요구 사항을 방지할 수 있습니다.이것이 최선의 방법인지는 모르겠지만(배열의 기본 구현, 아마도 미친 내장 함수가 더 잘 수행할 수 있을 것이다, 누가 알겠는가). :) - 아고르.
다음은 이를 달성하기 위한 네 가지 알고리즘의 비교입니다. https://jsperf.com/sorted-array-insert-comparison/1
알고리즘
- 순진함: 나중에 누르고 정렬()하면 됩니다.
- 선형: 어레이 위에 반복하고 필요한 경우 삽입
- 이진 검색: https://stackoverflow.com/a/20352387/154329 에서 가져옵니다.
- "Quick Sort Like": 합성 제로의 정제된 솔루션(https://stackoverflow.com/a/18341744/154329)
순진함은 항상 끔찍합니다.어레이 크기가 작은 경우에는 나머지 3개가 크게 다르지 않지만, 어레이 크기가 큰 경우에는 마지막 2개가 단순한 선형 접근 방식을 능가합니다.
내가 생각할 수 있는 최고의 데이터 구조는 로그 시간 작업을 가능하게 하는 계층 구조로 연결된 목록의 삽입 속성을 유지하는 색인화된 건너뛰기 목록입니다.평균적으로 검색, 삽입 및 임의 접근 조회는 O(log n) 시간 내에 수행할 수 있습니다.
순서 통계 트리는 순위 함수를 사용하여 로그 시간 인덱싱을 활성화합니다.
랜덤 액세스가 필요하지 않지만 O(log n) 삽입 및 키 검색이 필요한 경우 어레이 구조를 무시하고 모든 종류의 이진 검색 트리를 사용할 수 있습니다.
사하는답변없다습니이용을 사용하는 .array.splice()평균 O(n) 시간이므로 효율적입니다.Google Chrome에서 array.splice()의 시간 복잡도는 얼마입니까?
다음은 이진 검색을 사용하여 항목을 찾은 다음 적절하게 삽입하는 기능입니다.
function binaryInsert(val, arr){
let mid,
len=arr.length,
start=0,
end=len-1;
while(start <= end){
mid = Math.floor((end + start)/2);
if(val <= arr[mid]){
if(val >= arr[mid-1]){
arr.splice(mid,0,val);
break;
}
end = mid-1;
}else{
if(val <= arr[mid+1]){
arr.splice(mid+1,0,val);
break;
}
start = mid+1;
}
}
return arr;
}
console.log(binaryInsert(16, [
5, 6, 14, 19, 23, 44,
35, 51, 86, 68, 63, 71,
87, 117
]));모든 항목을 다시 정렬하지 마십시오. 오버킬입니다.
삽입할 항목이 하나만 있는 경우 이진 검색을 사용하여 삽입할 위치를 찾을 수 있습니다.그런 다음 memcpy 등을 사용하여 나머지 항목을 대량 복사하여 삽입된 항목을 위한 공간을 확보합니다.이진 검색은 O(log n)이고 복사본은 O(n)이며 총 O(n + log n)입니다.위의 방법을 사용하여 삽입할 때마다 O(n log n)인 재 정렬을 수행합니다.
그게 중요한가요?k개의 원소를 랜덤하게 삽입한다고 가정합니다. 여기서 k = 1000입니다.정렬된 목록은 5000개 항목입니다.
Binary search + Move = k*(n + log n) = 1000*(5000 + 12) = 5,000,012 = ~5 million opsRe-sort on each = k*(n log n) = ~60 million ops
삽입할 k개의 항목이 언제든지 도착하면 검색+이동을 해야 합니다.그러나 정렬된 배열에 삽입할 k개의 항목 목록이 미리 주어지면 훨씬 더 잘 할 수 있습니다.k개의 항목을 이미 정렬된 n개의 배열과 별도로 정렬합니다.그런 다음 두 정렬된 배열을 동시에 아래로 이동하여 하나를 다른 배열로 병합하는 검색 정렬을 수행합니다. - 한 단계 병합 정렬 = klog k + n = 9965 + 5000 = ~15,000 ops
업데이트: 질문과 관련하여.
First method = binary search+move = O(n + log n).Second method = re-sort = O(n log n)정확하게 당신이 받고 있는 타이밍을 설명합니다.
사용자 지정 비교 방법을 사용하는 TypeScript 버전:
const { compare } = new Intl.Collator(undefined, {
numeric: true,
sensitivity: "base"
});
const insert = (items: string[], item: string) => {
let low = 0;
let high = items.length;
while (low < high) {
const mid = (low + high) >> 1;
compare(items[mid], item) > 0
? (high = mid)
: (low = mid + 1);
}
items.splice(low, 0, item);
};
사용:
const items = [];
insert(items, "item 12");
insert(items, "item 1");
insert(items, "item 2");
insert(items, "item 22");
console.log(items);
// ["item 1", "item 2", "item 12", "item 22"]
만약 당신의 첫 번째 코드가 버그가 없었다면, 제 추측으로는 JS에서 당신이 이 일을 하는 방법이었을 것입니다.내 말은;
- 바이너리 검색을 통해 삽입 인덱스 찾기
- 사용하다
splice삽입을 수행할 수 있습니다.
이것은 거의 항상 하향식 또는 상향식 선형 검색 및 삽입보다 2배 빠릅니다. domoarigato의 답변에서 언급한 것처럼 제가 매우 좋아했고 제 벤치마크에 대한 기초로 삼았습니다.push그리고.sort.
물론 대부분의 경우 실제 일부 개체에 대해 이 작업을 수행하고 있으며 여기서는 일부 개체를 포함하는 크기 100000의 배열에 대해 이 세 가지 사례에 대한 벤치마크 테스트를 생성했습니다.자유롭게 그것을 가지고 놀아요.
function insertElementToSorted(arr, ele, start=0,end=null) {
var n , mid
if (end == null) {
end = arr.length-1;
}
n = end - start
if (n%2 == 0) {
mid = start + n/2;
} else {
mid = start + (n-1)/2
}
if (start == end) {
return start
}
if (arr[0] > ele ) return 0;
if (arr[end] < ele) return end+2;
if (arr[mid] >= ele && arr[mid-1] <= ele) {
return mid
}
if (arr[mid] > ele && arr[mid-1] > ele) {
return insertElementToSorted(arr,ele,start,mid-1)
}
if (arr[mid] <= ele && arr[mid+1] >= ele) {
return mid + 1
}
if (arr[mid] < ele && arr[mid-1] < ele) {
return insertElementToSorted(arr,ele,mid,end)
}
if(arr[mid] < ele && arr[mid+1] < ele) {
console.log("mid+1", mid+1, end)
return insertElementToSorted(arr,ele,mid+1,end)
}
}
// Example
var test = [1,2,5,9, 10, 14, 17,21, 35, 38,54, 78, 89,102];
insertElementToSorted(test,6)
미래의 나에 대한 메모로서, 여기 또 다른 버전이 있습니다.findOrAddSorted코너 케이스와 초보적인 테스트를 위한 몇 가지 최적화와 함께.
// returns BigInt(index) if the item has been found
// or BigInt(index) + BigInt(MAX_SAFE_INTEGER) if it has been inserted
function findOrAddSorted(items, newItem) {
let from = 0;
let to = items.length;
let item;
// check if the array is empty
if (to === 0) {
items.push(newItem);
return BigInt(Number.MAX_SAFE_INTEGER);
}
// compare with the first item
item = items[0];
if (newItem === item) {
return 0;
}
if (newItem < item) {
items.splice(0, 0, newItem);
return BigInt(Number.MAX_SAFE_INTEGER);
}
// compare with the last item
item = items[to-1];
if (newItem === item) {
return BigInt(to-1);
}
if (newItem > item) {
items.push(newItem);
return BigInt(to) + BigInt(Number.MAX_SAFE_INTEGER);
}
// binary search
let where;
for (;;) {
where = (from + to) >> 1;
if (from >= to) {
break;
}
item = items[where];
if (item === newItem) {
return BigInt(where);
}
if (item < newItem) {
from = where + 1;
}
else {
to = where;
}
}
// insert newItem
items.splice(where, 0, newItem);
return BigInt(where) + BigInt(Number.MAX_SAFE_INTEGER);
}
// generate a random integer < MAX_SAFE_INTEGER
const generateRandomInt = () => Math.floor(Math.random() * Number.MAX_SAFE_INTEGER);
// fill the array with random numbers
const items = new Array();
const amount = 1000;
let i = 0;
let where = 0;
for (i = 0; i < amount; i++) {
where = findOrAddSorted(items, generateRandomInt());
if (where < BigInt(Number.MAX_SAFE_INTEGER)) {
break;
}
}
if (where < BigInt(Number.MAX_SAFE_INTEGER)) {
console.log(`items: ${i}, repeated at ${where}: ${items[Number(where)]}`)
}
else {
const at = Number(where - BigInt(Number.MAX_SAFE_INTEGER));
console.log(`items: ${i}, last insert at: ${at}: ${items[at]}`);
}
console.log(items);function insertOrdered(array, elem) {
let _array = array;
let i = 0;
while ( i < array.length && array[i] < elem ) {i ++};
_array.splice(i, 0, elem);
return _array;
}
언급URL : https://stackoverflow.com/questions/1344500/efficient-way-to-insert-a-number-into-a-sorted-array-of-numbers
'sourcecode' 카테고리의 다른 글
| PowerShell에서 파일 이름을 대량으로 변경하려면 어떻게 해야 합니까? (0) | 2023.08.22 |
|---|---|
| jQuery: 요소의 클래스와 ID를 동시에 선택하시겠습니까? (0) | 2023.08.22 |
| DESC 순서에 따라 그룹화하는 방법 (0) | 2023.08.22 |
| 마리아드브는 짐을 싣고 몇 분 후에 추락합니다.서버가 "스냅샷"에서 복원된 후 발생했습니다. (0) | 2023.08.22 |
| jQuery 셀렉터에서 $(이것)를 제외하려면 어떻게 해야 합니까? (0) | 2023.08.22 |