1
zonghua 2016-08-18 12:45:33 +08:00 via iPhone
实际上是作为循环队列, LRU 就是最少使用缓存算法,队列里把最少用到的排挤掉。用数组每次插入只要从新标志队头和队尾。
|
2
geeti OP |
3
geeti OP 刷题感想。 leetcode 的 LRU 那道题,大家都是定义 linked list,但我发现 functools 里边直接使用 list ,特别简洁。但好像一个 list 比同样一个 node object 要耗内存
|
4
wodesuck 2016-08-18 14:20:43 +08:00 via Android
python 的 object 并不省内存,里面还有__dict__。。
|
5
SlipStupig 2016-08-18 16:13:09 +08:00
@wodesuck 定义一下 __slots__就好了
|
6
langyu 2016-08-18 21:15:20 +08:00
意义不大, 就像用汽车来模拟自行车一样。
|
7
wizardforcel 2016-08-18 21:37:57 +08:00
离散序列结构在插入和删除上省时间,在随机访问上花费时间。
lru 并不需要随机访问,删除倒是很频繁。 |
8
hitmanx 2016-08-19 11:55:01 +08:00 1
有没有比较过两者的效率?可以写个测试 perf 一下。倒是很多在直觉上应该由链表完成的东西,在实际 os 内核的实现里用的都是 array ,就是因为局部性原理带来的效率提升。
|