Cara yang efisien untuk memasukkan angka ke dalam array angka yang diurutkan?

Saya memiliki array JavaScript yang diurutkan, dan ingin memasukkan satu item lagi ke dalam array sehingga array yang dihasilkan tetap diurutkan. Saya pasti bisa menerapkan fungsi penyisipan quicksort-style sederhana:

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

[PERINGATAN] kode ini memiliki bug ketika mencoba memasukkan ke awal array, misalnya insert(2, [3, 7 ,9]) menghasilkan salah [3, 2, 7, 9].

Namun, saya perhatikan bahwa implementasi fungsi Array.sort berpotensi melakukan ini untuk saya, dan secara native:

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

Apakah ada alasan bagus untuk memilih implementasi pertama dari yang kedua?

Sunting : Perhatikan bahwa untuk kasus umum, penyisipan O (log (n)) (seperti yang diterapkan pada contoh pertama) akan lebih cepat daripada algoritma penyortiran umum; namun ini belum tentu berlaku untuk JavaScript pada khususnya. Perhatikan bahwa:

• Kasus terbaik untuk beberapa algoritma penyisipan adalah O (n), yang masih sangat berbeda dari O (log (n)), tetapi tidak seburuk O (n log (n)) seperti yang disebutkan di bawah ini. Itu akan datang ke algoritma pengurutan tertentu yang digunakan (lihat implementasi Javascript Array.sort? )
• Metode pengurutan dalam JavaScript adalah fungsi asli, sehingga berpotensi menyadari manfaat besar - O (log (n)) dengan koefisien yang sangat besar masih bisa jauh lebih buruk daripada O (n) untuk set data berukuran cukup.

Sama seperti satu titik data, untuk tendangan saya menguji ini dengan memasukkan 1000 elemen acak ke dalam array 100.000 angka pra-diurutkan menggunakan dua metode menggunakan Chrome pada Windows 7:

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

Jadi, setidaknya pada pengaturan ini, metode asli tidak menebusnya. Ini berlaku bahkan untuk set data kecil, memasukkan 100 elemen ke dalam array 1000:

First Method:
1 milliseconds
Second Method:
34 milliseconds

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

Pertanyaan yang sangat bagus dan luar biasa dengan diskusi yang sangat menarik! Saya juga menggunakan Array.sort()fungsi setelah mendorong satu elemen dalam array dengan ribuan objek.

Saya harus memperluas locationOffungsi Anda untuk tujuan saya karena memiliki objek yang kompleks dan karena itu kebutuhan untuk fungsi perbandingan seperti di 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;
};

Ada bug dalam kode Anda. Itu harus membaca:

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

Tanpa perbaikan ini, kode tidak akan pernah bisa menyisipkan elemen di awal array.

Saya tahu ini adalah pertanyaan lama yang sudah memiliki jawaban, dan ada sejumlah jawaban yang layak lainnya. Saya melihat beberapa jawaban yang mengusulkan agar Anda dapat menyelesaikan masalah ini dengan mencari indeks penyisipan yang benar di O (log n) - Anda bisa, tetapi Anda tidak dapat memasukkan waktu itu, karena array perlu disalin sebagian untuk membuat ruang.

Intinya: Jika Anda benar-benar membutuhkan O (log n) menyisipkan dan menghapus ke dalam array yang diurutkan, Anda memerlukan struktur data yang berbeda - bukan sebuah array. Anda harus menggunakan B-Tree . Keuntungan kinerja yang akan Anda dapatkan dari menggunakan B-Tree untuk kumpulan data yang besar, akan jauh dari perbaikan yang ditawarkan di sini.

Jika Anda harus menggunakan array. Saya menawarkan kode berikut, berdasarkan pada jenis penyisipan, yang berfungsi, jika dan hanya jika array sudah diurutkan. Ini berguna untuk kasing ketika Anda harus menggunakan setelah setiap sisipan:

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

Itu harus beroperasi di O (n), yang saya pikir adalah yang terbaik yang dapat Anda lakukan. Akan lebih baik jika js mendukung banyak tugas. inilah contoh untuk bermain:

Memperbarui:

ini mungkin lebih cepat:

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

