Loading [MathJax]/jax/input/TeX/jax.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >Google 因果推断的CausalImpact 贝叶斯结构时间序列模型(二十二)

Google 因果推断的CausalImpact 贝叶斯结构时间序列模型(二十二)

作者头像
悟乙己
发布于 2021-12-31 01:03:09
发布于 2021-12-31 01:03:09
1.9K00
代码可运行
举报
文章被收录于专栏:素质云笔记素质云笔记
运行总次数:0
代码可运行

之前一篇:跟着开源项目学因果推断——CausalImpact 贝叶斯结构时间序列模型(二十一)

这里另外写一篇来继续研究一下CausalImpact这个开源库的一些细节的

1 CausalImpact 一些可调参数

1.1 CausalImpact默认的两种算法

CausalImpact默认使用TensorFlow Probability来求的两种算法,分别是Variational InferenceHamiltonian Monte Carlo

切换的方式:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
# HMC
ci = CausalImpact(data, pre_period, post_period, model_args={'fit_method': 'hmc'})

# VI
ci = CausalImpact(data, pre_period, post_period, model_args={'fit_method': 'vi'})

1.2 model_args的可调节模型参数

CausalImpact中,model_args还可以做几种修改:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
standardize: bool
   If `True`, standardizes data to have zero mean and unitary standard
   deviation.
prior_level_sd: Optional[float]
   Prior value for the local level standard deviation. If `None` then an
   automatic optimization of the local level is performed. This is
   recommended when there's uncertainty about what prior value is
   appropriate for the data.
   In general, if the covariates are expected to be good descriptors of the
   observed response then this value can be low (such as the default of
   0.01). In cases when the linear regression is not quite expected to fully
   explain the observed data, the value 0.1 can be used.
fit_method: str
   Which method to use for the Bayesian algorithm. Can be either 'vi'
   (default) or 'hmc' (more precision but much slower).
nseasons: int
 Specifies the duration of the period of the seasonal component; if input
 data is specified in terms of days, then choosing nseasons=7 adds a weekly
 seasonal effect.
season_duration: int
 Specifies how many data points each value in season spans over. A good
 example to understand this argument is to consider a hourly data as input.
 For modeling a weekly season on this data, one can specify `nseasons=7` and
 season_duration=24 which means each value that builds the season component
 is repeated for 24 data points. Default value is 1 which means the season
 component spans over just 1 point (this in practice doesn't change
 anything). If this value is specified and bigger than 1 then `nseasons`
 must be specified and bigger than 1 as well.

其中,

  • standardize = True,需要给入的数据就是标准化过的;
  • nseasons: int,如果想by week来看影响,可以设置为:
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
ci = CausalImpact(data, pre_period, post_period,nseasons=[{'period': 7}],trend=True)
  • prior_level_sd,设定先验标准差
  • season_duration: int,这个要与nseasons联合来看

举一个例子,比如我们现在有by hour的数据,然后我们希望By week来看效果,那么需要设定为:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
df = pd.DataFrame('tests/fixtures/arma_data.csv')
df = df.set_index(pd.date_range(start='20200101', periods=len(data), freq='H'))
pre_period = ['20200101 00:00:00', '20200311 23:00:00']
post_period = ['20200312 00:00:00', '20200410 23:00:00']
ci = CausalImpact(df, pre_period, post_period, model_args={'nseasons': 7,   'season_duration': 24})
print(ci.summary())

这里可以这么理解,如果是Hour粒度数据需要By week看,那就需要每隔 7*24个数据点作为一个batch,所以这里就是nseasons * season_duration

1.3 CausalImpact自定义模型

如果除了提供的VI / HMC都不满足,自己可以自定义:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
      import tensorflow_probability as tfp


      pre_y = data[:70, 0]
      pre_X = data[:70, 1:]
      obs_series = data.iloc[:, 0]
      local_linear = tfp.sts.LocalLinearTrend(observed_time_series=obs_series)
      seasonal = tfp.sts.Seasonal(nseasons=7, observed_time_series=obs_series)
      model = tfp.sts.Sum([local_linear, seasonal], observed_time_series=obs_series)

      ci = CausalImpact(data, pre_period, post_period, model=model)
      print(ci.summary())

分别在3.7.4 和 2.3的案例中都会采用自定义

1.4 CausalImpact如何数据标准化

