Last active
February 20, 2024 17:59
-
-
Save beenotung/808330e4b19842fc856fd845f7f0c0cb to your computer and use it in GitHub Desktop.
Weighted Cache Pool Walk Through. Explaination Video: https://youtu.be/k3rKetctNug
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
let time = 0 | |
Date.now = () => { | |
time++ | |
return time | |
} | |
class Cache { | |
pool = {} | |
size = 0 | |
constructor(capacity) { | |
this.capacity = capacity | |
} | |
calcScore(weight, current_time, last_accessed_time) { | |
return weight / (Math.log(current_time - last_accessed_time + 1) + 1) | |
} | |
getMinScoreKey(current_time) { | |
let min_score = Number.POSITIVE_INFINITY | |
let min_key | |
for (let key in this.pool) { | |
let { weight, last_accessed_time } = this.pool[key] | |
let score = this.calcScore(weight, current_time, last_accessed_time) | |
console.log('compare:', { | |
key, | |
weight, | |
diff_time: current_time - last_accessed_time, | |
score, | |
}) | |
if (score < min_score) { | |
min_score = score | |
min_key = key | |
} | |
} | |
return min_key | |
} | |
put(key, value, weight) { | |
let current_time = Date.now() | |
if (this.size >= this.capacity) { | |
console.log('full, the pool:', this.pool) | |
let min_key = this.getMinScoreKey(current_time) | |
console.log('remove from pool:', min_key) | |
delete this.pool[min_key] | |
this.size-- | |
} | |
this.pool[key] = { | |
value, | |
weight, | |
last_accessed_time: current_time, | |
} | |
this.size++ | |
} | |
get(key) { | |
if (key in this.pool) { | |
let item = this.pool[key] | |
item.last_accessed_time = Date.now() | |
return item.value | |
} | |
return -1 | |
} | |
} | |
let cache = new Cache(3) | |
cache.put('pie1', 'v01', 50) | |
cache.put('pie2', 'v02', 30) | |
cache.put('pie3', 'v03', 10) | |
cache.put('pie4', 'v04', 20) | |
function get(key) { | |
console.log(key, '->', cache.get(key)) | |
} | |
get('apple') | |
get('pie1') | |
get('pie2') | |
get('pie3') | |
get('pie4') | |
cache.put('pie5', 'v05', 20) | |
cache.put('pie6', 'v06', 20) | |
cache.put('pie7', 'v07', 20) | |
cache.put('pie8', 'v08', 20) | |
cache.put('pie9', 'v09', 20) | |
cache.put('pie10', 'v10', 20) | |
cache.put('pie11', 'v11', 20) | |
get('pie1') | |
get('pie2') | |
get('pie3') | |
get('pie4') | |
get('pie5') | |
get('pie6') | |
get('pie7') | |
get('pie8') | |
get('pie9') | |
get('pie10') | |
get('pie11') |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
let numbers: number[] = new Array(10) | |
numbers[5] = 50 | |
class LinkedList<T> { | |
head: LinkedListNode<T> | null = null | |
add(data: T) { | |
this.add_to_head(data) | |
} | |
*iterate() { | |
let node = this.head | |
while (node) { | |
yield node.data | |
node = node.next | |
} | |
} | |
add_to_head(data: T) { | |
this.head = { data, next: this.head } | |
} | |
add_to_tail(data: T) { | |
if (!this.head) { | |
this.head = { | |
data, | |
next: null, | |
} | |
return | |
} | |
let node = this.head | |
while (true) { | |
if (node.next) { | |
node = node.next | |
continue | |
} | |
node.next = { | |
data, | |
next: null, | |
} | |
} | |
} | |
} | |
interface LinkedListNode<T> { | |
data: T | |
next: LinkedListNode<T> | null | |
} | |
export class HashTable<T> { | |
buckets: Array<LinkedList<{ key: string; value: T }>> | |
constructor() { | |
this.buckets = new Array(10) | |
for (let i = 0; i < this.buckets.length; i++) { | |
this.buckets[i] = new LinkedList() | |
} | |
} | |
set(key: string, value: T) { | |
let index: number = this.hash(key) | |
let bucket = this.buckets[index] | |
bucket.add({ key, value }) | |
} | |
get(key: string): T | null { | |
let index: number = this.hash(key) | |
let bucket = this.buckets[index] | |
for (let item of bucket.iterate()) { | |
if (item.key == key) { | |
return item.value | |
} | |
} | |
return null | |
} | |
hash(key: string): number { | |
// return key.length % this.buckets.length | |
let acc = 0 | |
for (let i = 0; i < key.length; i++) { | |
acc += key.charCodeAt(i) | |
} | |
return acc % this.buckets.length | |
} | |
} | |
let map = new HashTable() | |
map.set('apple', 10) | |
map.set('banana', 20) | |
map.set('cherry', 30) | |
map.set('123456', 40) | |
function get(key: string) { | |
console.log(key, '->', map.get(key)) | |
} | |
get('apple') | |
get('banana') | |
get('cherry') | |
console.dir(map, { depth: 20 }) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment