Оптимизировать простой цикл for для IE

Question

array.sort(function(left, right) {
    return index(otherArray, left) < index(otherArray, right);
});

Это O(len(array) ^ 2), поэтому для массива разумного размера len = 1000 требуется постоянная * 1 миллион операций, что легко превышает ограничение на 5 миллионов операторов IE.

Таким образом, IE создает сценарийзанимает слишком много времени, даже если это быстро.

Проблема в том, что IE не имеет своего собственного Array.prototype.indexOf, поэтому я не могу уменьшить счет операций до O(len(array) и вместо этого полагаюсь, что получу двойнойцикл for вместо одного цикла for.

Я рассматривал array.join и использовал String.prototype.indexOf, но объекты в массивах являются элементами DOM, и вы не можете преобразовать их в строку (легко).

Указывать пользователям IE удалить эту заглушку по умолчанию не вариант.

Answer 1

Я могу подумать о двух возможных решениях этой проблемы: одно из них будет работать везде, другое - полностью проприетарное для IE (и я ожидаю, что не работает в IE9, но поддерживает Array.prototype.indexOf, так что этоне проблема).

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

Решение только для IE - сделать что-то похожее на то, что предлагал @maclema, используя объект поиска, и HTMLElement.uniqueID:

var otherArrayLookup = {};
for (var i=0; i < otherArray.length; i++) {
    otherArrayLookup[otherArray[i].uniqueID] = i;
}

array.sort(function(left, right) {
    return otherArrayLookup[left.uniqueID] < otherArrayLookup[right.uniqueID];
});

Вы захотитедобавить туда несколько ветвей (не помещать их в функцию обратного вызова, но использовать другие функции обратного вызова) для поддерживаемого случая Array.prototype.indexOf, поддерживаемого случая HTMLElement.uniqueID и случая «ничего из вышеперечисленного».

Answer 2

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

var otherArrayLookup = {};
for ( var i=0; i<otherArray.length; i++ ) {
    otherArrayLookup[otherArray[i]] = i;
}

array.sort(function(left, right) {
    return otherArrayLookup[left] < otherArrayLookup[right];
});