JavaScript: оптимизация сортировки массивов

Question

У меня есть массив JavaScript с вложенным объектом для ex: [{id:1, position: 1}, {id:2, position: 2}, {id:3, position: 3}, {id:4, position: 4}, {id:7, position: 7}, {id:5, position: 5},{id:6, position: 6}]. Это всего лишь пример, на самом деле у меня есть массив в моем приложении, содержащий 100 записей. И я пытаюсь сортировать массив с методом сортировки массива JavaScript. Пусть говорят, что имя массива является туАггау, так что я делаю что-то, как показано ниже:

myArray.sort(function(a, b) { 
    return a.position- b.position; 
}); 

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

Answer 1

Вы можете создавать свои собственные алгоритмы сортировки, которые очень эффективны, такие как QuickSort и MergeSort.

In this interesting article Вы найдете сравнение между сортировкой javascript() и реализацией MergeSort. Я рекомендую вам узнать больше о sorting algorithms и найти тот, который он больше адаптирует к вашей проблеме.

Answer 2

В одном из ваших последних комментариев вы упомянули, что данные поступают поэтапно, а не все одновременно. Но Array.prototype.sort() должен каждый раз перерабатывать весь массив, хотя он в основном уже отсортирован; только несколько элементов находятся вне того места, где они должны быть.

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

Вот базовая реализация алгоритма.

/** 
* Compare two items as though they were strings. 
* 
* This is like the default comparison for Array.prototype.sort() 
* 
* @param {*} a The first item 
* @param {*} b The second item 
* 
* @return -1 if a is less, 1 is b is less, 0 otherwise 
*/ 
function compareStrings(a, b) { 
    var sa = String(a), 
     sb = String(b); 

    if (sa < sb) { 
     return -1; 
    } 
    if (sa > sb) { 
     return 1; 
    } 
    return 0; 
} 

/** 
* Insert a new item into a sorted array. 
* 
* The compareFunction callback function works as for the analogous argument 
* in Array.prototype.sort(). Leave unspecified to compare lexically. 
* 
* @param {Array}  data   A sorted array, into which to put this item 
* @param {*}   newItem   The item to add to the data. 
* @param {Function=} compareFunction Optional comparison function. 
*/ 
function arrayInsert(data, newItem, compareFunction) { 
    var stop = data.length, 
     i = 0; 

    compareFunction = compareFunction || compareStrings; 
    while (i < stop) { 
     if (compareFunction(newItem, data[i]) < 0) { 
      data.splice(i, 0, newItem); 
      return; 
     } 
     i += 1; 
    } 
    // If we got this far, then this should be the last item. 
    data.push(newItem); 
} 

Весь массив еще должен быть отсортирован раз, когда страница загружается, и вы не должны использовать вставки рода для этого (это было бы лучше, если вы получаете сервер для отправки вам уже отсортированных данных, но если вы не можете этого сделать, используйте вместо этого обычную функцию Array.prototype.sort). Затем, когда вы получите новые данные, вызовите arrayInsert(data, newItem, /* your comparison function */) один раз для каждого нового элемента данных, который вы получите. Это должно ускорить процесс.

Если это все еще слишком медленно, вы можете поместить свои новые элементы данных в очередь и добавить короткий таймер на страницу. Каждые несколько миллисекунд этот таймер проверяет очередь, и если есть какие-то элементы ожидания, он добавляет один из них в массив. На самом деле это не ускорит работу (на самом деле, это сделает их немного медленнее), но страница больше не должна замерзать.

Answer 3

Вместо того, чтобы нажимать, а затем сортировать, я предлагаю использовать двоичный поиск, чтобы определить, по какому индексу следует вставить новый объект.

В следующем коде нет накладных расходов, так как нет вызовов функций.

Также есть переменная iteration, которая служит только свидетелем, ее можно выбросить.

Я сделал jsfiddle следующего кода

Предполагая, что ваш a является уже отсортирован и содержит UNIQUE позиции вы можете сделать это

// THIS SECTION IS ONLY THERE TO SUIT YOUR CONSTRAINTS (100 objects in a) 
var a = []; 

for (var i = 0; i < 200; i++) { 
    if (i & 1) { 
     a.push({ id: i, position: i }); // objects are pushed only if they position is odd 
    } 
} 

// this means o.position (our new object) can have any even value, we know that it won't already exist in a 
var o = { 
    id: 2, 
    position: 2 
}; 
var start = 0, 
    end = (a.length - 1), 
    mid = end >>> 1, 
    left, 
    right; 

var iterations = 0; 

while (mid !== a.length - 1) { 
    if (mid > 0) { 
     leftIsMore = a[mid - 1].position > o.position; 
    } else { 
     leftIsMore = false; 
    } 

    rightIsLess = a[mid].position < o.position; 

    if (!leftIsMore && !rightIsLess) { 
     break; 
    } else if (leftIsMore) { 
     end = mid - 1; 
    } else { 
     start = mid + 1; 
    } 

    mid = (start + end) >>> 1; 
    iterations++; 
} 

var index = mid; 

if (index === a.length - 1) { 
    a.push(o); 
} else { 
    a.splice(index, 0, o); 
} 

console.log(a, 'Number of iterations to insert: ', iterations);