01 背包的二进制优化

也是在刷题的时候发现的,比如 hiho week 195。一眼看过去就是一个 0-1 背包问题,然后直接 DP 上了,当时觉得应该问题不大,结果最后只有 50%,一看数据,100% 的数据为 1E5 量,简单的 DP 的话复杂度为 O(MN),这样复杂度估计是 1E10,这样肯定会 TLE。 然后一看,他的单个商品的全权值很低,都在 [1, 10] 之间,这样的话,最多有 100 种组合,所以极端情况下,每个商品都会有 1000 个同类。这样就有了二进制优化的余地。简单的说就是,将多个重复的商品进行优化。比如 p(w, v) 的商品有 10 个,那么,我们可以将其简化为,一个 p(1w, 1v),一个 p(2w, 2v),一个 p(4w, 4v),最后剩下一个 p(3w, 3v)。 这样的话,就将数据量从 10 简化到了 4。于是乎,就可以将数据量减少一个数量级。所以,最后这题的代码: using namespace std; typedef pair<uint64_t, uint64_t> pii; typedef pair<pii, uint64_t> ppiii; typedef pair<pii,…

Redis 相关的复习

这段时间主要是扑在算法上了,这些工程领域的知识有点遗忘了。所以趁着这次复习,复习下之前做过得项目。同时,正好当时,Redis 官方还没有集群方案,所以才有了之前的 Cache 集群方案,现在正好也看看 Redis 官方的方案。 Codis 方案 一张 Codis 官方给出的架构图: 可以看到,它是采用了 proxy 的方式,和 Redis 官方给出的去中心化的思路不同,Proxy 是一种中心话的思路,将 Redis 仅仅作为存储引擎来使用。这一点其实比较符合组件化的原则,每一个组件只需要做一件事。同时,proxy 的方案,也非常利于简化代码的逻辑。 Zookeeper 用来维护整个集群的 metadata 信息。相比较于去中心化的思路,中心话带来的就是一致性问题。比较简单的,在多个 proxy 中,如何维护同一个正确的 redis 集群信息。所以这个使用了 Zookeeper 来进行维护。也算是做到了 HA。 至于 proxy 中的分区算法,依旧是采用的一致性 Hash 算法。这个也算是在这种扩展性上的一个比较通用的处理手段。 记得我们当时讨论过,是否直接采用这个方案进行部署。但是,当时的负责人始终坚持自研,但是最后的方案也还是参考的 Codis 进行,不得不说是一个很没有意思的事情。 一致性 Hash 其实就是将一个一维线性的地址空间做成环状,收尾相接。 同时部署在上面的机器,都会握有一个 index,比如 1024 中的 256,512,768,1024 这四台机器。 当一个 key = 268 值传入时,就会找第一个接近的值,这里就是 512 号机器。…

Emlog 迁移至 WordPress

作为一个 Emlog 4 年多的用户同时也是众多参与 Emlog 开发者中的一员,做出这个决定确实很难。不过 Emlog 的长期荒废,加上论坛里高质量的内容越来越少。这个也是势在必行。 最后一根稻草是:混乱的社区。于是乎,最后转向了 WordPress。 说道迁移,最麻烦的时数据的备份,之前也想过迁移,但是总是在最后一步卡住了,因为缺少一个合适的工具进行数据的导入导出。自己写的话,比较麻烦,因为对应的数据库表众多(其实就是懒)。 于是乎,这次我觉定自己玩一下。先是查到了这么一篇文章:emlog 5.3.1程序转入wordpress程序教程。得到了这么一个优秀的脚本 em2wp.php。 但是跑了一下,发现问题挺大的。因为这个版本的 php 是用 5 来写的,现在所有的云主机,基本都是 7 打底,所以就会有兼容性问题: WordPress 版本更新之后,对应的表结构发生了改变。 PHP7 以后不再支持 mysql_xxxx 函数。 代码并不会显示错误代码。 中文字符集的乱码问题。 于是自己修改了下,并且运行成功。代码 GIST – em2wp.php。 代码不会修改 emlog 原始表结构,所以放心的在线上执行,毕竟如果是迁移,Wordpress 的库内容是无足轻重的。并且,我相信各位都是可以成功看到 GIST 的。 不过总体而言,迁移非常的成功。剩下的 https,资源文件,域名,postId 保持一致,则都是体力活了。 本来以为一切都已经搞定了,可是,我去 google 搜了一下我的博客,发现他的 url 为 https://mikecoder.cn/post/{postId},然后看看其他人引用我博客的时候的 url 则是 https://mikecoder.cn/?post={postId}。 不管是哪一种,WP 都没有默认的支持,前者比较好办,直接在后台进行修改就好,修改默认的链接为 /post/%postId%/ 即可,后者则是比较麻烦。因为不太想修改…

二分查找和 Lucas 定理

因为这段时间都在打比赛中度过,有几个小的收获点这边可以留个纪念。 1. 二分查找的几个用法。 一般而言,二分查找都是用在不同数字的数量集中。这样的好处是如何快速的定位。但是,如果是排序的包含相同数字的数组,要求获得某一个数出现的次数时,就得用另一种二分查找的变种了。 假设是 [1, 1, 2, 3, 3] 这样的一个数组,要求获得 1 和 3 的个数时。普通的二分查找只能定位到其中的一个位置。之前我的做法是,向前向后搜索。但是,在极端情况下,比如一整个数组都是 1,此时,算法的复杂度退化为 O(N),然后就 TLE 了。 所以这边也正好是看到【剑指 offer 】里面有这么一题,就写一下。 int getFirstIdx(vector<int> &nums, int target) { if (nums.size() == 0) { return -1; } int left = 0, right = nums.size() – 1; do { int mid = left + (right – left)…