Каков наиболее эффективный способ обращения массива в Javascript?



недавно меня спросили, какой самый эффективный способ отменить массив в Javascript. На данный момент, я предложил использовать цикл for и возиться с массивом, но потом понял, что это уроженец Array.reverse() метод.



ради любопытства, может ли кто-нибудь помочь мне исследовать это, показывая примеры или указывая в правильном направлении, чтобы я мог прочитать это? Любые предложения о том, как измерить производительность будет слишком удивительным.

591   14  

14 ответов:

на основе этой настройки:

var array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var length = array.length;

Array.reverse(); является первым или вторым самым медленным!

ориентиры здесь: http://jsperf.com/js-array-reverse-vs-while-loop/5

в разных браузерах циклы подкачки быстрее. Существует два распространенных типа алгоритмов подкачки (см. Википедия), каждый с двумя вариациями.

два типа алгоритмов подкачки, временные замены и гаммирования своп.

два вариации обрабатывают вычисления индекса по-разному. Первый вариант сравнивает текущий левый индекс и правый индекс, а затем уменьшает правый индекс массива. Второй вариант сравнивает текущий левый индекс и длину, разделенную пополам, а затем пересчитывает правый индекс для каждой итерации.

вы можете или не можете видеть огромные различия между двумя вариантами. Например, в Chrome 18 первые варианты временной замены и замены XOR превышают 60% медленнее, чем вторые вариации, но в Opera 12 обе вариации временного свопа и свопа XOR имеют одинаковую производительность.

временные замены:

первый вариант:

function temporarySwap(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0, right = length - 1; left < right; left += 1, right -= 1)
    {
        var temporary = array[left];
        array[left] = array[right];
        array[right] = temporary;
    }
    return array;
}

второй вариант:

function temporarySwapHalf(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0; left < length / 2; left += 1)
    {
        right = length - 1 - left;
        var temporary = array[left];
        array[left] = array[right];
        array[right] = temporary;
    }
    return array;
}

XOR swap:

первый вариант:

function xorSwap(array)
{
    var i = null;
    var r = null;
    var length = array.length;
    for (i = 0, r = length - 1; i < r; i += 1, r -= 1)
    {
        var left = array[i];
        var right = array[r];
        left ^= right;
        right ^= left;
        left ^= right;
        array[i] = left;
        array[r] = right;
    }
    return array;
}

второй вариант:

function xorSwapHalf(array)
{
    var i = null;
    var r = null;
    var length = array.length;
    for (i = 0; i < length / 2; i += 1)
    {
        r = length - 1 - i;
        var left = array[i];
        var right = array[r];
        left ^= right;
        right ^= left;
        left ^= right;
        array[i] = left;
        array[r] = right;
    }
    return array;
}

есть еще один метод, который называется swap реструктуризующее присваивание: http://wiki.ecmascript.org/doku.php?id=harmony:destructuring

Реструктуризующее присваивание:

первый вариант:

function destructuringSwap(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0, right = length - 1; left < right; left += 1, right -= 1)
    {
        [array[left], array[right]] = [array[right], array[left]];
    }
    return array;
}

второй вариант:

function destructuringSwapHalf(array)
{
    var left = null;
    var right = null;
    var length = array.length;
    for (left = 0; left < length / 2; left += 1)
    {
        right = length - 1 - left;
        [array[left], array[right]] = [array[right], array[left]];
    }
    return array;
}

сейчас алгоритм, использующий назначение деструктурирования, является самым медленным из всех. Это даже медленнее, чем Array.reverse();. Однако алгоритмы, использующие назначения деструктурирования и Array.reverse(); методы самые короткие примеры, и они выглядят чистыми. Я надеюсь, что их производительность станет лучше в будущем.


еще одно упоминание о том, что современные браузеры улучшают свою производительность массива push и splice операции.

в Firefox 10, этот for алгоритм цикла с использованием массива push и splice соперника временной замены и гаммирования алгоритмы цикл подкачки.

for (length -= 2; length > -1; length -= 1)
{
    array.push(array[length]);
    array.splice(length, 1);
}

