Find closest array index

Question

I'm dealing with an array of "events" where the key of the array is the Unix Timestamp of the event. In other words let's assume we have the following array of event objects in JS:

var MyEventsArray=[];
MyEventsArray[1513957775]={lat:40.671978333333, lng:14.778661666667, eventcode:46};
MyEventsArray[1513957845]={lat:40.674568332333, lng:14.568661645667, eventcode:23};
MyEventsArray[1513957932]={lat:41.674568332333, lng:13.568661645667, eventcode:133};
and so on for thousands rows...

Data are sent along Ajax call and encoded in JSON to be processed with JS. When the data set is received, I have another Unix Timestamp let say 1513957845, coming from another source and I want to find the event that happened at that time...it's quite easy I just need to take the element from the array having the given index (the second in the list above). Now the question: immagine that the given index is not found (imagine we are looking for UXTimestamp=1513957855) and that this index was not existing in the array but I want to take the closest index (in the example above I would take the element MyEventsArray[1513957845] as it's index 1513957845 is the closest to 1513957855). What can I do to obtain this result? My difficulties are in handling array index as I when I receive the array I don't know where the index begins.

How the machine will handle situations like that? Will the machine allocate (and waste) memory for dummy/empty elements placed between each rows or the compiler have some kind of ability to build it's own index and optimize the space? In other words: is it safe to play with index as we're doing or it's better to allocate the array as:

var MyEventsArray=[];
MyEventsArray['1513957775']={lat:40.671978333333, lng:14.778661666667, eventcode:46};
MyEventsArray['1513957845']={lat:40.674568332333, lng:14.568661645667, eventcode:23};
MyEventsArray['1513957932']={lat:41.674568332333, lng:13.568661645667, eventcode:133};
and so on for thousands rows...

In this case the key and the index are clearly different so here it's possible to get the first element with MyArray[0] despite we don't know the key value. Is this approach more expensive (here we must save index and key) in term of memory or the effects are the same for the compiler?

score 4 · Accepted Answer · answered Dec 22 '17 at 19:01

There is no difference between MyEventsArray[1513957775] and MyEventsArray['1513957775']. Deep down, array indexes are just property names, and property names are strings.

Regarding the question of whether these sparse indices will lead to millions of empty cells being allocated, no, that won't happen. Sparse arrays only store what you put in them, not empty space.

If you want to find a key quickly, you can obtain an array of the keys, sort them, and then find the one you want:

var MyEventsArray=[];
MyEventsArray[1513957775]={lat:40.671978333333, lng:14.778661666667, eventcode:46};
MyEventsArray[1513957845]={lat:40.674568332333, lng:14.568661645667, eventcode:23};
MyEventsArray[1513957932]={lat:41.674568332333, lng:13.568661645667, eventcode:133};

var target = 1513957855;

var closest= Object.keys(MyEventsArray)
                   .map(k => ({ k, delta: Math.abs(target - k) }))  
                   .sort((a, b) => a.delta - b.delta)[0].k;

console.log(closest);

Brilliant solution, I underestimated Object.keys().map. It's exactly what I was looking for. — Power Engineering, Dec 22 '17 at 19:30

score 1 · Answer 2 · answered Dec 22 '17 at 20:22

1

You could take Array#some which allowes to exits the iteration if the delta is getting greater than the last delta.

var array = [];
array[1513957775] = { lat: 40.671978333333, lng: 14.778661666667, eventcode: 46 };
array[1513957845] = { lat: 40.674568332333, lng: 14.568661645667, eventcode: 23 };
array[1513957932] = { lat: 41.674568332333, lng: 13.568661645667, eventcode: 133 };

var key = 0,
    search = 1513957855;

Object.keys(array).some(function (k) {
    if (Math.abs(k - search) > Math.abs(key - search)) {
        return true;
    }
    key = k;
});

console.log(key);

answered Dec 22 '17 at 20:22

Nina Scholz

376,160
25
347
392

`Object.keys` isn't guaranteed to return keys in any particular order, so this optimization relies on implementation details. – JLRishe Dec 23 '17 at 02:50
@JLRishe, in newer systems at leaset ES2015 has the standars, that integer properties comes sorted first, so no sorting required, becaus you get it in the right order for iterating. a faster mehtod could be to use a binary search. – Nina Scholz Dec 23 '17 at 09:39
Thanks. I didn't realize they standardized it in ES2015. – JLRishe Dec 23 '17 at 11:51

Glenn Barnett · Answer 3 · 2017-12-22T19:00:11.560

0

You can use Object.keys(MyEventsArray) to get an array of the keys (which are strangely expressed as strings); you could then iterate through that and find the closest match.

var MyEventsArray=[];
MyEventsArray[1513957775]={lat:40.671978333333, lng:14.778661666667, eventcode:46};
MyEventsArray[1513957845]={lat:40.674568332333, lng:14.568661645667, eventcode:23};
MyEventsArray[1513957932]={lat:41.674568332333, lng:13.568661645667, eventcode:133};
Object.keys(MyEventsArray)

["1513957775", "1513957845", "1513957932"]

Reference: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array

edited Dec 22 '17 at 19:00

answered Dec 22 '17 at 18:55

Glenn Barnett

2,031
1
21
31

Nice - then you could `.map` against that key array adding a second property to each entry consisting of the absolute difference between the key array's value and the searched value .. then sort the returned mapped array by the difference ascending grabbing the first entry.. I like this `Object.keys(MyEventsArray)`. – Forty3 Dec 22 '17 at 18:59

Find closest array index

3 Answers3