来看一个来自[test_main.py ],数据是官方项目里面的数据,例子:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
import numpy as np
import pandas as pd
import pytest
import tensorflow as tf
import tensorflow_probability as tfp
from numpy.testing import assert_array_equal
from pandas.util.testing import assert_frame_equal

from causalimpact import CausalImpact
from causalimpact.misc import standardize

data = pd.read_csv('tests/fixtures/btc.csv', parse_dates=True, index_col='Date')
training_start = "2020-12-01"
training_end = "2021-02-05"
treatment_start = "2021-02-08"
treatment_end = "2021-02-09"
pre_period = [training_start, training_end]
post_period = [treatment_start, treatment_end]

pre_data = rand_data.loc[pre_int_period[0]: pre_int_period[1], :]
# 标准化
normed_pre_data, (mu, sig) = standardize(pre_data)
# mu / sig如何让原数据post_data  ->  标准化之后的normed_post_data 

normed_post_data = (post_data - mu) / sig

使用causalimpact.misc进行标准化; 如果你自行标准化之后,在训练模型的时候,需要:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
model_args == {'fit_method': 'hmc', 'niter': 1000, 'prior_level_sd': 0.01,  'season_duration': 1, 'nseasons': 1, 'standardize': True}

2 协变量回归系数解读

在整个模型中会有:

yt=ZTtαt+βXt+Gtϵt

其中线性部分,拆出来单独理解

2.1 Horseshoe prior的Bayes回归

来自统计之都的一篇文章先认识一下Horseshoe prior: 使用Horseshoe 先验的Bayes回归及代码解析 以及: 稀疏数据分析:马蹄估计量及其理论性质

也贴一段,tensorflow_probability感觉写的很好:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
  The Cauchy scale parameters puts substantial mass near zero, encouraging
  weights to be sparse, but their heavy tails allow weights far from zero to be
  estimated without excessive shrinkage. The horseshoe can be thought of as a
  continuous relaxation of a traditional 'spike-and-slab' discrete sparsity
  prior, in which the latent Cauchy scale mixes between 'spike'
  (`scales[i] ~= 0`) and 'slab' (`scales[i] >> 0`) regimes.
  Following the recommendations in [2], `SparseLinearRegression` implements
  a horseshoe with the following adaptations:
  - The Cauchy prior on `scales[i]` is represented as an InverseGamma-Normal
    compound.
  - The `global_scale` parameter is integrated out following a `Cauchy(0.,
    scale=weights_prior_scale)` hyperprior, which is also represented as an
    InverseGamma-Normal compound.
  - All compound distributions are implemented using a non-centered
    parameterization.
  The compound, non-centered representation defines the same marginal prior as
  the original horseshoe (up to integrating out the global scale),
  but allows samplers to mix more efficiently through the heavy tails; for
  variational inference, the compound representation implicity expands the
  representational power of the variational model.
  Note that we do not yet implement the regularized ('Finnish') horseshoe,
  proposed in [2] for models with weak likelihoods, because the likelihood
  in STS models is typically Gaussian, where it's not clear that additional
  regularization is appropriate. If you need this functionality, please
  email tfprobability@tensorflow.org.

Horseshoe prior是一种稀疏bayes监督学习的方法。通过对模型参数的先验分布中加入稀疏特征,从而得到稀疏的估计。

horseshoe prior属于multivariate scale mixtures of normals的分布族。所以和其他常用的稀疏bayes学习方法,Laplacian prior, (Lasso), Student-t prior,非常类似。

其中λj 叫做local shrinkage parameter,局部压缩参数,对于不同的θj 可以有不同的压缩系数,τ 叫做global shrinkage parameter其中,half-Cauchy分布的概率密度函数:

回看上面三层先验,上面a 就可以带入各自的先验:

考虑λi 的边缘先验分布

定义κi=1/(1+λ2i) 这个量在Bayesian shrinkage中非常重要,我们在下一个小标题介绍它的意义,但我们可以先分析它的先验分布。现在我们只想做一点定性分析,了解一下κi 的先验的形状,所以简单起见假设σ=τ=1 ,于是

因此 kiBeta(1/2,1/2) ,来看ki 的先验分布,这里可以看到a =β =0.5的时候,就会出现马蹄状,基于这种先验的贝叶斯方法被称为马蹄估计。

这里有一段tensorflow_probability 中的评价:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
The Cauchy scale parameters puts substantial mass near zero, encouraging   weights to be sparse, but their heavy tails allow weights far from zero to be   estimated without excessive shrinkage.
The horseshoe can be thought of as a   continuous relaxation of a traditional 'spike-and-slab' discrete sparsity   prior, in which the latent Cauchy scale mixes between 'spike'   (`scales[i] ~= 0`) and 'slab' (`scales[i] >> 0`) regimes.

2.2 SparseLinearRegression的weight计算逻辑

因为在CausalImpact 会使用SparseLinearRegression,我来看一下回归部分的系数weight求解,参考下面公式:

来到tensorflow_probability的源代码中看到:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
This is identical to `tfp.sts.LinearRegression`, except that   `SparseLinearRegression` uses a parameterization of a Horseshoe prior [1][2] to encode the assumption that many of the `weights` are zero,  i.e., many of the covariate time series are irrelevant.

可以看到local scales 是服从HalfCauchy分布:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
scales[i] ~ HalfCauchy(loc=0, scale=1)
weights[i] ~ Normal(loc=0., scale=scales[i] * global_scale)`

由伪代码来看整个回归系数计算过程:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
# Sample global_scale from Cauchy(0, scale=weights_prior_scale).
global_scale_variance ~ InverseGamma(alpha=0.5, beta=0.5)
global_scale_noncentered ~ HalfNormal(loc=0, scale=1)
global_scale = (global_scale_noncentered *
               sqrt(global_scale_variance) *
               weights_prior_scale)
# Sample local_scales from Cauchy(0, 1).
local_scale_variances[i] ~ InverseGamma(alpha=0.5, beta=0.5)
local_scales_noncentered[i] ~ HalfNormal(loc=0, scale=1)
local_scales[i] = local_scales_noncentered[i] * sqrt(local_scale_variances[i])
weights[i] ~ Normal(loc=0., scale=local_scales[i] * global_scale)

weights[i] ~ Normal(loc=0., scale=local_scales[i] * global_scale)开始反着看,weight = local的λj 和 global的τ 的相乘。

2.3 案例推导回归系数的计算

如果默认VI算法的情况下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
import numpy as np
import pandas as pd
import pytest
import tensorflow as tf
import tensorflow_probability as tfp
from numpy.testing import assert_array_equal
from pandas.util.testing import assert_frame_equal

from causalimpact import CausalImpact
from causalimpact.misc import standardize

data = pd.read_csv('../tests/fixtures/btc.csv', parse_dates=True, index_col='Date')
training_start = "2020-12-01"
training_end = "2021-02-05"
treatment_start = "2021-02-08"
treatment_end = "2021-02-09"
pre_period = [training_start, training_end]
post_period = [treatment_start, treatment_end]


rand_data = data
pre_int_period = pre_period
post_int_period = post_period
ci = CausalImpact(rand_data, pre_int_period, post_int_period)


for name, values in ci.model_samples.items():
    print(f'{name}: {values.numpy().mean(axis=0)}')

本来官方教程里面默认算法下的一些标准差为:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
print('Mean value of noise observation std: ', ci.model_samples[0].numpy().mean())
print('Mean value of level std: ', ci.model_samples[1].numpy().mean())
print('Mean value of linear regression x0, x1: ', ci.model_samples[2].numpy().mean(axis=0))

可以看到三个比较明显的指标,noise std,level std,回归系数。 那么现在的版本,可以看到ci.model_samples是一个dict形,然后得出有,

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
observation_noise_scale: 0.455566942691803
LocalLevel/_level_scale: 0.01129493024200201
SparseLinearRegression/_global_scale_variance: 0.8674567341804504
SparseLinearRegression/_global_scale_noncentered: 0.9352844953536987
SparseLinearRegression/_local_scale_variances: [1.4979423  1.3915676  2.5401886  0.82398146 1.3655316  1.3455669
 1.2680935  0.9430675  2.4824152 ]
SparseLinearRegression/_local_scales_noncentered: [0.6454335  1.1153866  1.5575289  0.39585915 0.85925627 0.964816
 0.7337909  0.7373393  1.4985642 ]
SparseLinearRegression/_weights_noncentered: [-0.31404912  1.3935399   1.904644   -0.769298    0.7848593   0.53083557
  0.9080193   0.37757748  1.6231401 ]

observation_noise_scaleLocalLevel/_level_scale 与之前一样,这里LR改成了,特有的SparseLinearRegression

再返回CausalImpact 的输出结果:

  • causalimpact 的issue
  • tensorflow_probability

先来看tensorflow_probability 的源码,可以从Line298开始看:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
  def params_to_weights(
                        global_scale_variance,
                        global_scale_noncentered,
                        local_scale_variances,
                        local_scales_noncentered,
                        weights_noncentered,
  weights_prior_scale = 0.1):
    """Build regression weights from model parameters."""
    global_scale = (global_scale_noncentered *
                    tf.sqrt(global_scale_variance) *
                    weights_prior_scale)

    local_scales = local_scales_noncentered * tf.sqrt(local_scale_variances)
    return weights_noncentered * local_scales * global_scale[..., tf.newaxis]

其中weights_prior_scaleThe weights_prior_scale determines the level of sparsity; small scales encourage the weights to be sparse. 是先验分布的参数,决定稀疏程度,一般默认为0.1

再来看一下weight输出的结果,是weights.shape == [num_users, num_features],不像之前

再是causalimpact 的issue,参考 : Printing averages of the posterior does not work #24

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
import tensorflow as tf


weights_prior_scale = 0.1
global_scale_nonentered = param_samples['SparseLinearRegression/_global_scale_noncentered']
global_scale_variance = param_samples['SparseLinearRegression/_global_scale_variance']
local_scales_noncentered = param_samples['SparseLinearRegression/_local_scales_noncentered']
local_scale_variances = param_samples['SparseLinearRegression/_local_scale_variances']
global_scale = global_scale_nonentered * tf.sqrt(global_scale_variance) * weights_prior_scale
weights_noncented = param_samples['SparseLinearRegression/_weights_noncentered']
local_scales = local_scales_noncentered * tf.sqrt(local_scale_variances)

weights = weights_noncented * local_scales * global_scale[..., tf.newaxis]

# 按样本的权重,100个
weights.numpy().mean(axis=1)

# 按特征的权重 ,2个
weights.numpy().mean(axis=0)

# 所有的平均权重,1个
weights.numpy().mean(axis=1).mean()

如果有了weight,那如何进行预测,可以简单看一下预测的逻辑:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
predicted_timeseries = self.design_matrix.matmul(weights[..., tf.newaxis])
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021/12/29 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
146. LRU 缓存机制
要在O(1)时间复杂度完成这两种操作,我们想到的使用HashMap来进行操作,而且参考LRUCache的特性,需要对元素进行移动或者删除,首选的是双向链表。
用户7447819
2021/07/23
2960
LeetCode146. LRU缓存机制
 基础数据结构的应用,HashMap中存的是key和Node,Node中存的是key和value
mathor
2018/08/16
3430
LeetCode146. LRU缓存机制
【LeetCode】146. LRU 缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类:
韩旭051
2021/01/07
4620
Leetcode LRU 缓存机制
缓存是一种提高数据读取性能的技术,在计算机中cpu和主内存之间读取数据存在差异,CPU和主内存之间有CPU缓存,而且在内存和硬盘有内存缓存。当主存容量远大于CPU缓存,或磁盘容量远大于主存时,哪些数据应该被应该被清理,哪些数据应该被保留,这就需要缓存淘汰策略来决定。常见的策略有三种:先进先出策略FIFO(First In,First Out)、最少使用策略LFU(Least Frequently Used)、最近最少使用策略LRU(Least Recently Used)。
用户10384376
2023/02/25
3170
Leetcode LRU 缓存机制
【Leetcode】146.LRU缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。
Leetcode名企之路
2019/03/18
1.1K0
【Leetcode】146.LRU缓存机制
2020-09-18:LRU手撸,说下时间复杂度和空间复杂度。
空间复杂度:O(capacity),因为哈希表和双向链表最多存储 capacity+1 个元素。
福大大架构师每日一题
2020/09/18
1.1K0
2020-09-18:LRU手撸,说下时间复杂度和空间复杂度。
实现 LRU 缓存算法
LRU 算法全称是最近最少使用算法(Least Recently Use),是一种简单的缓存策略。顾名思义,LRU 算法会选出最近最少使用的数据进行淘汰。
Se7en258
2022/06/24
1K0
实现 LRU 缓存算法
LeetCode-146-LRU缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。
benym
2022/07/14
3100
经典算法之链表篇(三)
ma布
2024/10/21
1060
经典算法之链表篇(三)
☆打卡算法☆LeetCode 146. LRU 缓存 算法解析
请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类:
恬静的小魔龙
2022/08/07
3150
☆打卡算法☆LeetCode 146. LRU 缓存 算法解析
LRU 缓存机制实现:哈希表 + 双向链表
LRU 缓存机制可以通过哈希表辅以双向链表实现,我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
一个会写诗的程序员
2021/03/23
2K0
LRU 缓存机制实现:哈希表 + 双向链表
搞定大厂算法面试之leetcode精讲15.链表
搞定大厂算法面试之leetcode精讲15.链表 视频讲解(高效学习):点击学习 目录: 1.开篇介绍 2.时间空间复杂度 3.动态规划 4.贪心 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.单调栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其他类型题 链表操作如下图: 动画过大,点击查看 时间复杂度: prepend: O(1
全栈潇晨
2021/12/02
4490
一个今日头条的面试题——LRU原理和Redis实现
很久前参加过今日头条的面试,遇到一个题,目前半部分是如何实现 LRU,后半部分是 Redis 中如何实现 LRU。
Java架构
2018/09/20
2.1K0
一个今日头条的面试题——LRU原理和Redis实现
LRU算法与Caffeine、Redis中的缓存淘汰策略
在现代计算机系统中,缓存是提高系统性能的关键技术之一。为了避免频繁的IO操作,常见的做法是将数据存储在内存中的缓存中,以便快速访问。然而,由于内存资源有限,缓存的大小是有限的,因此需要一种策略来淘汰缓存中的数据,以便为新的数据腾出空间。本文将介绍一种常用的缓存淘汰策略——最近最少使用(Least Recently Used,LRU)算法,并且比较它与Caffeine和Redis中的缓存淘汰策略。
疯狂的KK
2023/08/17
5240
LRU算法与Caffeine、Redis中的缓存淘汰策略
数据结构界的“六脉神剑”:数组、链表、哈希表、栈、队列、树的终极解析与实战演练
在编程的世界里,数据结构是构建高效算法的基石。它们就像是武侠小说中的武功秘籍,掌握了它们,就能在代码的江湖中游刃有余。今天,我们就来深入探讨数据结构界的“六脉神剑”——数组、链表、哈希表、栈、队列和树。这六种数据结构,每一种都有其独特的运行原理和应用场景,它们是编程高手的必备技能。
疯狂的KK
2024/05/06
2870
数据结构界的“六脉神剑”:数组、链表、哈希表、栈、队列、树的终极解析与实战演练
146. LRU 缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类: LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。 void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之
编程张无忌
2021/06/29
2310
漫画:LRU从实现到应用层层剖析(第一讲)
LRU是Least Recently Used的缩写,译为最近最少使用。它的理论基础为“最近使用的数据会在未来一段时期内仍然被使用,已经很久没有使用的数据大概率在未来很长一段时间仍然不会被使用”由于该思想非常契合业务场景 ,并且可以解决很多实际开发中的问题,所以我们经常通过LRU的思想来作缓存,一般也将其称为LRU缓存机制。因为恰好leetcode上有这道题,所以我干脆把题目贴这里。但是对于LRU而言,希望大家不要局限于本题(大家不用担心学不会,我希望能做一个全网最简单的版本,希望可以坚持看下去!)下面,我们一起学习一下。
程序员小浩
2020/03/30
3440
漫画:LRU从实现到应用层层剖析(第一讲)
Leetcode模块训练2
1. 两数之和(1)# 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1: 输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。 示例 2: 输入:nums = [3,2
素履coder
2022/11/16
3370
LRU算法简介
LRU(Least Recently Used)算法是一种缓存淘汰算法,常用于缓存系统中,通过保留最近使用的数据而淘汰最久未使用的数据,以提高缓存的命中率。LRU算法的核心思想是基于时间局部性原理:最近访问的数据在未来会被再次访问。
孟斯特
2024/01/28
6680
LRU算法简介
【LeetCode热题100】【链表】LRU缓存
我昨天面了天美L1的游戏客户端开发,面了我100分钟,问完实习、项目、计算机图形学和C++后给了我两道算法题做,一道是最长公共子序列,一道是LRU缓存,我知道是经典的题目,但是我都没敲过,我之前写过一个KV的数据库系统用过LRU(最近最少使用)缓存,用的是双向链表和哈希表解决的,当时是实现了一个双向链表,用来存储value,哈希表存储key和对应存储value的链表节点的指针,最近被访问的key就把它的节点移到链表头,超过容量就删掉链表尾
叶茂林
2024/03/31
920
相关推荐
146. LRU 缓存机制
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验