Cu1universe

hashtable前言:hashtable 实现一个关联容器, 其在插入, 删除等操作都可以做到 O(1) 实现 哈希表概念哈希方法 直接定址法：取关键字或关键字的某个线性函数值为散列地址。（这种散列函数叫做自身函数） 数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。 平方取中法：取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。 折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。 随机数法 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。 hashtable解决冲突的办法就是开链. 冲突处理哈希表的冲突处理 ...

POST 和 GET 的区别转自 前言无论是 POST 还是 GET 请求, 都是基于 HTTP 的, 而 HTTP 协议是 TCP/IP 协议族的应用层协议 请求方法 GET: 获取资源, 用来请求访问已被 URI (同意资源标识符, 和 URL 是包含和被包含关系) 识别的资源 POST: 用来传输实体的主体, GET 也可以实现, 但是一般不使用 **PUT: 传输文件, ** 但是鉴于 PUT 方法本身不带验证机制, 任何人都可以上传文件, 存在安全性问题, 因此网站一般都不使用该方法 HEAD: 获得报文首部, 和 GET 请求一样, 只是不返回报文主体部分. DELETE: 删除文件, 同样不带验证机制, 存在安全性问题 OPTIONS: 询问指定的请求 URI 支持哪些方法 CONNECT: 要求在与代理服务器通信时建立隧道, 实现隧道协议进行 TCP 通信 GET 和 POST 本质上都 TCP 连接, 并无差别 由于 **HTTP 的规定和浏览器/服务器的限制, ** 导致其在实际应用过程中会体现出一些区别 区别 GET 在浏览器回退时是无害的, 而 POST ...

C++ 编译器中的优化 原文 Optimizations in C++ Compilers 作者 Matt Godbolt 翻译 Fu Zhe’s Blog 在将上层容易写的代码转换为高效的由计算机去执行的机器码的过程中，编译器必不可少。但它们在其中完成的复杂工作却常常被人忽视。你也许会花许多时间来慎重考虑算法和解决错误，但可能没有足够的时间关注编译器能做什么。 本文介绍了一些编译器和代码生产方面的概念，之后着重介绍一些你的编译器为你所做的令人印象深刻的转换工作，以及我最喜欢的优化方式的一些实际例子。希望你能了解编译器可以做哪些优化，以及如何进一步探索该主题。最重要的是，你可能也会爱上看汇编输出，并开始对编译器的工程质量肃然起敬。 本文举的都是C/C++的例子，这是我最有经验的语言。但其中的许多优化方法也适用于其它编译语言。事实上，像LLVM这样的前端不可见的编译器工具包的出现意味着多数优化方法都会以相同方式作用在Rust/Swift/D语言等语言上。 关于我我一直着迷于编译器能做什么。我曾经花了10年去制作一款视频游戏，并力争在相同CPU周期数下得到比竞争对手更多的精灵（sp ...

出离作者：许嵩这几个月，走过了不少地方。 每到一处，采访我的媒体通常会有这么一问：你的音乐理想是什么？而当答案是“我从来没有理想”时，我迎接那些错愕的眼神。 年轻的时候，拥有一些世俗的念想（比如声名远播？）、一些物质上的期待（比如大房子好车子？）、一些精神上的憧憬（比如寻得佳偶？）、一些相对崇高的目标（比如造福子孙？！），似乎的确能让一些人更有动力的过活每一天。但如果，岁月在你脸上已然留下不少年轮——你坐船的动机仍然只是到达一座岛，别人把岛上的一切美妙和宝藏说给你听就可以让你划船划的更带劲儿——那我能对你说些什么呢？ 平日里花费极多的时间在音乐上，无论是作词，作曲，制作，还是今年开始的演出，为此我已经感到体力不支（特别是最近一个月）。但仍然乐此不疲，并且不断研究着提升体能的方法。但这绝对不代表我有什么理想。那真是一种侮辱。 你一定试过非常入戏的观看一部电影吧？是了，电影非常精彩，你感受主角的悲喜，在影院里为它落泪或鼓掌——甚至为它憋住尿。但一旦事情严重到你觉得快要尿出来了，你还是可以毫无负担的起身奔向厕所。只因你知道，戏毕竟是戏。戏的发展和结局，毕竟和自己无关。你很清楚，你是你，戏是戏 ...

