Skuteczny sposób wstawiania liczby do posortowanej tablicy liczb?

Mam posortowaną tablicę JavaScript i chcę wstawić jeszcze jeden element do tablicy, tak aby wynikowa tablica pozostała posortowana. Z pewnością mógłbym zaimplementować prostą funkcję wstawiania w stylu quicksort:

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));

[OSTRZEŻENIE] ten kod ma błąd, gdy próba wstawienia na początek tablicy, np. insert(2, [3, 7 ,9]) Daje niepoprawne [3, 2, 7, 9].

Jednak zauważyłem, że implementacje funkcji Array.sort mogą potencjalnie zrobić to dla mnie i natywnie:

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));

Czy jest dobry powód, aby wybrać pierwszą implementację zamiast drugiej?

Edycja : Zauważ, że w ogólnym przypadku wstawienie O (log (n)) (jak zaimplementowano w pierwszym przykładzie) będzie szybsze niż ogólny algorytm sortowania; jednakże niekoniecznie ma to miejsce w szczególności w przypadku JavaScript. Zauważ, że:

• Najlepszym przypadkiem dla kilku algorytmów wstawiania jest O (n), które nadal znacznie różni się od O (log (n)), ale nie tak źle jak O (n log (n)), jak wspomniano poniżej. Sprowadziłoby się to do konkretnego użytego algorytmu sortowania (patrz implementacja Javascript Array.sort? )
• Metoda sortowania w JavaScript jest funkcją natywną, więc potencjalnie przynosząca ogromne korzyści - O (log (n)) z ogromnym współczynnikiem może nadal być znacznie gorsza niż O (n) dla zbiorów danych o rozsądnych rozmiarach.

Podobnie jak pojedynczy punkt danych, dla wykopów przetestowałem to, wstawiając 1000 losowych elementów do tablicy 100000 wstępnie posortowanych liczb przy użyciu dwóch metod w przeglądarce Chrome w systemie Windows 7:

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

Tak więc, przynajmniej w tej konfiguracji, metoda natywna tego nie rekompensuje. Dzieje się tak nawet w przypadku małych zestawów danych, wstawiania 100 elementów do tablicy 1000:

First Method:
1 milliseconds
Second Method:
34 milliseconds

Proste ( Demo ):

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;
}

Bardzo dobre i niezwykłe pytanie z bardzo interesującą dyskusją! Używałem również tej Array.sort()funkcji po wypchnięciu pojedynczego elementu w tablicy z kilkoma tysiącami obiektów.

Musiałem rozszerzyć twoją locationOffunkcję dla swoich celów ze względu na złożone obiekty, a zatem potrzebę funkcji porównującej, takiej jak 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;
};

W Twoim kodzie jest błąd. Powinien brzmieć:

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);
  }
}

Bez tej poprawki kod nigdy nie będzie mógł wstawić elementu na początku tablicy.

Wiem, że to stare pytanie, na które już jest odpowiedź, i istnieje wiele innych przyzwoitych odpowiedzi. Widzę kilka odpowiedzi, które sugerują, że możesz rozwiązać ten problem, wyszukując poprawny indeks wstawiania w O (log n) - możesz, ale nie możesz wstawić w tym czasie, ponieważ tablica musi być częściowo skopiowana, aby zrobić przestrzeń.

Konkluzja: Jeśli naprawdę potrzebujesz wstawiania i usuwania O (log n) do posortowanej tablicy, potrzebujesz innej struktury danych - nie tablicy. Powinieneś użyć B-Tree . Wzrost wydajności, który uzyskasz, korzystając z B-Tree dla dużego zestawu danych, przyćmiewa wszelkie oferowane tutaj ulepszenia.

Jeśli musisz użyć tablicy. Oferuję następujący kod, oparty na sortowaniu przez wstawianie, który działa wtedy i tylko wtedy, gdy tablica jest już posortowana. Jest to przydatne w przypadku, gdy musisz uciekać się po każdej wkładce:

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;
}

Powinien działać w O (n), co moim zdaniem jest najlepsze, co możesz zrobić. Byłoby ładniej, gdyby js obsługiwał wielokrotne przypisywanie. oto przykład do zabawy:

Aktualizacja:

to może być szybsze:

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;
}

Zaktualizowany link JS Bin

