Наиболее эффективный способ вычисления последнего элемента в массиве JavaScript?

Question

Будет ли быстрее использовать

var lastelement = myarray[myarray.length - 1]; 

или

var lastelement = myarray.reverse()[0]; 

и почему?

Answer 1

Просто подумайте об этом.

Если вы знаете, как долго массив, то намного быстрее, чтобы просто получить последнее значение, чем вычислять обратное!

Answer 2

Быстро получить доступ к элементу по его индексу, так как он должен иметь сложность O (1). С другой стороны, реверсив массив, а затем доступ к первому индексу, будет иметь как минимум сложность O (n), в зависимости от того, как реализуется алгоритм реверсирования.

Answer 3

Я возьму это под другим углом, чем здесь был дан ответ. Скорее всего, вы просто хотите получить последний элемент, вы не хотите ничего делать с самим массивом. Если вы используете array.reverse, чтобы получить последний элемент, вы фактически меняете массив (вероятно, неприятный побочный эффект в вашем случае).

var myArray = [.....]; // some array 
var lastElement = myArray.reverse()[0]; // get the last element 
var firstElement = myArray[0]; // tricked you! This is now the same as 
           // lastElement because the myArray object 
           // in memory has been reversed. 

Так что если вы хотите получить последний элемент без изменения массива вы должны сделать это:

var myArray = [.....]; // some array 
var lastElement = myArray.slice().reverse()[0]; // copy and get the last element 
var firstElement = myArray[0]; // this is the correct first element 

Довольно очевидно, какой путь является более эффективным в настоящее время.

Answer 4

Реальное эффективное решение заключается в использовании красного и черного двоичного дерева (http://en.wikipedia.org/wiki/Red%E2%80%93black_tree), где вы будете хранить в каждом узле одно значение массива, дельта с предыдущим и следующим элементом, а также относительное положение до медиана. Затем, только с небольшим обходом, вы должны иметь возможность идентифицировать последний элемент (последний элемент - тот, у которого индекс с наибольшим разбросом по медианному индексу, с предыдущим элементом и без следующего элемента).

Фокус в том, что каждый обход принимает только O (ln (n)), и поскольку вы выполняете меньше, чем ln (n) обход, время ниже O (sq (ln (n))), так что это очень быстро.

Редактировать: после конструктивных комментариев Bergi я просто задаюсь вопросом, не будет ли быстрее использовать массивы для этого, используя быстрое преобразование Фурье в массиве, содержащем все индексы массива, а затем идентифицирует последний элемент с затем преобразуйте назад массив, чтобы получить номер из частоты. Я прошу прощения, если я неясен, я не вижу четко всех шагов на момент написания, но я думаю, что это стоит того.