机器学习初步什么是机器学习我们人类学习的过程就像是在理解一个知识并且能够运用这种知识，而理解知识过程本身就是一种改善提高自我的过程。这里面最重要的其实就是从过往的，已有的数据中，提取知识，并且能够运用 机器学习的三个步骤在人类学习的过程中，例如学习将实物苹果和文字“苹果”做对应，我们通过观看苹果的图片或者实物，提取出共同的特征，例如都有类似红色的颜色，顶部和底部都有凹陷的窝，一般有梗，叶子是绿色的等等一系列特征，再将这些特征与苹果这两个文字联系起来，就完成了从实物到文字的这样一个映射（学习过程） 那么对于机器学习也是一样的，我们有特定输入，预期输出，处理函数 对于特定输入，其实就是苹果的图片或者实物，但是对于计算机而言，他是无法观看这些实物的影像的。因此我们考虑将这些影响转化为具有特征值的向量空间，例如使用灰度矩阵来表示图片 预期输出也就是我们最终学习到的“苹果”两个字，也就是学习之后的结果 而处理函数就是我们的大脑 每一个具体的输入称之为实例（instance），由特征向量（feature vector）构成，所有特征向量存在的空间称之为特征空间（feature space） ...

布隆过滤器我们在上一篇中主要说的是位图，是用于判断整形是否存在的一种应用，但是他不好的地方就是只能判断整形了，如果是字符串的话就难再应用了 在之前哈希表中，我们使用了一些哈希函数来将字符串转化成整形，再存入哈希表 这里我们是否可以使用同样的方法呢 其实我们讲，可以但是还不够，因为相似的字符串很容易就会产生哈希冲突，本质上来说还是因为字符串的数量太庞大，远远超出了整形能承受的范围，从而形成一种多对少的效果，产生了冲突 那么对于这样的冲突，也不能直接存字符串，因为使用位图本身就是为了节省空间的 这时候就有人想到了一个方法，既然一个关键字（哈希地址）容易产生冲突，那么我如果使用两种不同的哈希函数，每一个字符串对应两个哈希地址，只有当两个哈希地址都是1的时候，我们才认为该字符串是已经存在的 但是这种存在依旧是“不可靠”的，在数据量特别巨大的时候，可能是别的字符串，恰好占用了这两个地址，此时就会误判，但是判断不存在的时候就是可靠的了，因为只要有一个是0，就说明这个字符串并不存在 这也就是为什么我们称之为过滤器，简单说一种应用就是用户注册时不允许重复名称，当我们查询时，发现不存在，这时就不需...

位图鹅厂有这样一道题，给四十亿个不重复无符号整数，无序，如何判断一个数是否在这四十亿个数中出现过 直接遍历的话，时间复杂度是N的；排序加二分是NlogN的，哈希的话会好很多，是常数级的 但是需要考虑一个问题，就是说四十亿个值内存里能不能开出来，大概算一下需要16G左右的内存，因此直接开哈希表也是不现实的 实际上要解决在不在这个问题，不需要存下来这么多数据，只需要使用整数通过哈希函数计算出对应的位置，用0表示不在，用1表示在，这样就能节省大量空间 这里四十亿个数据只需要0.5G左右即可 那其实可以拓展来讲，在不在是两种状态，也可以使用两个bit位表示四种状态，以此类推，在后面我们会尝试实现 模拟实现在C++标准库里面也有bitset可以直接使用，而且功能也算是比较丰富的，我们主要模拟实现三个函数，一个是set置一，一个属reset置零，一个是test查询 我们用什么来承载这些个bit呢，考虑使用int，32位机器下，一个int是4个字节，刚好可以承载32个比特 如果我们想开N个bit的大小，那么至少需要N/32+1个int 这样我们就可以搭一个基本的框架了 1234567...

补档上一次我们在使用哈希函数时说，利用仿函数可以解决不知道哈希表内存的数据类型时对哈希函数也可以进行计算，但是当时只给了一个框架，一种是可以直接强制类型转换为整型的，另一种是字符串类型 对于字符串的哈希函数有很多研究，一种比较方便的做法是使用字符串的第一个字符的ASCII码值进行简单的数学运算，或者把所有的ASCII码值相加再运算，因为如果直接作为哈希地址会导致很多重复的冲突 12345678910template<>struct HashFunc<string> { size_t operator()(const string& key) { size_t hash = 0; for (auto e : key) { hash = hash * 31 + e; } return hash; }}; HashTable迭代器开放定址法比较简单，这里我们主要实现连定址法 和之前一样，我们封装需要增加迭代器、和他的基本操作，还有KeyOfT，然后再遇到什么问题我们详细说 首先...