тем не менее, вы, вероятно, должны придерживаться алгоритмов цикла подкачки до тех пор, пока многие из других браузеров совпадают или превышают их массив push и splice производительность.

собственные методы всегда быстрее.

так что используйте Array.reverse там, где это возможно. В противном случае реализация, которая выполняется в O(1) будет лучше ;)

в противном случае просто использовать что-то вроде этого

var reverse = function(arr) {
   var result = [],
       ii = arr.length;
   for (var i = ii - 1;i !== 0;i--) {
       result.push(arr[i]);
   }
   return result;
}

эталоном!

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

for(var i = ii - 1; i !== 0;i--) затем быстрее var i = ii - 1;for(;i-- !== 0;)

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

простым способом вы можете сделать это с помощью карты.

let list = [10, 20, 30, 60, 90]
let reversedList = list.map((e, i, a)=> a[(a.length -1) -i]) // [90, 60...]

Так как никто не придумал его и завершить список способов реверсирования массива...

array.sort(function() {
    return 1;
})

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

http://jsperf.com/js-array-reverse-vs-while-loop/53

функции подкачки являются самыми быстрыми. Вот обратная функция, которую я написал, которая только немного похожа на функции подкачки, упомянутые выше, но работает быстрее.

function reverse(array) {
  var first = null;
  var last = null;
  var tmp = null;
  var length = array.length;

  for (first = 0, last = length - 1; first < length / 2; first++, last--) {
    tmp = array[first];
    array[first] = array[last];
    array[last] = tmp;
  }
}

вы можете найти бенчмаркинг здесь http://jsperf.com/js-array-reverse-vs-while-loop/19

вот пример javahttp://www.leepoint.net/notes-java/data/arrays/arrays-ex-reverse.html показывает, как изменить массив. Очень легко конвертировать в javascript.

Я бы предложил использовать что-то, что просто фиксирует время до вызова функции и после вызова функции. Который когда-либо занимает меньше времени / тактов будет самым быстрым.

Если вы хотите скопировать перевернутую версию массива и сохранить оригинал как есть:

a = [0,1,2,3,4,5,6,7,8,9];
b = []
for(i=0;i<a.length;i++){
    b.push(a.slice(a.length-i-1,a.length-i)[0])
}

выход b:

[ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

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

var theArray = ['a', 'b', 'c', 'd', 'e', 'f'];

function reverseArrayInPlace(array) {
  for (var i = array.length - 1; i >= 0; i -= 1) {
    array.push(array[i]);
  }
  array.splice(0, array.length / 2);
  return array;
};
reverseArrayInPlace(theArray);
console.log(theArray); // -> ["f", "e", "d", "c", "b", "a"]

вот несколько трюков, которые я нашел. Кредит идет на Codemanx для оригинального решения

array.sort(function() {
   return 1;
})

в Typescript это можно упростить до одной строки

array.sort(() => 1)

var numbers = [1,4,9,13,16];

console.log(numbers.sort(() => 1));

так как это будет будущее JavaScript, я думал, что поделюсь этим.

вот еще один трюк, если Ваш массив имеет только 2 элемента

array.push(array.shift());

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

var myArray=["one","two","three","four","five","six"];
console.log(myArray);
for(i=0;i<myArray.length;i++){
myArray.splice(i,0,myArray.pop(myArray[myArray.length-1]));
}
console.log(myArray);

Это наиболее эффективный и чистый способ обращения массива с помощью тернарного оператора.

function reverse(arr) {
  return arr.length < 2 ? arr : [arr.pop()].concat(reverse(arr));
}
console.log(reverse([4, 3, 3, 1]));

Я нашел простой способ сделать это .ломтик.)(обратный()

var yourArray = ["first", "second", "third", "...", "etc"]
var reverseArray = yourArray.slice().reverse()

console.log(reverseArray)

Вы получаете

["etc", "...", "third", "second", "first"]

вы также можете использовать reduceRight, который будет перебирать каждое значение массива (справа-налево)

const myArray = [1, 2, 3, 4, 5]
const reversedArray = myArray.reduceRight((acc, curr) => [...acc, curr], [])
console.log(reversedArray) // [5, 4, 3, 2, 1]

Comments

    Ничего не найдено.