Would it be faster to use
var lastelement = myarray[myarray.length - 1];
or
var lastelement = myarray.reverse()[0];
and why?
Would it be faster to use
var lastelement = myarray[myarray.length - 1];
or
var lastelement = myarray.reverse()[0];
and why?
Share Improve this question edited Dec 12, 2013 at 18:23 awesame asked Dec 12, 2013 at 14:42 awesameawesame 942 silver badges14 bronze badges 7- 10 Reversing an array just to get the last element ? Seriously ? BTW you probably forgot some parenthesis. – Denys Séguret Commented Dec 12, 2013 at 14:43
- 7 Note that instead of asking SO, you could test by yourself, for example using jsperf. – Denys Séguret Commented Dec 12, 2013 at 14:44
- micro optimization alert! – rlemon Commented Dec 12, 2013 at 14:52
-
1
I think you meant
myarray.reverse()[0]
. Maybe it shows you better how the putation differs. – Florian Margaine Commented Dec 12, 2013 at 14:53 - Which is faster, taking a card off the bottom of the deck, or reversing the order of the entire deck and then taking one off the top? – user2736012 Commented Dec 12, 2013 at 14:56
5 Answers
Reset to default 4Just think about it.
If you know how long an array is, it is much faster to just get the last value than to have to pute the reverse!
It is faster to access an element by its index, as it should have O(1) plexity. Reversing an array and then accessing the first index, on the other hand, would have at least O(n) plexity, depending on how the reversing algorithm is implemented.
I'll take this from a different angle than has been answered here. Chances are you just want to get the last element, you don't want to do anything to the actual array itself. If you use array.reverse
to get the last element, you are actually changing the array (probably an unpleasant side effect in your case).
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.
So if you want to get the last element without changing the array you'd have to do this:
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
Pretty obvious which way is more efficient now.
Array.reverse() replacing old array with new reversed array in same reference ,crating the new array with new elements is much slower than get array element by index. var lastelement = myarray[myarray.length - 1]; Is much faster.
The real efficient solution is to use a red and black binary tree (http://en.wikipedia/wiki/Red%E2%80%93black_tree ) where you'll store in each node one array value, the delta with the previous and next item, as well as the relative position to median. Then with only a few traversal you should be able to identify the last element (last element is the one having an index with biggest spread to median index, while having a previous item and no next item).
The trick is that each traversal takes only O(ln(n)) and since you do less than ln(n) traversal, time is below O(sq(ln(n))), so it's very fast.
Edit : following Bergi's constructive ments, i just wonder if it wouldn't be faster to just use arrays for this, by using a Fast fourier transform on an array containing all indexes of the array, then identifying last element with a frequency analysis, then convert back the array to get the number out of the frequency. I apologize if i'm unclear, i don't see clearly all steps at the time of writing, but i think it's a idea worth following.