How to cache data in JavaScript for a non-transient shift range?

Question

Edit:. For simplicity and in order to try to make this question and sample code more general, I left the detail. An important detail is that in the light of one of the answers (which was wonderful). This system will be used primarily to display things in a date range. Low / high numbers in code often represent Unix timestamps, which can span weeks or months. Edit end

I have a page where I provide a representation of data objects that have properties that fall within a specific range. Since the user interacts with the idea of ​​his change, he is usually a sequential range change (0-9, 10-19 ...). I retrieve this data from the server, and as I understand it, it caches it so that a subsequent request for data in this range is already available. Each time I read the data, I first check if I have cache data, and if not, I read it from the server and set up the cache.

A crude, oversimplified example:

var cache, haveCache, read; cache = { rangeLow: 0, rangeHigh: 10, data: [ //whatever has been read so far between current low and high { low: 1, high: 3, // ...other props }, { low: 5, high: 6, // ...other props }, //... ] }; haveCache = function( low, high ) { return ! ( low < cache.rangeLow || high > cache.rangeHigh ); }; read = function( low, high ) { var data; if( ! haveCache( low, high ) ) { //go to outside source and read in info , then merge to cache // // when merging to cache: // if `low` param is lower than `cache.rangeLow`, overwrite cache.rangeLow with `low` // if `high` param is higher than `cache.rangeHigh`, overwrite `cache.rangeHigh` with `high` } //read data from cache return data; }; 

This works fine as long as the change in range is really consistent. However, I realized that there is a way to change the view not sequentially and skip a large set of values. So, let's say I am now showing ranges 10-19, and I have cache memory for ranges 0-29. The user then requests data for the range 60-69. The way it works at the moment, I will ask the server to provide data and return it and present it in order. But now, the Low and rangeHigh cache ranges from 0 to 69, while it actually only stores data for ranges 0-29 and 60-69. Items with properties from 30 to 59 are not in the cache and will never be restored.

What (best, effective) mechanism or algorithm can be used to store cached information and determine if the current displayed range is in the cache?

Thanks a lot jim

Answer 1

You seem to have “chunks” of data with a range of 10 objects each. Calculate how many of these pieces you can store in your cache, call this cache_size . Now you can use the list of pieces that you have in the cache, i.e. for cache_size 4:

 20-29 0-9 40-49 30-39 

It will be a little more difficult to maintain this list and check if any object is in the cache, but I think it is worth the effort.

You can also think about storing every day in the time or date index to determine when the object was last retrieved from it, so when your cache is full and you have to discard the cached piece, you can discard the oldest one.

Answer 2

I think you should change your hasCache to have smoother key => values.

For example, one could instead:

  1..4
 5..7
 10.14

Simply:

  1,1,1,1, // means like 1 => true, 2 => true, 3 => true, 4 => true
 1,1,1, // means like 5 => true, 6 => true, 7 => true
 0,0, // means like 8 => false, 9 => false
 1,1,1,1,1 // means like 10 => false, 11 => false, 12 => false, 13 => false, 13 => false

Then you just change your hasCache function to determine if you have a cache in any range. When updating the cache, you also need to update your new cache index by filling in / adding the necessary values ​​to 1.

For the case of time

You just need to smooth it in another form:

 var cache = { 1304960585 : {/* your data for 1304960585 */}, 1304960586 : {/* your data for 1304960586 */}, 1304960999 : {/* your data for 1304960999 */}, }; // then in haveCache function you should have something like: function haveCache(start, end) { for (var i = start; i <= end; i++) { if (undefined == cache[i]) { return false; } } return true; } 

In cases where you have part of the range in the cache, and part not - you have to invent for yourself.

Answer 3

I would change havecashe

 haveCache = function( low, high ) { if( low < cache.rangeLow || high > cache.rangeHigh )return undefined; for(var i = 0;i<cashe.data.length;i++){ if( !(low < cache.data[i].low || high > cache.data[i].high) ) return cache.data[i] } return undefined; }; 

this also returns the data item in cashe, so you don't need to search again

 var data; if((data=haveCashe(low,high))==undefined){ //read from server and store in cashe } return data;