unordered系列关联式容器之前我们讲到，STL提供了底层为红黑树的一系列关联式容器，可以在相当高的效率下进行查询 但是在树的节点非常多的时候，查询效率也不够理想，因此在C++11中又提供了unordered系列的容器，unordered_map、unordered_set、unordered_multimap、unordered_multiset 这四个容器的使用和原本的map和set基本完全相同，只是没有了排序的功能，也就是没有中序有序的特性，我们可以在文档中看到他的各种使用，这里就不过多赘述了 我们主要想了解他实现的底层原理和封装过程 底层结构unordered系列的关联式容器他不需要排序的功能，也就意味着他的底层并非红黑树 实际上他的底层使用了哈希结构 需要注意的是，哈希其实是一种思想，是将原先的数据通过某种方法处理过后，对应到另一种数据上的思想；哈希表是哈希的一种应用，是将数据通过处理后，对应到表的某个位置上 哈希的概念在过往我们学习顺序结构或树状结构进行查找时，是通过一次次的比较来查找，而效率则是取决于查找过程中元素的比较次数 那是否存在一种查找方法是可以不通过任...

封装的一些小问题封装要实现什么一般来说封装需要实现map和set的迭代器，包括普通迭代器和const迭代器，其次是++和–操作，还有判断是否相等的重载 除此之外我们需要实现map和set的特性，例如set的值不允许修改，map的key不允许修改 伏笔一set的构造参数只有一个，而map的构造参数有两个，我们怎么只用一个数据结构（红黑树）来封装两个容器呢 RBTree的模板参数前两个是K和T，K表示key关键字类型，T表示其中的数据类型 当用来构造map时刚刚好，一个用来存key，另一个用来存数据，这里我们考虑使用pair，分别存入const K和V，用来确保K不被修改 当用来构造set时，K和T是相同的，我们都传入K即可 伏笔二RBTree的模板参数里面有一个KeyOfT，这是一个仿函数，因为map的结构特殊性，是一个pair，所以我们需要用仿函数来自动调用对应的取key中的T的操作，类似于C语言的回调函数，根据数据的类型调用不同的函数 伏笔三在实现Insert函数时，返回值是一个pair，first是Node*，second是一个布尔值 这里的Node*一方面是需要返回给外部调...

红黑树概念和AVL树一样，红黑树也是一种二叉搜索树，是解决二叉搜索树不平衡的另一种方案，他在每个节点上增加一个存储位，用于表示节点的颜色，是Red或者Black 红黑树的核心思想是通过一些着色的条件限制，达到一种最长路径不超过最短路径的两倍的状态 所以说红黑树并不是严格平衡的树，而是一种近似平衡 例如 性质（条件限制）红黑树一共有五条性质，由此来保证最长路径不超过最短路径的两倍 每个节点都有颜色，不是黑色就是红色 根节点是黑色的 如果一共节点是红色，那么他的子节点一定是黑色（不会出现两个红色节点连接的情况） 对于每个节点，以这个节点到所有后代的任意路径上，均包含相同数目的黑色节点 每个叶子节点（空节点）是黑色的（为了满足第四条性质，某些情况下如果没有第五条第四条会失效） 节点的定义123456789101112131415161718192021222324// 颜色enum Color { RED, BLACK};template<class T>struct RBTreeNode { RBTreeNode<T>* _...

函数 我们想让用户可以定义自己的函数，而不仅仅是使用我们提供的内建函数 那我们要提供这样的功能就要首先就得提供一个内置函数，可以使用户通过这个函数创建自定义的函数 他使用起来有两个参数，第一个是形参列表，也就是要使用的参数，第二个参数是另一个列表，也就是函数的具体内容，运行函数时，我们调用对应函数进行处理即可 我们使用\来表示定义函数 例如 1\ {x y} {+ x y} 然后可以将其作为普通的S表达式使用，也就是计算的符号 1(\ {x y} {+ x y}) 10 20 如果我们想命名这个函数，只需要使用def给他起个名字，这样就能使用名字直接调用了 123def {add-together} (\ {x y} {+ x y})add-together 10 20 函数类型我们要将函数存储为一种MLval的值，就需要考虑他的组成部分 根据刚刚功能的描述，可以基本确定如下内容： 函数有三个部分构成 第一个是形参列表，并且需要绑定参...