Moyen efficace d'insérer un nombre dans un tableau trié de chiffres?

Question

J'ai une triés tableau JavaScript, et souhaitez insérer un élément de plus dans le tableau tel que le tableau qui en résulte reste triés. Je pourrais certainement de mettre en œuvre un simple quicksort style d'insertion de la fonction:

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

Cependant, j'ai remarqué que les implémentations de la Matrice.fonction de tri peut-être de faire cela pour moi, et nativement:

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

Est-il une bonne raison de choisir la première mise en œuvre au cours de la seconde?

Edit: à Noter que pour le cas général, un O(log(n)) insertion (tel que mis en œuvre dans le premier exemple) sera plus rapide qu'un générique algorithme de tri; toutefois, ce n'est pas forcément le cas de JavaScript en particulier. Notez que:

• Dans le meilleur des cas pour plusieurs d'insertion des algorithmes est O(n), qui est encore nettement différent de O(log(n)), mais pas tout à fait aussi mauvais que O(n log(n)) comme indiqué ci-dessous. Il allait descendre pour le particulier algorithme de tri utilisé (voir Tableau Javascript.trier la mise en œuvre?)
• La méthode de tri en JavaScript est une fonction native, donc potentiellement de réaliser d'énormes avantages -- O(log(n)) avec un grand coefficient peut être encore pire que O(n) de taille raisonnable, des ensembles de données.

Answer 1

Simple (Démo):

function sortedIndex(array, value, key) {
    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;
}

Answer 2

Tout comme un point de données unique, pour le plaisir j'ai testé cette insertion de 1000 aléatoire des éléments dans un tableau de 100 000 pré-trier les nombres en utilisant les deux méthodes à l'aide de Chrome sur Windows 7:

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

Donc, au moins sur cette installation, la méthode native ne fait pas pour elle. Cela est vrai même pour de petits ensembles de données, insertion de 100 éléments dans un tableau de 1000:

First Method:
1 milliseconds
Second Method:
34 milliseconds

Answer 3

Très bon et remarquable question avec une discussion très intéressante! J'ai aussi été à l'aide de l' Array.sort() fonction après avoir poussé un seul élément dans un tableau avec quelques milliers d'objets.

J'ai dû prolonger votre locationOf fonction de mon objectif parce que d'avoir des objets complexes et, par conséquent, la nécessité d'une fonction de comparaison comme en 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 the above calculation

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

Answer 4

Il y a un bug dans votre code. Il faut lire:

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

Sans ce correctif, le code ne sera jamais en mesure d'insérer un élément au début du tableau.

Answer 5

Votre insertion fonction suppose que le tableau est trié, il recherche directement à l'emplacement où le nouvel élément peut être inséré, généralement simplement en regardant quelques-uns des éléments dans le tableau.

Le général la fonction de tri d'un tableau ne peut pas prendre ces raccourcis. Évidemment, elle a au moins pour inspecter tous les éléments du tableau pour voir si elles sont déjà classées correctement. Ce seul fait rend le tri général plus lent que l'insertion de la fonction.

Un générique algorithme de tri est généralement en moyenne O(n*log(n()) et en fonction de la mise en œuvre, il pourrait en fait être le pire des cas, si le tableau est déjà trié, conduisant à une complexité de O(n^2). Directement à la recherche de la position d'insertion, au contraire, a tout juste une complexité de O(log(n)), de sorte qu'il sera toujours beaucoup plus rapide.