沧海一粟

天下事有难易乎?为之,则难者亦易矣;不为,则易者亦难矣。

0%

Hash (哈希,或者散列)函数在计算机领域,尤其是数据快速查找领域,加密领域用的极广。

其作用是将一个大的数据集映射到一个小的数据集上面(这些小的数据集叫做哈希值,或者散列值)。

一个应用是Hash table(散列表,也叫哈希表),是根据哈希值 (Key value) 而直接进行访问的数据结构。
也就是说,它通过把哈希值映射到表中一个位置来访问记录,以加快查找的速度。下面是一个典型的 hash 函数 / 表示意图:

hash

阅读全文 »

在遇到有关联关系 并且 数据量很大时,会遇到一个很头疼的问题,就是要处理的数据量太大,效率很低。
比如用户画像系统、每天的活跃用户、商品适配、人际关系 等。

以用户画像系统为例,如果用户数 < 500万 并且 标签数 也不多,可以用传统的关系型数据库直接查询。
但是当数据数很多 或者 查询比较复杂时,关系型数据会效率会很低。就得想想其它办法。

  1. 优化算法
  2. 数据压缩
  3. 压缩维度展示(类似数据压缩)

(1) 优化算法

用户画像系统
用户 张三、李四
用户标签 学生、单身、90后、程序员

统计 标签是90后 程序员 的用户
mysql条件查询

统计 标签是90后 或 程序员 的用户个数
mysql 查询 取并集

当 用户数过多 (500万用户) 或 标签过多(10万标签) 时,mysql的效率很低。

假设
user_id int类型,占4字节, 1千万用户 也就是 4 40 000 000 byte = 160M
user_name varchar(8) 使用utf-8编码 占24字节 也就是 24
40 000 000 byte = 480M

tag_id int类型,占4字节,10万标签 也就是 4 * 100000 byte = 400 000 = 400K

用户 和 标签 是多对多关系,假设有一张 用户标签表, 有1千万行 10万列, 每一行需要 (user_id + 100 000 tag_id ) 4 byte 10 000 000 ≈ 4000G

得换一种办法。

bitmap
一个标签对应多个用户
标签id化,用户id化 (倒排索引)

每个标签 一个bitmap ,这个bitmap存储了用户信息,用户是500万,实际存储需要 2^23 bit = 2^23 / 8 byte ≈ 1MB
有 10万标签 100 000 * 1MB = 100 GB

这个算的是所有的用户和标签,实际上可以只处理需要的。可以过滤掉很多用户和标签。
用户数过滤一部分,其实 一个bitmap 实际存储会变成 2^22 bit = 2^22 / 8 byte ≈ 0.5MB
只处理常用的标签,实际常用的大概1000,1000 * 0.5MB = 5G

根据标签查对应用户,拿到结果后 并集 交集 差集

统计 标签是90后 程序员 的用户
根据标签查对应用户,拿到结果后 交集

统计 标签是90后 或 程序员 的用户个数
根据标签查对应用户,拿到结果后 并集

阅读全文 »

Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。例如 网页URL的去重,垃圾邮件的判别,集合重复元素的判别,查询加速(比如基于key-value的存储系统)等。

阅读全文 »

俗话说,工欲善其事必先利其器。
平常在使用Windows自带的cmd复制粘贴太麻烦,而且cmd在中国用的是gbk编码,有的时候想用UTF-8编码,感觉cmd不太好用,就想找一个替代品,看了powershell,git bash(mingw64) cmder,最后觉得cmder好用。
Cmder1.3.2版本中,可以使用cmd,bash,git-bash。感觉特别方便。

阅读全文 »

总结了很多东西,放在博客上,担心有一天本地的文件损坏或者丢失,就想了一个办法,用Git来备份本地的博客。
有一个问题是博客目录是一个git仓库,博客目录下的themes目录下的一个theme又是一个git仓库,如果git不熟悉,在这儿肯定会犯错。

阅读全文 »

MySQL的一些基础知识。

对比 MySQL Excel
数据库 database 一个excel
table 一个sheet
row 一个sheet里的一行数据
字段 column 一列
阅读全文 »

隐马尔科夫学习

  先来玩一个掷骰子的游戏。
  游戏规则:假设我手里有三个不同的骰子。第一个骰子是我们平常见的骰子(称这个骰子为D6),6个面,每个面(1,2,3,4,5,6)出现的概率是1/6。第二个骰子是个四面体(称这个骰子为D4),每个面(1,2,3,4)出现的概率是1/4。第三个骰子有八个面(称这个骰子为D8),每个面(1,2,3,4,5,6,7,8)出现的概率是1/8。
假设我们开始掷骰子,我们先从三个骰子里随机挑一个,掷骰子,得到一个数字,然后再随机挑一个骰子,再掷骰子,得到一个数字,重复这个过程10次。我们会依次得到10的点数。

第一种玩法,我告诉你我用了几个骰子(包括骰子的详细信息),告诉你这十次掷的点数依次是多少,你来猜每次用的是哪个骰子。
第二种玩法,我告诉你我用了几个骰子(包括骰子的详细信息),告诉你这十次掷的点数依次是多少,你来猜依次掷出这十个点的概率。
第三种玩法,我告诉你我用了几个骰子(不告诉你骰子的详细信息),告诉你这十次掷的点数依次是多少,你来猜这几种骰子分别是什么骰子(要说出骰子的详细信息)。

阅读全文 »

看到好多人说idea好用,自己也想试试。结果发现上手的时候比较难,一旦上手,真的是爱不释手。
比eclipse好用多了。
举一个很简单的例子。

1
2
3
在main方法里写了下面一行代码
double a;
a = args[2]; // idea 会在这行代码下标红线,提示有错误

(1) 下载及安装

http://www.jetbrains.com/idea/download/

推荐使用社区版,资源占用少,而且不用担心license问题,缺点是部分功能支持不好

阅读全文 »

1 下载及安装

在Eclipse官网 下载页面选择对应的版本下载,这里提供一个下载链接
下载的是zip安装包,解压完就可以使用

2 配置

1.设置JDK

Window - Preferences - Java - Installed JREs - Add - Standard VM - 选中JDK安装目录的jdk1.7.0_80文件夹
Eclipse配置JDK

阅读全文 »