Twoja funkcja wstawiania zakłada, że ​​podana tablica jest posortowana, wyszukuje bezpośrednio lokalizację, w której można wstawić nowy element, zwykle po prostu patrząc na kilka elementów w tablicy.

Ogólna funkcja sortowania tablicy nie może przyjąć tych skrótów. Oczywiście musi przynajmniej sprawdzić wszystkie elementy w tablicy, aby zobaczyć, czy są już poprawnie uporządkowane. Już sam ten fakt sprawia, że ​​ogólne sortowanie jest wolniejsze niż funkcja wstawiania.

Ogólny algorytm sortowania ma zwykle średnią wartość O (n ⋅ log (n)) iw zależności od implementacji może to być w rzeczywistości najgorszy przypadek, jeśli tablica jest już posortowana, co prowadzi do złożoności O (n ² ) . Zamiast tego bezpośrednie wyszukiwanie pozycji wstawienia ma tylko złożoność O (log (n)) , więc zawsze będzie znacznie szybsze.

W przypadku niewielkiej liczby przedmiotów różnica jest dość trywialna. Jednakże, jeśli wstawiasz dużo elementów lub pracujesz z bardzo dużą tablicą, wywołanie funkcji .sort () po każdym wstawieniu spowoduje ogromne obciążenie.

Skończyło się na napisaniu całkiem zręcznej funkcji wyszukiwania / wstawiania plików binarnych właśnie w tym celu, więc pomyślałem, że się nią podzielę. Ponieważ whilezamiast rekurencji używa pętli, nie ma podsłuchiwania dodatkowych wywołań funkcji, więc myślę, że wydajność będzie nawet lepsza niż w przypadku każdej z pierwotnie opublikowanych metod. I domyślnie emuluje domyślny Array.sort()komparator, ale w razie potrzeby akceptuje niestandardową funkcję komparatora.

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);
};

Jeśli jesteś otwarty na używanie innych bibliotek, lodash udostępnia funkcje sortIndex i sortLastIndex , których można użyć zamiast whilepętli. Dwie potencjalne wady to 1) wydajność nie jest tak dobra jak moja metoda (myślę, że nie jestem pewien, o ile jest gorsza) i 2) nie akceptuje niestandardowej funkcji komparatora, a jedynie metodę uzyskiwania wartości do porównania (zakładam, że używam domyślnego komparatora).

Oto kilka przemyśleń: Po pierwsze, jeśli naprawdę martwisz się o środowisko wykonawcze swojego kodu, upewnij się, że wiesz, co się dzieje, gdy wywołujesz funkcje wbudowane! Nie wiem od góry w javascript, ale szybkie wygooglowanie funkcji splice zwróciło to , co wydaje się wskazywać, że tworzysz zupełnie nową tablicę przy każdym wywołaniu! Nie wiem, czy to rzeczywiście ma znaczenie, ale na pewno ma to związek z wydajnością. Widzę, że Breton już w komentarzach zwrócił na to uwagę, ale z pewnością ma to zastosowanie do dowolnej wybranej funkcji manipulowania tablicami.

W każdym razie, aby faktycznie rozwiązać problem.

Kiedy przeczytałem, że chcesz posortować, moją pierwszą myślą jest użycie sortowania przez wstawianie! . Jest to przydatne, ponieważ działa w czasie liniowym na posortowanych lub prawie posortowanych listach . Ponieważ twoje tablice będą miały tylko 1 nieprawidłowy element, liczy się to jako prawie posortowane (z wyjątkiem, no cóż, tablic o rozmiarze 2 lub 3 lub cokolwiek innego, ale w tym momencie daj spokój). Wdrożenie sortowania nie jest takie złe, ale jest to kłopot, z którym możesz nie chcieć sobie radzić, i znowu nie wiem nic o javascript i czy będzie to łatwe, trudne, czy co tam. Eliminuje to potrzebę korzystania z funkcji wyszukiwania i po prostu naciskasz (jak sugerował Breton).

Po drugie, twoja funkcja wyszukiwania „quicksort-esque” wydaje się być binarnym algorytmem wyszukiwania ! To bardzo fajny algorytm, intuicyjny i szybki, ale z jednym haczykiem: notorycznie trudno go poprawnie zaimplementować. Nie ośmielę się powiedzieć, czy twoje jest poprawne, czy nie (mam nadzieję, że tak! :)), ale bądź ostrożny, jeśli chcesz go użyć.

