缓冲更新的算法？
输入端每秒输入约4000个数据块， 每个数据块的长度在 512 Byte 到 2048 Byte不等
我对这些数据块加工（比较耗费时间）后送往输出端。 实际上，有很多数据块是会重
复的。 为了减少加工负担，我在输入和处理之间加入了一定容量的缓冲。这样，在处
理数据时我就先在缓冲中查看有没有处理过，如果在缓冲中，就直接送出结果数据，否
则再处理，然后把当前数据块放入缓冲。 我要解决的问题是如何进行缓冲区内容的更新，
才能达到比较高的缓冲命中率。 伪代码如下:
{ Data = GetNextData; //获取下一输入块
CacheHit = SearchInCache(Data); //在缓冲中查找
IF CacheHit>0
OutPut( ResultInCache(Cachehit) ) //命中则直接出结果
Else
{ Result:=DataProcess(Data); //未命中先处理
OutPut(Result); //输出结果
CacheUpdate(Data,Result); } *****更新缓冲内容****
}
问题就在 如何优化地更新缓冲内容,书上的FIFO,LRU,LFU都不理想
问题点数：70、回复次数：16Top
1 楼lhztco99（环保概念股）回复于 2001-01-08 10:41:00 得分 0
请多多讨论，也许哪天你也能用到呢！Top
2 楼seman（西曼）回复于 2001-01-08 11:53:00 得分 10
使用HASH表Top
3 楼xzjxu（糊涂神仙）回复于 2001-01-26 13:05:00 得分 0
主要是设多少个缓冲性价比好Top
4 楼xzjxu（糊涂神仙）回复于 2001-01-26 16:54:00 得分 0
数据的规律Top
5 楼rchu（可怜的老马）回复于 2001-02-01 01:10:00 得分 20
如果你学过体系结构，应该知道对于CPU cache的算法而言，关键是要减少搜索时间，
因此，用hash应该是比较理想的，目前的CPU通常都是两路或四路组相连，最疯狂的
不过八路组相连。因为硬件实现复杂，软件上其实也一样，实现不复杂，但是速度慢，
建议你试一下4路组相连Top
6 楼xzjxu（糊涂神仙）回复于 2001-02-01 01:43:00 得分 40
to rchu,
CPU cache是根据局部性原理设计的，而lhztco99的问题中没有提到数据的规律，所以没有办法确定最优算法。Top
7 楼lhztco99（环保概念股）回复于 2001-02-01 13:33:00 得分 0
谢谢 rchu(可怜的老马) xzjxu(常新)的回答 ，我还想再等等。
另外 To rchu(可怜的老马): 我的搜索时间不成问题，只是想
缓冲能达到它的最大效用。
To xzjxu(常新): 数据的具体概率是不定的，我也不求最好
的算法，只要比操作系统自己的页面调度
好点就行了。 Top
8 楼xzjxu（糊涂神仙）回复于 2001-02-02 12:48:00 得分 0
to lhztco99,
数据的重复概率是什么？就是大概多长时间来一个重复的数据？Top
9 楼xzjxu（糊涂神仙）回复于 2001-02-02 12:49:00 得分 0
to lhztco99,
否则，缓冲是没有意义的Top
10 楼lhztco99（环保概念股）回复于 2001-02-02 15:32:00 得分 0
这样的 有一定量的数据A某一时间段经常出现 随后可能
长时间不出现 这段时间的数据B基本是新的 然后又有
一段时间经常出现前述的数据A 然后又有一段时间经常出
现数据B 怎样让缓冲更新的算法能够利用这个规律呢？
能够很好的保留A和B中的高频数据块？而且要内存和运算
开销小一点。否则就失去意义了。
Top
11 楼xzjxu（糊涂神仙）回复于 2001-02-02 16:10:00 得分 0
to lhztco99,
是不是在一个小的时间段里数据集中在某几个（n)数据上?
那么可以设n大小的缓冲，提取数据时先到缓冲查找
更新规律是尽量保持最近的数据Top
12 楼xzjxu（糊涂神仙）回复于 2001-02-02 16:12:00 得分 0
给数据设个命中次数，尽量保持命中次数高的数据
Top
13 楼xzjxu（糊涂神仙）回复于 2001-02-02 16:14:00 得分 0
一旦有m次不命中就抛弃Top
14 楼xzjxu（糊涂神仙）回复于 2001-02-02 16:22:00 得分 0
to lhztco99,
是不是在一个小的时间段里数据集中在某几个（n)数据上?
那么可以设n大小的缓冲，提取数据时先到缓冲查找
更新规律是:
给数据设个命中次数，尽量保持命中次数高的数据,其次尽量保持最近的数据，
一旦有m次不命中就可以被更新（就是降低它的命中次数）
Top
15 楼lhztco99（环保概念股）回复于 2001-02-05 14:22:00 得分 0
还是自己想吧 不过还是谢谢几位 Top
16 楼skt985（傻问天）回复于 2001-06-01 09:34:00 得分 0
82850关注！Top
