算法与数据结构—应用篇

垃圾短信过滤

基于黑名单： 如布隆过滤器 基于规则的过滤器 基于概率统计的过滤器，如朴素贝叶斯算法

简单的音乐推荐系统

原理： 找到跟你口味偏好相似的用户，把他们爱听的歌曲推荐给你； 找出跟你喜爱的歌曲特征相似的歌曲，把这些歌曲推荐给你。

欧几里得距离 计算两个向量之间的距离，sqrt((x1-y1)^2 + (x2-y2)^2 +(x3-y3)^2 + ….+(xk-yk)^2 )

基于相似用户做推荐 每个用户对所有歌曲的喜爱程度，都用一个向量表示。数值表示喜爱程度， 小明 (5, 3, 4, 5, 0, -1, 2, 3, 4,5) 小王 (-1, 2, 3, 4,5,5, 3, 4, 5, 0 ) 小李 (4, 3, 4, 5, 0, -1, 2, 3, 4,5) 欧几里得距离越小，高纬空间距离约接近，则两人口味月接近。

基于相似的歌曲做推荐 如果用户是一个新用户，我们还没有收集到足够多的行为数据，基于相似歌曲的推荐方法， 方式一：对歌曲打标签，如纯音乐，伤感，开心，钢琴，流行，电音，印第安，等维度。欧几里得距离小的即为相似歌曲。但这个可能需要大量的人工。 方式二：如果两首歌，喜欢的人群差不多则定位相似歌曲。 如下，括号里的数字为同一批用户对歌曲的喜爱程度，依然是欧几里得距离小的算作相似歌曲 十年(5, 3, 4, 5, 0, -1, 2, 3, 4,5) 吻别(-1, 2, 3, 4,5,5, 3, 4, 5, 0 ) 勇气 (4, 3, 4, 5, 0, -1, 2, 3, 4,5)

推荐系统（Recommender System）是典型的机器学习应用场景。其核心就是通过算法得到用户偏好向量以及内容向量，两个向量的内积即为用户对内容的的评分预测（即用户对某内容的喜好程度）。推荐学习算法本质上就是学习这两个向量的过程。 通常有两种方法：

  1. 已知内容向量，学习用户偏好向量的方法就是基于内容的推荐算法（content-based）；
  2. 用户偏好向量和内容向量都未知，则适合使用联合过滤算法（collaborative filtering）同时学习两个向量。

mysql B+树索引

B+树和跳跃表的结构很相似的。可以实现logn查找，也能实现范围快速查找。 B+树只有叶子节点才存储数据。并且从前往后递增，这样可以实现范围查找。而且可以让上层索引节点存更多的有效数据，减少io次数。

B+树为N叉平衡查找树, N值是根据页的大小事先计算好的。每个节点等于页大小，往一个节点插入数据可能导致页分裂，当节点数小于N/2时（阈值根据情况调整），进行页合并。

为什么要用B+树来建索引？其他的查找树可以吗？ 普通的二叉查找树，没法支持快速范围查询。（改造：所有数据都下放到叶子节点，并用指针把叶子节点前后连起来，先O(logn)查到临界点，然后在叶子节点往前后遍历即可。）

B+ 树的特点m叉树

  • 每个节点中子节点的个数不能超过 m，也不能小于 m/2；
  • 根节点的子节点个数可以不超过 m/2，这是一个例外；
  • m 叉树非叶子节点只存储索引，并不真正存储数据，有点儿类似跳表；
  • 通过链表将叶子节点串联在一起，这样可以方便按区间查找；
  • 通常根节点会被存储在内存中，其他节点存储在磁盘中。

B树与B+树的区别

  • B+ 树中的节点不存储数据，只是索引，而 B 树中的节点存储数据。
  • B 树中的叶子节点并没有链表来串联。
  • 以上两点都算是B树如果作为索引的不足。B 树只是一个每个节点的子节点个数不能小于 m/2 的 m 叉树。
