维持此CAM中的平均查找时间所需的缓存命中率是多少

Question

我讨厌Uni的一个问题，它让我完全被难住了。

一个系统经常进行某种类型的查找;首先是在CAM存储器中，这总是需要m时间。命中的概率是P，如果没有命中，它将在主内存中的表中查找。查找是通过在向量中索引来完成的。在主内存中查找总是导致命中，访问主内存需要M时间。

但是，在索引中用作键的值是分散的，因此向量最终会变得不必要地大。要解决此问题，向量将被另一种需要两个索引才能查找的数据结构所取代。

问题：平均查找时间需要什么新的命中概率P_new才能与旧数据结构保持一致？给出了 5 个选项，尽管可能有多个选项是正确的。

1. P_new = P + 0.5
2. P_new = ((P+1(M + pm((M+m(
3. P_new = (1 - 2P(/2
4. P_new = (P+1(*M/2
5. P_new = (P+1(/2

如果有人知道其中哪些是正确的(更重要的是;为什么它是正确的，而其他的不正确(，如果您能启发我，我将不胜感激。

Answer 1

因此，最终通过使用上一个问题的答案来解决它，该问题将平均查找时间公式定义为T = (1-P(M + m

由于两种情况下的时间 T 应该相同，唯一的区别是主内存中的查找现在需要两倍的时间，我们得到 (1-P(M + m= (1-P_new(2M + m，然后可以简化。

(1-P(M = (1-P_new(2M

1 - P = 2 *(1-P_new( = 2 - 2*P_new

P - 1 = 2*P_new - 2

P + 1 = 2 * P_new

(P + 1(/2 = P_new

因此，正确答案是Nr_5