Faster approach to iterate JavaScript array without using for loop

Question

Here is a sample of the JSON data that I'm trying to parse.

{
    "tags": [{
        "name": "SQOP_SPD",
        "results": [{
            },
            "values": [
                [1499771383876, 0, 0],
                [1499771384800, 0, 0],
                [1499771385885, 10, 0],
                [1499771386893, 0, 0],
                [1499771388867, 0, 0],
                [1499771389879, 10, 0],
                [1499771390878, 0, 0],
                [1499771391787, 0, 0],
                [1499771392870, 0, 0],
                [1499771394015, 0, 0],
                [1499771394955, 0, 0],
                [1499771395800, 0, 0],
                [1499771396882, 0, 0],
                [1499771397904, 0, 0],
                [1499771399906, 0, 0]
            ],
            "attributes": {
                "VId": ["9499"],
            }
        }],
        "stats": {
            "rawCount": 15
        }
    }
}

I'm iterating through the values array using a for loop and checking if a particular timestamp is present.

var items = dataa['tags'][j]['results'][0]['values'];
for (var k = 0; k < items.length; k++) {
    if (items[k] == sortedTimeStampList[i]) {
          // some code
    }
}

The page begins to hang when there are like 10000000 entries in the the values array.

Is there a faster approach to check for a timestamp in the values array.

Answer 1

Honestly, the fastest form of loop in Javascript is the for loop, with a cached index as you currently have. Your performance will vary quite greatly depending on the browser you are in and the available resources on your machine.

I believe you have an architectural flaw in your application. Do you need all 10000000 entries at once? A binary search will help you out for what you need (as suggested by someone else), but I would argue that there probably isn't a need to load and loop all entries like you are trying to do.

Consider lazily loading your entries as you need them instead of all at once. Load the data when you need it, as you need it. It sounds like you're currently hitting memory limitations, 10000000 entries is a lot of data to work with (especially if you have arrays of complex objects).

I recommend looking into Service Workers which are made for more computational/heavy tasks that are run in a separate thread from the browser, but they're not supported that well just yet, so probably not an option for you if you're creating a front-facing application where you don't control what browsers access it.

Answer 2

One possibility would be iterating slower ( so that it doesnt hang):

function find(callback,value,start=0){
 for (var k = 0; k+start < items.length; k++) {
  if (items[k+start][0] === value) {
      callback(items[k+start]);
  }
  if(k==100){
   setTimeout(find,0,callback,value,start+k);
   break;
 }
}

Usecase:

find(console.log,512627172);

Or if you just want to get a certain timestamp you could use a map:

var map=new Map(items.map(el=>[el[0],el.slice(1)]));
console.log(map.get(5293842838));

And if you just want to check the existance of a certain timestamp you could also create a Set out of your array (better performance concerning finding) :

var set=new Set(items.map(el=>el[0]));
set.has(5293842838);

Answer 3

Here is a native solution. I get about 150ms when looping through a single dataset.

var obj = {
  "tags": [{
    "name": "SQOP_SPD",
    "results": [{
      "values": [],
      "attributes": {
        "VId": ["9499"]
      }
    }],
    "stats": {
      "rawCount": 15
    }
  }]
};
//Date for timing
var d = Date.now();
//Add 10000000 rows
while (obj.tags[0].results[0].values.length < 10000000) {
  obj.tags[0].results[0].values.push([1499771383876 + obj.tags[0].results[0].values.length, 0, 0]);
}
console.log("spent " + (Date.now() - d) + "ms on adding rows");
//Native model for comparison
d = Date.now();
//Target is number 100 from the end
var target = obj.tags[0].results[0].values[obj.tags[0].results[0].values.length - 7];
//Find index
var iAmNative = obj.tags[0].results[0].values.
findIndex(function(a) {
  return a[0] == target[0];
});
//Log output
console.log("spent " + (Date.now() - d) + "ms on succeeding natively, result:", obj.tags[0].results[0].values[iAmNative], " index:", iAmNative);
obj = null;

Or even faster using a binary search approach:

var obj = {
  "tags": [{
    "name": "SQOP_SPD",
    "results": [{
      "values": [],
      "attributes": {
        "VId": ["9499"]
      }
    }],
    "stats": {
      "rawCount": 15
    }
  }]
};
//Date for timing
var d = Date.now();
//Add 10000000 rows
while (obj.tags[0].results[0].values.length < 10000000) {
  obj.tags[0].results[0].values.push([1499771383876 + obj.tags[0].results[0].values.length, 0, 0]);
}
console.log("spent " + (Date.now() - d) + "ms on adding rows");
//The binary search algorithm
var binarySearch = (function() {
  /**
   * compare_complex
   *
   * @param {(number | string)} a
   * @param {(number | string)} b
   * @returns {number}
   */
  function compare_complex(a, b) {
    return a.toString().localeCompare(b.toString());
  }
  /**
   * compare_number
   *
   * @param {number} a
   * @param {number} b
   * @returns {number}
   */
  function compare_number(a, b) {
    return a - b;
  }
  /**
   * binarySearch
   *
   * @param {IBinarySearch} [args={ list: [], target: '' }]
   * @returns {number}
   */
  function binarySearch(args) {
    if (args === void 0) {
      args = {
        list: [],
        target: ''
      };
    }
    var params = {
      list: [],
      key: null,
      target: '',
      threshold: 10,
      complex: true
    };
    for (var key in args) {
      if (args.hasOwnProperty(key) && params.hasOwnProperty(key)) {
        params[key] = args[key];
      }
    }
    var max = params.list.length - 1;
    var maxKey = (params.key == null ? params.list[max] : params.list[max][params.key]);
    var min = 0;
    var minKey = (params.key == null ? params.list[min] : params.list[min][params.key]);
    if (minKey == params.target) {
      return min;
    }
    if (maxKey == params.target) {
      return max;
    }
    var compare = (params.complex === true ? compare_complex : compare_number);
    while (max - min >= params.threshold) {
      var diff = max - Math.floor((max - min) / 2);
      var diffKey = (params.key == null ? params.list[diff] : params.list[diff][params.key]);
      var cmp = compare(diffKey, params.target);
      if (cmp == 0) {
        return diff;
      } else if (cmp < 0) {
        min = diff;
      } else {
        max = diff;
      }
    }
    if (params.key != void 0) {
      var index = params.list.slice(min, max).map(function(m) {
        return m[params.key];
      }).indexOf(params.target);
    } else {
      var index = params.list.slice(min, max).indexOf(params.target);
    }
    if (index >= 0) {
      return index + min;
    }
    return index;
  }
  return binarySearch;
})();
//Binary model for comparison
d = Date.now();
//Target is number 100 from the end
var target = obj.tags[0].results[0].values[obj.tags[0].results[0].values.length - 7][0];
//Find index
var iAmBinary = binarySearch({
  list: obj.tags[0].results[0].values,
  target: target,
  key: 0
});
//Log output
console.log("spent " + (Date.now() - d) + "ms on searching binarily, result:", obj.tags[0].results[0].values[iAmBinary], "index:", iAmBinary);
//Release memory
obj = null;

I consistently gets less than 10ms search time with the binary approach.