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.

I think the `map` function has a better perfomance. Maybe you could sort the entries first and then run over it with map. — hansTheFranz, Jul 11 '17 at 11:21
As per @EmilS.Jørgensen - sorting and performing a more efficient search is absolutely the answer. If you can sort them server side (as you pull them from an efficient source like a database), even better. — wally, Jul 11 '17 at 11:21
It's already sorted. But still it hangs with data above a certain level — iJade, Jul 11 '17 at 11:21
@SagarV but that cost is amortized over every subsequent search and glancing at the code it looks like OP is likely doing this more than once. — Jared Smith, Jul 11 '17 at 11:24
@iJade, but did you try binary search like EmilSJorgensen suggested? Also there might be limits in terms of available RAM since the whole list still needs to be loaded into memory. — laurent, Jul 11 '17 at 11:24
If it is server side, it is ok. I think he said to sort in client side - each time — Sagar V, Jul 11 '17 at 11:25

Dwayne Charrington · Answer 1 · 2017-07-11T11:42:27.520

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.

Jonas Wilms · Answer 2 · 2017-07-11T11:55:12.867

0

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);

edited Jul 11 '17 at 11:55

answered Jul 11 '17 at 11:43

Jonas Wilms

132,000
20
149
151

set returns if it exists or not. But it wouldn't help with getting the corresponding `values` in the array ? – iJade Jul 11 '17 at 11:53
@iJade then a Map? – Jonas Wilms Jul 11 '17 at 11:53

Emil S. Jørgensen · Answer 3 · 2017-07-11T12:33:12.870

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.

Faster approach to iterate JavaScript array without using for loop

3 Answers3