大数据,机器学习基础

《大数据,机器学习基础》由会员分享，可在线阅读，更多相关《大数据,机器学习基础（24页珍藏版）》请在金锄头文库上搜索。

1、正则表达式d 可以匹配一个数字，w 可以匹配一个字母或数字 s 表示一个或多个空格. 匹配任意单字符 ? 表示 0 个或 1 个字符 * 表示任意个字符（包括 0 个） + 表示至少一个字符 n,m表示 n-m 个字符 这几个都是可以加在具体匹配内容的后面的如d3s+w3,8 表示 3 个数字 至少有一个空格 3-8 个任意字母或数字a-zA-Z_0-9a-zA-Z_* 由字母或下划 线开头，后接任意个由一个数字、字母或者下划线组成的字符串（数量不定）(P|p)ython 可以匹配 Python或者python表示行的开 头 $表示行的结束 py$就是这一行中只能有 py 两个字母Python

2、 的一般匹配写法是：if re.match(rw3-d2$, test) re 要提前 importMatch 之后看 结 果是 group = re.match()里面写法一致，group(0)就看内容A or 1(强行变成 =或的奇数)(A or 1)-1(强行变成=或101101,k=3) | x or (1 shl (k-1)把右数第 k 位变成 0 | (101101-101001,k=3) | x and not (1 shl (k-1)去掉右起第一个 1 的左边 | (100101000-1000) | x and (x xor (x-1)int abs(int n) retur

3、n (n (n 31) - (n 31); /* n31 取得 n 的符号，若 n 为正数，n31 等于 0，若 n 为负数，n31 等于-1 若 n 为正数 n0=0,数不变，若 n 为负数有 n-1 需要计算 n 和-1 的补码，然后进行异或运算，结果 n 变号并且为 n 的绝对值减 1，再减去 -1 就是绝对值 */ int max(int a,int b) 取两数最大 值return b /*如果 a=b,(a-b)31 为 0，否则为-1*/ int num = 0; while(n) n 把一个整数减去 1，再和原整数做与运算，会把该整数最右边一个 1 变成 0 。 那么一个整数的

4、二进制表示中有多少个 1，就可以 进行多少次这样的操作。用一条语句判断一个整数是不是 2 的整数次方：!（x & (x - 1)）每个阶段只有一个状态-递推；每个阶段的最优状态都是由上一个阶段的最优状态得到的-贪心；每个阶段的最优状态是由之前所有阶段的状态的组合得到的-搜索；每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的-动态规划。我所了解的卡特兰数有关的问题，大都 满足这样一个描述：有一个大 问题 A，规模为 n，要解决这个问题，可以用分治的思想，首先固定其中某一个元素，将剩下的 n-1 个元素拆分成两个小问题，这两个小问题的规 模分别是(0,n-

5、1) (1,n-2) (2,n-3) . (n-1,0)举几个例子：1. 二叉树计数，n 个结点的二叉树，首先固定根节点，将剩下的 n-1 个结点拆分给左右子树 2. 三角形划分问题，凸 (n+2)边形可以划分为 n 个三角形，首先固定一条边（即一个三角形），这个三角形将这个 (n+2)边形拆分成两个更小的多边形。3.在 n*n 的格子中，只在下三角行走，每次横或竖走一格，有多少中走法？4.用 n 个长方形填充一个高度为 n 的阶梯状图形的方法个数通项公式好像这个公式只关注项数 n 因为这样的通项公式也是数据库主键选择方案数据库主键的作用是唯一标识一条记录，所以在同一 张表中，任意一条记录的主

6、键都是唯一的。主键的有个作用是让其他表的外 键引用自己，从而 实现 关系结构。一旦某个表的主键发生了变化，就会导致所有引用了 该表的数据必须全部修改外 键。所以 实践中数据库主键几乎不可更改。主键必须使用单独的，完全没有业务含义的字段，也就是主键本身除了唯一标识和不可修改这两个责任外，主 键没有任何业务含义。主 键建 议使用字符串。因为主键的本质是保证唯一记录，并不要求主 键是连续的。 实际上不连续的更好，这样既避免了运营数据泄露，也给黑客预测 ID 制造了障碍，具有更高的安全性。一般方案是自定义一个算法，时间戳放高位，序列号放低位，还可以保留机器位，然后用 base32 编码，可以把长度控制

7、在 20 个字符内。SIMHASH分为两个部分，首先是编码压缩 部分， 这里解决了普通哈希会把相近内容哈希 为特别不像的哈希值的问题。首先对每一句 话做分词， 给每个分出来的词 加权重（这个权重没细说估计是TFIDF 的权重），然后 给每个 词做普通哈希，看 结果的 2 进 制（通常会统一成 64bit 的二进制）把二进制中所有的 0 改成-1 和 权值相乘，就成了一个 33-3-3333 或者 9-9-9-999 这样的数列。将每个文章（或者句子，取决于你要搜索的内容）的 64 位内容相加（不要 进位）结果就是这个文章（或者句子的 simhash 值 ）通常在比较给定文章（或者句子）与数据库

8、中的内容重复性大小的时候，认为 64 位 simhash的结果中有 3 位以内相同，就是由高相似性。比较的过程就是亦或一下两个文章看还剩多少个 1（亦或之前把 simhash 结果，大于 0 的位写 1，小于 0 的位写 0）为了降低比较的过程将数据库中的表复制 4 份，每一份是顺次把 16 位交换到最前方作为hash 表的 key，因 为 3 位以内相同才会考虑，所以根据抽屉原理符合条件的相似文章一定有至少四份之一是完全相同的，然后把每张表剩余的部分中再按照 这种方法选出四份之一作为 key 也就是说一共会产生 16 张表，比较重复性过程可以减小到原来的（1-1/4-3/16）AVL 树可以

9、说是完全平衡的平衡二叉树，因为它的硬性规定就是左右子树高度差不超过 1；而红黑树，更准确地说，它应该是 几于平衡 的平衡二叉树，在最坏情况下，红黑相间的路径长度是全黑路径长度的 2 倍。B/B+树 : 用在磁盘文件组织 数据索引和数据库索引。Trie 树 (字典树): 用在统计和排序大量字符串，前 缀匹配，后缀匹配总之就是字符串匹配。AVL 树删除节点不一定需要回溯到根节点插入更新时：如当前节点的高度没有改变，则上面所有父节 点的高度和平衡也不会改变。删除更新时：如当前节点的高度没有改变且平衡值在 -1, 1 区间，则所有父节点的高度和平衡都不会改变。根据这两个推论，AVL 的插入和删除大部分

10、时候只需要向上回溯一两个节点即可，范围十分紧凑。红黑树中的 insert_rebalance 操作也可能会有 O(logn) 量级的回溯，证明如下：当程序进入 insert_rebalance()的 while (x != root() & x-parent-color = red)后，它只会有如下 6 种运行方式：1. Case 1；2. Case 1 - Case 1 - Case 1 .；3. Case 1 - . - Case 2 - Case 3；4. Case 1 - . - Case 3；5. Case 2 - Case 3；6. Case 3；红黑树中的 erase_rebal

11、ance 只有如下平衡方式当程序进入 while (x != root() & (x = nullptr | x-color = black)后，它只会有如下 6 种运行方式：1. Case 1 - Case 2；2. Case 1 - Case 3 - Case 4；3. Case 1 - Case 4;4. Case 2；5. Case 3 - Case 4；6. Case 4;经过如上分析，我们可以对 insert_rebalance()和 erase_rebalance()些微小的优化：B 树整理B 树不需要像其他自平衡搜索树一样频繁地重新平衡，但是由于节点并不是完全满的，所以可能会浪

12、费一些空间B 树有个基础属性，m 阶，是表示一个节点最多能有 m 个子 节点（当然也就意味着一个节点内最多能有 m-1 个 key），最少要求有 ceil(m-1)/2)个 key 有时会把这个 ceil(m-1)/2)称为这个 B 树的度那么考虑到根节点一般只有一个 key，一棵 m 阶 B 树的在有 n 个节点的时候树高范围在logt1n,log2t1n内 更准确的 说法是：2(12 )1(+12 )11(+1)/2)+1根节点最少可以只有一个元素，因为插入节点的策略在一直没有平衡 时会一直上溯到根节点并创立一个新节点，这个新 节点最少就是一个元素。插入策略搜索并选择插入的节点：1.如果节

13、点内元素小于最大的允许值-1（m 阶-1）直接插入2.否则先插入元素，再将节点按大小均匀的分成两个部分，每部分(m-2)/2 ，其中一 侧的元素使用老节点储存，另一侧新建一个 节点并储存剩余元素。并将正中间的元素放入父节点，然后检查父节点的元素数量看是否超过最大允许值，如果超过就继续向上分裂，直到根 节点删除策略有两种主流的删除策略，一是先 删除内容然后重新平衡 B 树，另一种是在删除（访问节点）前就先重构树的结构以使其符合无论接下来要删除哪个节点中的内容都不会引起 B 树不符合要求的情况（就是需要重构的情况）这里只说第一种方法首先删除元素，如果元素就在叶子 节点上，那么直接 删除这 个元素。

14、如果元素在内部节点上，就向下找到这个元素的后继元素或者前驱元素，把后 继或者前 驱元素赋值给现在的待删除元素并删除这个后继或者前驱元素以上两种方案最后都统一在删除一个叶子节点的元素上，如果叶子节点删除了元素以后还能保证符合每个节点最小元素的要求，那么 删除操作结束，如果不符合，就要进行平衡步骤删除平衡方法核心方法是旋转与合并节点， 这一操作可能会从叶子节点一路上溯到根 节点因为只是节点内元素数量不够，所以不在意从左 侧或者右 侧兄弟节点“获得”元素仅讨论左侧节点，如果检测左 侧兄弟节点的元素数量多于最小的要求 值（等于的话，减了一个元素就不符合要求了）旋转左侧兄弟节点的最后一个元素与父节点中“

15、夹在两个节点中间那个 key”，树就平衡了如果左右侧节点恰好都仅仅只有符合 B 树要求的最低节点数量，那么就随便（这里取左侧兄弟节点）与现有节点合并，同时 将父节点中用于分割本节点和左 侧兄弟节点的 key 拉下来放入这个新融合的节点中，再检测 父节点的数量是否符合要求，如果不符合继续进行平衡操作。如果一直上溯到根节点，根节 点很可能被拉入下一层的节 点中。如果原始的根 节点只有一个元素，下拉后根节点为空，于是放弃这个根节点，把 root 的指针指向下一层的新根节点元素初始化如果对于一列排序后的数，构造使之成为新 B 树，注意先将这列数字做分割， （除最后一组外）每一组数的个数应等于 m（m 阶 B 树），最后一组元素个数最大不超过 m-1，最小不小于(m-1)/2，（如果最后一组元素数量太小，就将倒数第二组设为（m-1）/2+1）。然后除最后一组以外，所有组都将最后一个元素提升一层，形成父 节点，再 检测一下父 节点如果超过最大允许的节点内元素数量，就继续对元素进 行这种操作。如果此 节点小于 m-1，那么此 节点就设为 root 节点。B+树：与 B 树的区别：在非叶子节点中不 储存信息，在叶子 节点间有个一从头链接起的指针，因为非叶子节点中不储存信息所以非叶子节点中 key 和子节点一样多优势：