/**
 * B+ 树非叶子节点的定义。
 * 假设 keywords=[3, 5, 8, 10]
 * 4 个键值将数据分为 5 个区间：(-INF,3), [3,5), [5,8), [8,10), [10,INF)
 * 5 个区间分别对应：children[0]...children[4]
 *
 * m 值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
 * PAGE_SIZE = (m-1)*4[keywords大小]+m*8[children 大小]， 8指的是引用（指针）占的内存大小
 */
class BPlusTreeNode {
	public static int m = 5;	//5叉树
	public int[] keywords = new int[m-1]; // 键值，用来划分数据区间 ？
	public BPlusTreeNode[] children = new BPlusTreeNode[m];
}

/**
 * B+ 树中叶子节点
 *
 * B+ 树中的叶子节点跟内部结点是不一样的,
 * 叶子节点存储的是值，而非区间。
 * 这个定义里，每个叶子节点存储 3 个数据行的键值及地址信息。
 *
 * k 值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
 * PAGE_SIZE = k*4[keyw.. 大小]+k*8[dataAd.. 大小]+8[prev 大小]+8[next 大小]
 */
class BPlusLeafNode {
	//前驱指针，后继指针，数据
	public static int k = 3;
	public int[] keywords = new int[k];		//数据的键值 ?
	public long[] dataAddr = new long[k];	//数据地址 ?
	
	public BPlusLeafNode prev;	//前驱节点
	public BPlusLeafNode next;	//后继节点
	
}

寻路功能

Dijkstra 最短路径算法的执行耗时会很多。超级大的地图和海量的寻路请求，算法的执行效率太低。实际上，像出行路线规划、游戏寻路，一般都是在兼顾计算效率下的次优解。

A* 算法 A* 算法是对 Dijkstra 算法的优化和改造 Dijkstra 算法有点儿类似 BFS 算法，它每次找到跟起点最近的顶点，往外扩展。

要找出起点 s 到终点 t 的最短路径，最简单的方法是，过回溯穷举所有从 s 到达 t 的不同路径，找出最短的。但是回溯算法效太低。指数级。Dijkstra 算法在此基础之上，利用动态规划的思想，对回溯搜索进行了剪枝，，对回溯搜索进行了剪枝，继续往外扩展搜索。动态规划相较于回溯搜索，只是换了一个实现思路，但它实际上也考察到了所有从起点到终点的路线，才能得到最优解。

Dijkstra 优先最近的点，层层外扩，甚至到能那个点在终点的反方向；而A* 算法是通过顶点到起点的距离，和顶点到终点的距离之和小的优先考察（还可以放优先级队列）。 由于顶点到终点的确切距离位置，我们近似评估计算，即用曼哈顿距离（即两点间横纵坐标差之和），之所以用它是因为欧几里得距离计算平方根开销大。

//曼哈顿距离计算
int hManhattan(Vertex v1, Vertex v2) { // Vertex 表示顶点，后面有定义
  return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);
}

A* 算法是一旦遍历到终点就结束。Dijkstra 还是要考察所有的点和线路。前者显然高效很多。 A* 算法属于一种启发式搜索算法 启发式搜索算法利用估价函数，避免“跑偏”，贪心地朝着最有可能到达终点的方向前进。贪心地朝着最有可能到达终点的方向前进。平衡路线质量和执行效率，实际应用更为广泛。

如何在海量数据中快速查找某个数据？

建索引 如何节省存储空间、如何提高数据增删改查的执行效率

数据是格式化数据还是非格式化数据？ 数据是静态数据还是动态数据？ 索引存储在内存还是硬盘？ 单值查找还是区间查找？ 单关键词查找还是多关键词组合查找？ 不管是存储在内存中还是磁盘中，索引对存储空间的消耗不能过大。 在考虑索引查询效率的同时，我们还要考虑索引的维护成本。 构建索引常用的数据结构有哪些？

  • 散列表、红黑树、跳表、B+ 树，位图、布隆过滤器，trie树
  • 有序数组可以用来对静态数据构建索引也不错（数据很少变动的）。
  • B+ 树比起红黑树来说，更加适合构建存储在磁盘中的索引。
  • 跳表也支持快速添加、删除、查找数据。

更新时间: