首页   注册   登录
 zealic 最近的时间轴更新

zealic

V2EX 第 78179 号会员,加入于 2014-10-23 10:34:37 +08:00
今日活跃度排名 19554
zealic 最近回复了
1 天前
回复了 Travis 创建的主题 分享创造 做了个 zerotier 的自动镜像
奥~康么~达令~ **** **
23 天前
回复了 littleb 创建的主题 成都 想在成都上车 LOFT,但是有几个现实问题
这个地段位置很垃圾的,IT 行业工作地点基本在南边高新区,除非你能忍受一个班小时的单程通勤,以及开车每天堵半小时+半小时路程,否则千万不要买。
上面的算

首次读取需要读取所有数据,以后增量数据就极其方便,开销几乎可以忽视
如果对于读取数据有比较高的要求,也可以 MapReduce 并行运行

完成后的也可以通过 Redis 做一二级缓存,完成后可以直接判断 ID 是否存在,以及 ID 总数
落地磁盘做三级缓存,这样以后都不用再次统计数据
详细说下我在一楼说的算法

(Bitmap + 二叉树) x 链表

空间最小化,根据已知条件,最坏的情况下内存占用为 645K,计算量也不大

算法细节为,

BitmapBinaryTree,六级,1->2-4->8->16->32
然后循环所有 ID,每个 ID 置位 Bitmap,发现重复的 ID 就创建一个新的 BitmapBinaryTree 并置位
如此循环最多创建 10000 个 BitmapBinaryTree
因为大多数 ID 不重复,大部分数据位只会存在于第一个 BitmapBinaryTree

那么最终数据结构应该叫做 BinaryTreeChain,数据结构如下

type BinaryTreeChain struct {
Left *Bitmap128
Right *Bitmap128
Next *BinaryTreeChain

// 二分查找对应的 Bitmap8 并置位,若设置成功返回,否则代表重复
// 重复需要创建或查找 Next 链并置位
SetByID(id int256) bool
//获取值
GetByID(id int256) bool
// 计算总数
CountByID(id int256) bool
}

type Bitmap128 struct {
Left *Bitmap64
Right *Bitmap64
}

type Bitmap64 struct {
Left *Bitmap32
Right *Bitmap32
}

type Bitmap32 struct {
Left *Bitmap16
Right *Bitmap16
}


type Bitmap16 struct {
Left *Bitmap8
Right *Bitmap8
}

type Bitmap8 = byte
Bitmap
@abirdcanfly 可联系详聊,邮箱就是用户名 gmail
关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   939 人在线   最高记录 4385   ·  
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.3 · 8ms · UTC 22:26 · PVG 06:26 · LAX 15:26 · JFK 18:26
♥ Do have faith in what you're doing.
沪ICP备16043287号-1