#839 bug
Yaffle

Array#lastIndexOf optimization and ES5 compatibility

Reported by Yaffle | October 22nd, 2009 @ 12:42 PM

Array#lastIndexOf, used when there is no native browser method, is very inefficient( It uses slice and reverse. )

Original lastIndexOf takes time O(array.length) in all cases...

See,
https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Obje...
+ ES5 15.4.4.15

Comments and changes to this ticket

  • Juriy Zaytsev

    Juriy Zaytsev October 22nd, 2009 @ 04:11 PM

    I wouldn't use arguments here (for perf. reasons), instead, replacing it with actual parameter.

    Also, I'm not sure MDC version is ES5 compliant. It looks like they coerce fromIndex parameter into <array length> - 1, when it's not present, whereas ES5 says that it should be just len. However, they might be using same semantics, just in a slightly different way.

    Following specs, I got something like this:

    
    function ToUInt32(number) {
      return number >>> 0;
    }
    
    function ToInteger(number) {
      var n = Number(number);
      if (isNaN(n)) return +0;
      /* technically, need to check for negative infinity too (!) */
      if (n === 0 || n === Infinity) return n;
      var sign = ( n < 0 ) ? -1 : 1;
      return sign * Math.floor(Math.abs(n));
    }
    
    // skip coercion of `this` to object
    function lastIndexOf(searchElement, fromIndex) {
      var len = ToUInt32(this.length), n, k;
      if (len === 0) return -1;
      n = typeof fromIndex != 'undefined' ? ToInteger(fromIndex) : len;
      k = (n >= 0) ? Math.min(n, len - 1) : len - Math.abs(n);
      while (k >= 0) {
        if (k in this && searchElement === this[k]) return k;
        k--;
      }
      return -1;
    }
    
  • Yaffle

    Yaffle October 23rd, 2009 @ 08:39 AM

    As standart says, Array.prototype.lastIndexOf.length === 1, so I don't use second argument here.

    It seems, than this version is following specs:

      function ToInteger(number) {

    number = Number(number);
    return ((number &lt; 0 ? Math.ceil(number) : Math.floor(number)) || 0);
    
    
    
    
    } function lastIndexOf(item /, i /) {
    var length = this.length &gt;&gt;&gt; 0, i;
    i = arguments[1];
    i = (typeof i !== 'undefined' ? ToInteger(i) : -1);
    i = (i &lt; 0 ? i + length : Math.min(i, length-1));
    for (; i &gt; -1 &amp;&amp; !((i in this) &amp;&amp; this[i] === item); i--);
    return (i &gt; -1 ? i : -1);
    
    
    
    
    }
    This versions differ from my patch only if second argument is NaN
    Browsers Native Array#lastIndexOf also works different.
    [1,2,3,4,2,1].lastIndexOf(2, 'x'); // 4 - Opera [1,2,3,4,2,1].lastIndexOf(2, 'x'); // -1 - FF,Safari,Chrome

    So my last patch lgtm =)

    Or we need to replace native Array#lastIndexOf in Opera

  • Yaffle
  • T.J. Crowder

    T.J. Crowder November 16th, 2009 @ 04:50 PM

    [responsible:none bulk edit command]

  • Yaffle

    Yaffle December 2nd, 2009 @ 07:40 AM

    implementation of Array#lastIndexOf, using Array#indeOx:

      function ToInteger(number) {
        number = (+number) || 0;
        return (number < 0 ? Math.ceil(number) : Math.floor(number));
      }
    
      var step = 1;
    
      function indexOf(item /*, i */) {
        var length = this.length >>> 0, i;
        i = (arguments.length < 2 ? (step > 0 ? 0 : -1 ) : ToInteger(arguments[1]));
        i = (i < 0 ? Math.max(i + length, step - 1) : Math.min(i, length + step));
        for (; i > -1 && i < length && !((i in this) && this[i] === item); i += step){}
        return (i > -1 && i < length ? i : -1);
      }
    
      function lastIndexOf(item /*, i */) {
        step = -1;
        var result = indexOf.apply(this, arguments);
        step = 1;
        return result;
      }
    
  • Yaffle

    Yaffle December 2nd, 2009 @ 07:59 AM

    or better:

    
      function ToInteger(number) {

    number = (+number) || 0;
    return (number &lt; 0 ? Math.ceil(number) : Math.floor(number));
    
    
    
    
    }
    var step = 1;
    function indexOf(item /, i /) {
    var length = this.length &gt;&gt;&gt; 0,
        s = step, i;
    step = 1;
    i = (arguments.length &lt; 2 ? (s &gt; 0 ? 0 : -1 ) : ToInteger(arguments[1]));
    i = (i &lt; 0 ? Math.max(i + length, s - 1) : Math.min(i, length + s));
    for (; i &gt; -1 &amp;&amp; i &lt; length &amp;&amp; !((i in this) &amp;&amp; this[i] === item); i += s){}
    return (i &gt; -1 &amp;&amp; i &lt; length ? i : -1);
    
    
    
    
    }
    function lastIndexOf(item /, i /) {
    step = -1;
    return indexOf.apply(this, arguments);
    
    
    
    
    }
  • Yaffle
  • Tobie Langel

    Tobie Langel February 25th, 2010 @ 10:41 PM

    • Tag changed from patched, performance, section:lang to patched, performance, priority:high, section:lang
  • Tobie Langel

    Tobie Langel February 25th, 2010 @ 10:46 PM

    • State changed from “new” to “bug”
  • Tobie Langel

    Tobie Langel February 25th, 2010 @ 10:46 PM

    • Tag changed from patched, performance, priority:high, section:lang to patched, performance, section:lang

Please Sign in or create a free account to add a new ticket.

With your very own profile, you can contribute to projects, track your activity, watch tickets, receive and update tickets through your email and much more.

New-ticket Create new ticket

Create your profile

Help contribute to this project by taking a few moments to create your personal profile. Create your profile ยป

The Prototype JavaScript library.

Shared Ticket Bins

Pages