SHARE
TWEET

Untitled

a guest Mar 25th, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. var LFUCache = function(capacity) {
  2.     // max capacity
  3.     this.maxCap = capacity;
  4.     // current capacity
  5.     this.currentCap = 0;
  6.     // cache
  7.     this.cache = {};
  8.         // value
  9.         // frequency
  10.     // Least amount accessed
  11.     this.leastFrequentAccessedAmount = 0;
  12. //    this.secondLeastFrequentAccessedAmount = 0;
  13.     // Frequency lookup object
  14.     this.frequency = {};
  15.         // array of values
  16. };
  17.  
  18. LFUCache.prototype.get = function(key) {
  19.   if (this.cache[key]) {
  20.     this._updateFrequency(this.cache[key]);
  21.     return this.cache[key].value;
  22.   } else {
  23.     return -1
  24.   }
  25. };
  26.  
  27. LFUCache.prototype.put = function(key, value) {
  28.   // look up key and value first
  29.   if (this.maxCap > 0) {
  30.     if (this.cache[key]) {
  31.       this.cache[key].value = value;
  32.       this._updateFrequency(this.cache[key]);
  33.     } else {
  34.       if (this.currentCap === this.maxCap) {
  35.         this.cache[this.frequency[this.leastFrequentAccessedAmount][0]] = null;
  36.         this.frequency[this.leastFrequentAccessedAmount].splice(0, 1);
  37.       } else {
  38.         this.currentCap++;
  39.       }
  40.       this.cache[key] = {
  41.         value,
  42.         frequency: 0,
  43.         keyName: key
  44.       };
  45.       if (this.frequency[0]) {
  46.         this.frequency[0].push(key);
  47.       } else {
  48.         this.frequency[0] = [key];
  49.       }
  50.       this.leastFrequentAccessedAmount = 0;
  51.     }
  52.   }
  53.  
  54. };
  55.  
  56. LFUCache.prototype._updateFrequency = function(key) {
  57.   let freq = this.frequency[key.frequency];
  58.   for (var i = 0; i < freq.length; i++) {
  59.     if (freq[i] === key.keyName) {
  60.       freq.splice(i, 1);
  61.     }
  62.   }
  63.   if (key.frequency === this.leastFrequentAccessedAmount && this.frequency[key.frequency].length === 0) {
  64.     this.leastFrequentAccessedAmount++;
  65.   }
  66.   key.frequency++;
  67.   if (this.frequency[key.frequency]) {
  68.     this.frequency[key.frequency].push(key.keyName);
  69.   } else {
  70.     this.frequency[key.frequency] = [key.keyName]
  71.   }
  72. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top