W każdym razie, podsumowanie: użycie "push" z sortowaniem przez wstawianie będzie działać w czasie liniowym (zakładając, że reszta tablicy jest posortowana) i pozwoli uniknąć bałaganu w wymaganiach algorytmu wyszukiwania binarnego. Nie wiem, czy to najlepszy sposób (podstawowa implementacja tablic, może szalona wbudowana funkcja robi to lepiej, kto wie), ale wydaje mi się to rozsądne. :) - Agor.

Oto porównanie czterech różnych algorytmów służących do osiągnięcia tego: https://jsperf.com/sorted-array-insert-comparison/1

Algorytmy

• Naiwny: po prostu wciśnij i posortuj () później
• Liniowy: iteruj po tablicy i wstaw w razie potrzeby
• Wyszukiwanie binarne: pobrane z https://stackoverflow.com/a/20352387/154329
• „Quick Sort Like”: dopracowane rozwiązanie od syntheticzero ( https://stackoverflow.com/a/18341744/154329 )

Naiwność jest zawsze okropna. Wydaje się, że w przypadku małych rozmiarów tablic pozostałe trzy nie różnią się zbytnio, ale w przypadku większych tablic ostatnie 2 przewyższają proste podejście liniowe.

Oto wersja wykorzystująca lodash.

const _ = require('lodash');
sortedArr.splice(_.sortedIndex(sortedArr,valueToInsert) ,0,valueToInsert);

uwaga: sortIndex wykonuje wyszukiwanie binarne.

Najlepszą strukturą danych, o jakiej przychodzi mi do głowy, jest indeksowana lista pomijania, która zachowuje właściwości wstawiania połączonych list ze strukturą hierarchiczną, która umożliwia operacje w czasie rejestrowania. Przeciętnie wyszukiwanie, wstawianie i wyszukiwanie dostępu swobodnego można przeprowadzić w czasie O (log n).

Drzewo Kolejność statystyka pozwala dziennika czasu indeksowania z funkcji rankingu.

Jeśli nie potrzebujesz dostępu swobodnego, ale potrzebujesz wstawienia O (log n) i wyszukania kluczy, możesz porzucić strukturę tablicy i użyć dowolnego rodzaju drzewa wyszukiwania binarnego .

Żadna z odpowiedzi nie array.splice()jest w ogóle skuteczna, ponieważ jest to średni czas O (n). Jaka jest złożoność czasowa funkcji array.splice () w przeglądarce Google Chrome?

Oto moja funkcja, używa wyszukiwania binarnego, aby znaleźć element, a następnie odpowiednio wstawia:

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
 ]));

Nie sortuj ponownie po każdym elemencie, to przesada ...

Jeśli jest tylko jeden element do wstawienia, możesz znaleźć lokalizację do wstawienia za pomocą wyszukiwania binarnego. Następnie użyj memcpy lub czegoś podobnego, aby zbiorczo skopiować pozostałe elementy, aby zrobić miejsce na wstawiony. Wyszukiwanie binarne to O (log n), a kopia to O (n), co daje łącznie O (n + log n). Korzystając z powyższych metod, wykonujesz ponowne sortowanie po każdym wstawieniu, czyli O (n log n).

Czy to ma znaczenie? Powiedzmy, że losowo wstawiasz k elementów, gdzie k = 1000. Posortowana lista zawiera 5000 elementów.

• Binary search + Move = k*(n + log n) = 1000*(5000 + 12) = 5,000,012 = ~5 million ops
• Re-sort on each = k*(n log n) = ~60 million ops

Jeśli k elementów do wstawienia pojawi się kiedykolwiek, musisz wykonać wyszukiwanie + przesuń. Jeśli jednak otrzymasz listę k elementów do wstawienia do posortowanej tablicy - z wyprzedzeniem - możesz zrobić jeszcze lepiej. Sortuj k elementów oddzielnie od już posortowanej tablicy n. Następnie wykonaj sortowanie ze skanowaniem, w którym przesuniesz w dół obie posortowane tablice jednocześnie, scalając jedną w drugą. - Jednostopniowe sortowanie scalające = k log k + n = 9965 + 5000 = ~ 15 000 operacji

Aktualizacja: jeśli chodzi o twoje pytanie.
First method = binary search+move = O(n + log n). Second method = re-sort = O(n log n)Dokładnie wyjaśnia, jakie czasy otrzymujesz.

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;
}