前缀和前置问题在认识前缀和之前, 首先提出万恶的需求: 对于一个数组, 并给出 q 次询问, 每一次都询问这个数组在 [l, r] 范围内的和 我们最开始的思路是, 每一次询问, 都去遍历一遍 [l, r] 区间去进行求和, 得到如下代码. 1234int sum = 0;while (q--) for (int i = l; i <= r; i++) sum += arry[i]; Easy! 当我们以为问题解决的时候, 问题升级了, 希望你在 **1s 内求出答案, 并且 ${n * q}$ 的值处于 10^6^ ** , 再去使用上面的方法, 就会喜提 TLE , 这时我们认识到, 每一个询问都进行区间求和的时间复杂度是 $O(nq)$ 的, 纯粹的暴力在升级的问题中是不可行的. 思考优化我们进一步思考, 突然发现一个有趣的性质, 如果要去求出区间 [l, r] 内的和, 只需要使用 sum([1, R]) - sum([1, L - 1]) (Ⅰ)就可以轻松得到, 而不再需要去进行遍历, 最重要的是我们只需要对整个数组求一次和, 即利用 sum([1, x]) ...

HTTP1.0 / HTTP1.1大部分都摘自 小伙伴 Tang7O 本文将在以下几个方面来对于 HTTP1.0 和 HTTP1.1 响应状态码 缓存处理 链接方式 Host 头处理 带宽优化 响应状态码HTTP1.0 仅定义了 16 种状态码. HTTP1.1 中新加入了大量的状态码, 光是错误响应状态码就新增了 24 种. 比如说: 100 (Continue) : 在请求大资源前的预热请求. 206 (Partial Content) : 范围请求的标识码. 409 (Conflict) : 请求与当前资源的规定冲突. 410 (Gone) : 资源已被永久转移, 而且没有任何已知的转发地址. 缓存处理缓存技术通过避免用户与资源服务器频繁交互, 节约了大量的网络带宽, 降低了用户接受信息的延迟. HTTP 1.0HTTP 1.0 提供的缓存机制非常简单. 服务器端使用 Expires 标签来标志 (时间) 一个响应体, 在 Expire 标志时间内的请求, 都会获得该响应体缓存. 服务器端在初次返回给客户端的响应体种, 有一个 Last-Modified 标签, 该标签 ...

C++ 基础知识点C++ 中四种 cast 转换C++ 中四种类型转换是: static_cast, dynamic_cast, const_cast, reinterpret_cast const_cast 用于将 const 变量转为非 const 变量 static_cast 用于各种隐式转换, 比如非 const 转 const, void* 转指针等, static_cast 能用于多态向上转化, 如果向下转能成功但是不安全, 结果未知 dynamic_cast 用于动态类型转换. 只能用于含有虚函数的类, 用于层次间的向上和向下转化. 只能转指针或引用. 向下转化时, 如果时非法的对于指针返回 null, 对于引用抛异常. 其中: 向上转换: 指的是子类向基类的转换 向下转换: 指的是基类向子类的转换 它通过判断在执行到该语句的时候变量的运行时类型和要转换的类型是否相同来判断是否能够向下转换 reinterpret_cast 几乎什么都可以转, 比如将 int 转换为指针, 可能会出问题, 建议尽量不要使用此类转换 C 的强制转换表面上看起来功能强大什 ...

Strategy 策略模式要解决的问题:在软件按的构建过程中, 一些对象使用的方法可能多种多样, 经常会出现变动, 如果将这个方法都编码到对象方法中, 将会高频率的修改对象方法, 使其变得异常复杂, 同时也破坏了代码尽量不去变动的准则, 并且有时候支持不会去使用的一些方法也是一个性能负担 模式定义:定义一系列算法, 将它们一个个封装起来, 并且使它们可互相替(变化). 该模式使得算法可独立于使用它的客户程序(稳定)而变化(扩展, 子类化) 举例当要实现一个计算税务的需求时, 没有进行优化前的代码如下 12345678910111213141516171819202122232425262728293031enum TaxBase { CN_Tax, US_Tax, DE_Tax, FR_Tax //每一个国家的税务计算};class SalesOrder{ TaxBase tax;public: double CalculateTax(){ //... if (tax == CN ...

RB-tree前言红黑树是一颗非严格均衡的二叉树, 它的平衡性并没有 AVL 树那么好, 但是其在调整树结构时所需要的调整的次数是小于 AVL 的, 所以对于频繁的插入删除等操作上是由于 AVL 树. 如果没有了解过红黑树的话, 建议先去看一下 红黑树(一)之 原理和算法详细介绍 , 否则对于下面的内容理解起来将会较为困难 红黑树的特性:（1）每个节点或者是黑色，或者是红色。（2）根节点是黑色。（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]（4）如果一个节点是红色的，则它的子节点必须是黑色的。（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。 红黑节点的定义 1234// 红黑定义typedef bool __rb_tree_color_type;const __rb_tree_color_type __rb_tree_red = false; const __rb_tree_color_type __rb_tree_black = true; 下面将 RB-tree 分为如下几个部分进行分析 基本结构 ...

占位文章 请忽略