Tautan JS Bin yang diperbarui

Fungsi penyisipan Anda mengasumsikan bahwa array yang diberikan diurutkan, itu mencari langsung ke lokasi di mana elemen baru dapat dimasukkan, biasanya dengan hanya melihat beberapa elemen dalam array.

Fungsi sortir umum dari suatu array tidak dapat menggunakan shortcut ini. Jelas itu setidaknya harus memeriksa semua elemen dalam array untuk melihat apakah mereka sudah dipesan dengan benar. Fakta ini saja membuat jenis umum lebih lambat daripada fungsi penyisipan.

Algoritma pengurutan generik biasanya pada rata-rata O (n ⋅ log (n)) dan tergantung pada implementasinya, ini mungkin merupakan kasus terburuk jika array sudah diurutkan, yang mengarah ke kompleksitas O (n ² ) . Mencari posisi penyisipan secara langsung malah hanya memiliki kompleksitas O (log (n)) , sehingga akan selalu jauh lebih cepat.

Untuk sejumlah kecil item, perbedaannya cukup sepele. Namun, jika Anda memasukkan banyak item, atau bekerja dengan array yang sangat besar, memanggil .sort () setelah setiap penyisipan akan menyebabkan overhead yang sangat besar.

Saya akhirnya menulis fungsi pencarian / masukkan biner yang cukup apik untuk tujuan yang tepat ini, jadi saya pikir saya akan membagikannya. Karena menggunakan whileloop alih-alih rekursi, tidak ada yang terdengar untuk panggilan fungsi tambahan, jadi saya pikir kinerjanya akan lebih baik daripada salah satu metode yang diposting sebelumnya. Dan itu mengemulasi Array.sort()komparator default secara default, tetapi menerima fungsi komparator kustom jika diinginkan.

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

Jika Anda terbuka untuk menggunakan perpustakaan lain, lodash menyediakan sortedIndex dan sortedLastIndex fungsi, yang dapat digunakan di tempat whilelingkaran. Dua kelemahan potensial adalah 1) kinerja tidak sebagus metode saya (saya pikir saya tidak yakin seberapa buruk itu) dan 2) tidak menerima fungsi komparator kustom, hanya metode untuk mendapatkan nilai untuk membandingkan nilai (menggunakan pembanding default, saya kira).

Berikut adalah beberapa pemikiran: Pertama, jika Anda benar-benar khawatir tentang runtime kode Anda, pastikan untuk mengetahui apa yang terjadi ketika Anda memanggil fungsi bawaan! Saya tidak tahu dari bawah dalam javascript, tetapi google cepat dari fungsi sambatan mengembalikan ini , yang tampaknya menunjukkan bahwa Anda membuat seluruh array baru setiap panggilan! Saya tidak tahu apakah itu benar-benar penting, tetapi tentu saja terkait dengan efisiensi. Saya melihat bahwa Breton, dalam komentar, telah menunjukkan hal ini, tetapi tentu saja berlaku untuk fungsi manipulasi array yang Anda pilih.

Bagaimanapun, untuk benar-benar menyelesaikan masalah.

Ketika saya membaca bahwa Anda ingin menyortir, pikiran pertama saya adalah menggunakan jenis penyisipan! . Ini berguna karena berjalan dalam waktu linier pada daftar yang diurutkan, atau hampir diurutkan . Karena array Anda hanya akan memiliki 1 elemen yang rusak, yang diperhitungkan sebagai hampir diurutkan (kecuali, baik, array ukuran 2 atau 3 atau apa pun, tetapi pada titik itu, ayo). Sekarang, menerapkan semacam itu tidak terlalu buruk, tetapi itu merepotkan Anda mungkin tidak ingin berurusan dengan, dan sekali lagi, saya tidak tahu apa-apa tentang javascript dan apakah itu akan mudah atau sulit atau yang lainnya. Ini menghilangkan kebutuhan untuk fungsi pencarian Anda, dan Anda hanya mendorong (seperti yang disarankan Breton).

