Time range hash function

Question

Given the following data structure:

[{
  start: 10.2,
  end: 15.3,
  text: 'Lorem Ipsum....'
}, {
  start: 16.3,
  end: 20.5,
  text: 'dolor sit...'
}, {
  start: 19.4,
  end: 25.1,
  text: 'consectetur adipiscing elit'
}]

I need to figure out the active text for a given time (e.g. 18, which maches element 2 and 3). I already implemented a find method that checks if the given time is greater than start and lesser than end. Unfortunately that's not as efficient for around 25k entries. I'm therefore looking for a hashmap implementation that has calculates start and end as keys and returns for a given time the matching entries.

@NinaScholz Yes the data can be sorted by start or end once on application init. Will have a look at binary search. — Alexander Heimbuch, Dec 02 '17 at 16:28
@KalaiselvanA Not yet, could be a more performant implementation but I want to avoid iterating over the full array. — Alexander Heimbuch, Dec 02 '17 at 16:28
is there a limit on the possible time values (for example 24 for 0 to 23, or 240 for 0.0 to 23.9), and do you get the data from JSON.parse? — Slai, Dec 02 '17 at 17:16
@Slai `start` and `end` are floating seconds. So `Number.MAX_VALUE` is the maximum. Yes I get the numbers from a JSON.parse. — Alexander Heimbuch, Dec 02 '17 at 19:36
I mean the value(s) to search by (18 in your example). Maybe interval tree https://stackoverflow.com/questions/47372219/efficient-algorithm-for-intersection-of-a-collection-of-bounded-lines — Slai, Dec 02 '17 at 19:47
@Slai I'm currently trying an interval tree. Results seem to be quite promising. — Alexander Heimbuch, Dec 03 '17 at 20:34

score 0 · Answer 1 · answered Dec 02 '17 at 16:21

it will helpful to you to filter the data

var arr=[{
  start: 10.2,
  end: 15.3,
  text: 'Lorem Ipsum....'
}, {
  start: 16.3,
  end: 20.5,
  text: 'dolor sit...'
}, {
  start: 19.4,
  end: 25.1,
  text: 'consectetur adipiscing elit'
}]

var condition=(arr)=>(arr.start>=18);

var arr_1=arr.filter(condition);
console.log(arr_1);

score 0 · Answer 2 · answered Dec 02 '17 at 16:38

For sorted data, you could take a binary seach where the start is in the middle of the list and if the wanted date is smaller, take the middle of start and middle or the middle values of the other side. Proceed until the item is found.

For unsorted data, you could take the year as part of the hash key and the week number for every event in the list.

If an event is ends in another week, add all references of the event in the hash table with all the weeks where it takes place.

For a seach, just calculate the week number and take a fine seach on the given week data.

Instead of the week, you could take a shorter range, like a day or a greater range, like the first half of the month or the last half of the month (this would be easier to calculate then a week).

Time range hash function

2 Answers2