哈,喷下时间戳和链扫描

中山野鬼 发布于 2017/01/15 22:54
阅读 653
收藏 0

@乌龟壳 关于链的扫描,在我自己做的库中,大体的算法如下:(假设链的节点不会超过 2的32次方。 则每个节点存在一个32位正整数的时间戳成员)

1、每次扫描,总会先额外做个工作,按存储空间顺序,更新一个节点的时间戳。这样,总能能在2的32次方次扫描前,所有存储节点的时间戳被更新,也即,任意节点的时间戳所记录的数值与当前的计次数值的距离不会大于2的32次方

2、每扫描一个节点前,更新扫描计数(累加)

3、判断该节点的时间戳的计数是否与本次扫描计数相等,如果相等则表示访问过。

4、每次访问过的节点,将本次扫描计数的值写入时间戳的成员数据中。

这样做,会费些存储,相对bit map的方式,不过每次扫描前额外的计算工作会很少。所以没啥特定应用环境时,我都是这么玩。哈。

加载中
1
乌龟壳
乌龟壳
首先你这个算法要解决什么问题没看懂。 其次,第一条看不懂
1
紅顏為君笑
紅顏為君笑
时不时的诈尸 太可怕了
快速开发师
快速开发师
他“哈”两下,你也要变成尸
0
宏哥
宏哥
用pg bitmap index不是更容易
0
滔哥
滔哥
好久不见,野鬼!
0
快速开发师
快速开发师
该评论暂时无法显示,详情咨询 QQ 群:点此入群
0
中山野鬼
中山野鬼

引用来自“乌龟壳”的评论

首先你这个算法要解决什么问题没看懂。 其次,第一条看不懂
解决链扫描时,如何判断某个节点被访问过。哈。
中山野鬼
中山野鬼
回复 @乌龟壳 : 确实不是一回事,我只是在讨论链表扫描时,判断节点访问过的问题。至于时间戳,不同系统下,有不同的解释和实现。不过总是在解决那些,区分时间轴(不同时间节点)事件的问题。哈
乌龟壳
乌龟壳
先不论这个算法效率啊之类的,你说的这个好像和之前有人问的内容不是一回事。然后回到算法本身,时间戳是什么?如果是所谓的unix timestamp之类的,这种算法会用到时钟时间始终不太好。如果是一个自增的量,每次扫描自增1还说的过去。
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部