Как сохранить Javascript массив отсортирован, без сортировки его

Question

У меня есть приложение Node.js, где я должен очень часто следующие вещи: - проверить, если массив частности уже содержит определенный элемент - если элемент существует, обновить его - если элемент не существует, толкать его в массив, а затем отсортировать его с помощью подчеркивания _.sortBy

для проверки, если элемент уже существует в массиве, я использую эту бинарную функцию поиска: http://oli.me.uk/2013/06/08/searching-javascript-arrays-with-a-binary-search/

в таким образом, когда размер массива растет, сортировка становится медленнее и медленнее. Я предполагаю, что размер массива может вырасти до 20 000 элементов на пользователя. И в итоге тысячи пользователей будут. Массив сортируется по ключу, что довольно короткая строка. При необходимости он может быть преобразован в целое.

Итак, мне понадобится лучший способ сохранить отсортированный массив, вместо сортировки его каждый раз, когда на него нажимается новый элемент.

Итак, мой вопрос заключается в том, как мне/мне следует изменить алгоритм бинарного поиска, который я использую, чтобы включить меня в получить индекс массива, в который должен быть помещен новый элемент, если он еще не существует в массиве ? Или какие другие возможности могли бы достичь этого. Конечно, я мог бы использовать какой-то цикл, который начинался бы с самого начала и проходил через массив, пока он не найдет место для нового элемента.

Все данные хранятся в MongoDB.

Другими словами, я хотел бы сохранить сортировку массива, не сортируя ее каждый раз при нажатии нового элемента.

Answer 1

Если ваш массив уже отсортирован, и вы хотите вставить элемент, чтобы его сортировать, вам нужно вставить его в определенное место в массиве. К счастью массивов есть метод, который может сделать это: Array.prototype.splice

Итак, как только вы получите индекс вам нужно вставить в (вы должны получить простую модификацию в ваш бинарный поиск), вы можете сделать:

myArr.splice(myIndex,0,myObj); 
// myArr your sorted array 
// myIndex the index of the first item larger than the one you want to insert 
// myObj the item you want to insert 

EDIT: автор вашего двоичного поиска кода имеет ту же идею:

Так что если вы хотели, чтобы вставить значение, и хотел бы знать, где вы должны положить его, вы можете запустить функцию и использовать возвращенный номер объединить значение в массив. Source

Answer 2

Легко изменить эту binaryIndexOf функцию, чтобы вернуть индекс следующего элемента, когда не найдено ни одного совпадения:

function binaryFind(searchElement) { 
    'use strict'; 

    var minIndex = 0; 
    var maxIndex = this.length - 1; 
    var currentIndex; 
    var currentElement; 

    while (minIndex <= maxIndex) { 
    currentIndex = (minIndex + maxIndex)/2 | 0; 
    currentElement = this[currentIndex]; 

    if (currentElement < searchElement) { 
     minIndex = currentIndex + 1; 
    } 
    else if (currentElement > searchElement) { 
     maxIndex = currentIndex - 1; 
    } 
    else { 
     return { // Modification 
     found: true, 
     index: currentIndex 
     }; 
    } 
    }  

    return { // Modification 
    found: false, 
    index: currentElement < searchElement ? currentIndex + 1 : currentIndex 
    }; 
} 

Итак, теперь он возвращает объекты, как:

{found: false, index: 4} 

где index - это индекс найденного элемента или следующий.

Итак, теперь вставка нового элемента будет выглядеть следующим образом:

var res = binaryFind.call(arr, element); 
if (!res.found) arr.splice(res.index, 0, element); 

Теперь вы можете добавить binaryFind к Array.prototype наряду с некоторыми помощниками для добавления новых элементов:

Array.prototype.binaryFind = binaryFind; 

Array.prototype.addSorted = function(element) { 
    var res = this.binaryFind(element); 
    if (!res.found) this.splice(res.index, 0, element); 
} 

Answer 3

Я знаю, что это ответ на старый вопрос, но следующее очень просто, используя javascripts array.splice().

function inOrder(arr, item) { 
    /* Insert item into arr keeping low to high order */ 

    let ix = 0; 
    while (ix < arr.length) { 
     //console.log('ix',ix); 
     if (item < arr[ix]) { break; } 
     ix++; 
    } 

    //console.log(' insert:', item, 'at:',ix); 
    arr.splice(ix,0,item); 
    return arr 
} 

Заказ может быть изменен на высокий к низкому переворачиванию теста