Kedua, fungsi pencarian "quicksort-esque" Anda tampaknya merupakan algoritma pencarian biner ! Ini adalah algoritma yang sangat bagus, intuitif dan cepat, tetapi dengan satu tangkapan: sangat sulit untuk diimplementasikan dengan benar. Saya tidak akan berani mengatakan apakah milik Anda benar atau tidak (saya harap, tentu saja! :)), tetapi berhati-hatilah jika Anda ingin menggunakannya.

Ringkasnya, ringkasan: menggunakan "push" dengan jenis penyisipan akan bekerja dalam waktu linier (dengan asumsi seluruh array diurutkan), dan menghindari persyaratan algoritma pencarian biner yang berantakan. Saya tidak tahu apakah ini cara terbaik (implementasi array yang mendasarinya, mungkin fungsi built-in yang gila lebih baik, siapa tahu), tetapi tampaknya masuk akal bagi saya. :) - Agor.

Berikut ini adalah perbandingan dari empat algoritma berbeda untuk mencapai hal ini: https://jsperf.com/sorted-array-insert-comparison/1

Algoritma

• Naif: cukup tekan dan urutkan () sesudahnya
• Linear: iterate over array dan masukkan yang sesuai
• Pencarian Biner: diambil dari https://stackoverflow.com/a/20352387/154329
• "Quick Sort Like": solusi halus dari syntheticzero ( https://stackoverflow.com/a/18341744/154329 )

Naif selalu mengerikan. Tampaknya untuk ukuran array kecil, tiga lainnya tidak terlalu berbeda, tetapi untuk array yang lebih besar, 2 terakhir mengungguli pendekatan linier sederhana.

Ini versi yang menggunakan lodash.

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

catatan: diurutkanIndex melakukan pencarian biner.

Struktur data terbaik yang dapat saya pikirkan adalah daftar lompatan yang diindeks yang mempertahankan properti penyisipan daftar terkait dengan struktur hierarki yang memungkinkan operasi waktu log. Rata-rata, pencarian, penyisipan, dan pencarian akses acak dapat dilakukan dalam waktu O (log n).

Sebuah pohon agar statistik memungkinkan log waktu pengindeksan dengan fungsi pangkat.

Jika Anda tidak memerlukan akses acak tetapi Anda membutuhkan penyisipan O (log n) dan mencari kunci, Anda dapat membuang struktur array dan menggunakan segala jenis pohon pencarian biner .

Tidak ada jawaban yang menggunakan array.splice()yang efisien sama sekali karena itu adalah rata-rata waktu O (n). Apa kompleksitas waktu array.splice () di Google Chrome?

Inilah fungsi saya, menggunakan pencarian biner untuk menemukan item dan kemudian menyisipkan dengan tepat:

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

Jangan mengurutkan ulang setelah setiap item, itu berlebihan ..

Jika hanya ada satu item untuk disisipkan, Anda dapat menemukan lokasi untuk disisipkan menggunakan pencarian biner. Kemudian gunakan memcpy atau mirip dengan menyalin sebagian besar item yang tersisa untuk membuat ruang untuk yang dimasukkan. Pencarian biner adalah O (log n), dan salinannya adalah O (n), memberikan total O (n + log n). Dengan menggunakan metode di atas, Anda melakukan pengurutan ulang setelah setiap penyisipan, yaitu O (n log n).

Apakah itu penting? Katakanlah Anda memasukkan elemen k secara acak, di mana k = 1000. Daftar yang diurutkan adalah 5000 item.

• 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

Jika k item yang dimasukkan tiba kapan saja, maka Anda harus melakukan pencarian + pindah. Namun, jika Anda diberi daftar item k untuk disisipkan ke dalam array yang diurutkan - sebelumnya - maka Anda dapat melakukan lebih baik lagi. Sortir item k, secara terpisah dari n array yang sudah diurutkan. Kemudian lakukan pemindaian, di mana Anda memindahkan kedua array yang diurutkan secara bersamaan, menggabungkan satu ke yang lain. - Sortir Gabung satu langkah = k log k + n = 9965 + 5000 = ~ 15.000 ops

Pembaruan: Mengenai pertanyaan Anda.
First method = binary search+move = O(n + log n). Second method = re-sort = O(n log n)Menjelaskan tepat waktu yang Anda dapatkan.

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