位图鹅厂有这样一道题，给四十亿个不重复无符号整数，无序，如何判断一个数是否在这四十亿个数中出现过 直接遍历的话，时间复杂度是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的值，就需要考虑他的组成部分 根据刚刚功能的描述，可以基本确定如下内容： 函数有三个部分构成 第一个是形参列表，并且需要绑定参...

AVL树之前我们讲了二叉搜索树的相关内容，但是也了解到二叉搜索树有其自身的缺陷，就是当插入的元素有序或者接近有序，退化成单支树的时候，他的时间复杂度就会退化成O(N)，因此我们需要对他进行优化，有两种，一种是AVL树，也就是平衡二叉树，另一种是红黑树，这里我们先介绍AVL树 概念在发现这个问题之后，两个俄罗斯数学家发明了解决这个问题的一种办法 当向二叉搜索树中插入节点之后，检查每个节点的左右子树高度只差绝对值不超过一，否则需要进行调整 这样就能降低树的高度，从而减少平均的搜索长度 一棵AVL树是空树或者有如下性质 左右子树都是AVL树 左右子树高度差（平衡因子）的绝对值不超过1 例如 节点12345678910111213141516template<class K, class V>struct AVLTreeNode { AVLTreeNode<K, V>* _left; // 左子树 AVLTreeNode<K, V>* _right; // 右子树 AVLTreeNode<K, V>* _parent; //...

构建对话式应用对话式应用的特点 交互性 使用自然语言，文本，声音来直接和应用互动，使用成本和学习成本低 智能化 能够通过对话式应用的载体较为全面的发挥出大语言模型的功能，例如逻辑、记忆、理解、生成 跨设备支持 对于不同种类的设备都能有很好的支持，例如手机、手表、网站、音响等，都能够落地展现出不同场景的支持能力 对话式应用的开发流程评估一个对话式应用的标准，一是要降低用户使用学习的门槛，二是要能够准确识别用户的输入和上下文语境，以此来生成高质量的结果 一般来说开发的过程有如下五个模块 基座模型选型 参数设计 系统提示词设计 示例设计 检索增强数据库设计 基座模型的选型我们使用飞桨大模型社区来进行应用构建，以我自己的项目为例 这里有五个基础的预制模型，可以查阅他们的区别和优势根据自己的需求选择使用，这里我选择LLaMA-13B 参数的调整除此之外有两个模型参数，一个是Temperature 我们需要根据自己的需求，温度越高，输出其他词的可能性也越高 第二个参数是TOP_P，他的意思就是采样和选择 这里我们就需要通过大量的实验来确定相应的参数选择了 除此之外还有一...