解决 WordPress 中的摘要字数问题

WordPress 是一个比较完善的博客系统, 也是我用来淘汰 Emlog 的方案, 但是最近发现有个问题, 即对中文的文字摘要做的不好, 默认是 55 个字符, 但实际上往往会把整片文章进行输出. 通过搜索引擎可以查阅到以下几个解决方案: 1. WordPress 修改摘要擷取字數 2. WordPress 技巧:正确获取文章摘要 3. WordPress 中文摘要插件 4. 教程:WordPress完美解决中文摘要不准确问题 从这里面可以了解到, 问题的核心在于 WordPress 的截取算法是默认通过空格进行计算的. 也就是说对于东亚文字而言, 没有空格的长篇大论都是认为是一个字. 所以, 我们需要通过部分的代码修改进行改正. 但是, 考虑到部分文档的历史久远, 以及严谨的态度, 我还是主要从代码出发, 最终定位到代码的位置为 wordpress/wp-includes/formatting.php line:3699 版本号为 5.2.4 也就是目前最新的版本: function wp_trim_excerpt( $text = ”, $post = null ) { $raw_excerpt = $text; if ( ” == $text ) { $post = get_post( $post ); $text = get_the_content( ”, false, $post ); $text = strip_shortcodes( $text ); $text = excerpt_remove_blocks( $text ); $text = apply_filters( ‘the_content’, $text ); $text = str_replace( ‘]]>’, ‘]]>’, $text ); $excerpt_length = apply_filters( ‘excerpt_length’, 55 ); $excerpt_more = apply_filters( ‘excerpt_more’, ‘ ‘ . ‘[…]’ ); $text = wp_trim_words( $text, $excerpt_length, $excerpt_more ); } return apply_filters( ‘wp_trim_excerpt’, $text, $raw_excerpt ); } 可以看到, 这段代码的主要用途就是截取摘要, 通常, 很多的教程都是在这里进行替换, 将 wp_trim_words 这句改成 substr 或者截取行数之类的, 但实际上这一步是多余的操作. 我们直接看 wp_trim_words 函数: function wp_trim_words( $text, $num_words = 55, $more = null ) { if ( null === $more ) { $more = __( ‘…’ ); } $original_text = $text; $text = wp_strip_all_tags( $text ); /* * translators: If your word count is based on single characters (e.g. East Asian characters), * enter ‘characters_excluding_spaces’ or ‘characters_including_spaces’. Otherwise, enter ‘words’. * Do not translate into…

巨硬实习之旅与近期总结

在巨硬已经呆了 15 个月, 已然创造了团队中实习期最长的记录。本来也没想呆这么久,只是没想到因为离家近, 价格也还好,外加学校也没什么事,就直接呆着了。没想到现在,论文定稿事情这么多,每周来回合肥苏州跑也不现实,导师的邮件回复速度真的是慢的令人发指,只好想着以后回实验室,盯着导师干活。 实习期间还是比较舒服的,之前在类似于国企的校企合作单位实习过,在互联网单位实习过,在台资企业实习过,最后的最后,像人一样工作的还是欧美外企啊。 在巨硬的实习期其实可以分为两个阶段,一个是转正面试前,一个是转正面试后。转正面试前,众所周知,因为转正的压力,干起活来特别卖力,所以这导致的一个结果就是,没啥事干。。。因为任务都是按照 Sprint 来排的,也就是每两周安排一次计划,当计划中的任务完成,那就只能从 backlog 中找点活干,backlog 里面呢,又都是一些无关紧要的低优先级任务(高优先级也没办法在 Sprint 碎片时间完成),所以我也学会了如何正确的工(hua)作(shui)。 本来硕士阶段和本科阶段着重点在于数据库相关的研发,但是众所周知,巨硬的特点就是,来了之后随机分岗。。所以我就被莫名其妙的被一三面面试官捞过去做 ML 相关的产品= =。(后来才知道,在楼上也有做数据库存储底层相关的组)。 实习期间,主要的任务就是处理数据和一个在线计算引擎。不得不说巨硬在存储上面是厉害,实习生项目是一个离线数据处理库,也就是尝试在做数据处理时,做一个中间层,对数据进行规范化梳理,也就是常说的 OLAP 操作。一开始觉得处理 PB 级的数据,哇好兴奋啊,到最后,哦又要等几个小时才能出结果啊。 关于在线计算引擎呢,这个我觉得从架构设计上就已经到了比较先进的水平。总共使用到的服务器在 40K 左右,每天处理的请求也是巨大的数量级。。关于如何处理大规模请求,网上有各种解决方案,巨硬内部的解决方案其实很奇葩,因为 Exchange 服务是从上个世纪 90 年代就开始的,所以受到时代的局限,很多的解决方法在现在看来思想有点落后,但是,很多的解决方法又很超前,因为当时的巨硬没有开源需求,导致很多的技术并没有外传。NoSQL的实践,列数据库实践都很超前。总的来说,我还是觉得巨硬少一个 Steve Jobs 般的营销鬼才,因为内部都是工程师说了算,导致很多的需求,都很工程师范(管用户怎么看,往上堆,这个很牛逼,往上堆)。 关于转正面试,貌似很多人都会觉得这个很难很慌,然而其实真的很简单,只要把给的题做出来,换着法子做出来,用各种奇葩技巧做出来然后一次过,就好了。想到当年在中科大复试,和老师交谈甚是开心,最后在专业面试中直接开始讨论苏州地区的房价对昆山地区的影响。差不多巨硬也是这样,记得面试最后问了下 AA 给我的评价,他也反常的直接给了答案,而不是非常官方的回答(不直接回答结果,编借口说等综合考虑)。 面试后的实习期,不出意外的,我从前端组换到了现在的重后端的部门。我的前端是真的烂,传说中的 Google(Bing) Coder,加上内部又是用 TypeScript,更是很难受。不得不说,内部的 infra 做的是好,哪怕不会写,照葫芦画瓢就行,写的不对的编译会告你怎么改。大不了最后 code review 拉回来重新写。现在的这个组就是在那个在线计算引擎上开发。如果你有幸购买了 Office 的高端版本,你可能就会看到我的代码。这里面也有个好玩的事情,我之前开发了个 feature,结果这个被美国的大老板喜欢上了,隔三差五提需求改,结果就是本来 1 个月就能上线到全球用户的 feature 脱了三个月。。。另一个项目就是 cache 相关的,要把线上所有的 cache 都进行替换到统一的 cache 缓存中,还是挺有挑战的。以前在蘑菇街的时候,也是做 cache,现在在巨硬还是做 cache,也算是一种传承? 到此,基本上就是实习期间的重大项目了。在实习的后期,因为学校开始了论文开题和初稿、定稿的琐事,也算是满负荷工作下抽空进行各种文案的编写,累啊。 近期总结 其实最近比较大的事情就是开源上的事情了,应该目前最大的事就是发掉 v3.0.0 的 hexo-blog-encrypt,当时启动这个项目的原因也是挺好玩的,有同学说 hexo 纯静态做不了加密,我查了下确实没有,然后他斩钉截铁说肯定不行。emmm,那我就只好做一个给他看看。没想到现在也广泛使用了。真的没想到。(vim 的那一堆插件,什么时候有人用啊)。确实感谢了一起付出的人,尤其是有一个 co-ownner 吧。羡慕现在的年轻人,大学期间确实是最轻松的时候了。 接下来也就是希望自己论文定稿顺利,外加顺利毕业吧。

微软实习面试经历

没想到,半年的学习已经结束了。和导师谈妥之后,研二就可以开始实习了,然后就开始了自己的实习招聘生涯。其实,因为目标比较明确,大部分的公司也并不是特别想去。所以就盯上了一家叫做巨硬的外企。然后就开始准备了。 但是主要好玩的地方不是面试的准备,而是拿 offer 的一段插曲。(巨硬的面试挺好过的,只要所有的算法题,都能很快的想到解决办法(不是最优解都可以),然后能够 bug free 的完成编写部分,都能有个很好的结果。) 当时,4.23 面试结束,在 4.27 收到 congratulations 邮件,被告知 offer 已经确认。然后就是精彩的部分了。邮件中说,具体的 offer 信息会在 few days(原话) 发送。所以,就是接下来的一周时间。但是,直到周三,我都没有收到 offer。因为感觉自己的面试过程非常的顺利。所以很是奇怪。发邮件询问 HR ,被告知,offer 还在发,说周四和周五一定会有。于是又开始了等待。最后周五中午还是没有 offer。于是很是紧张,发邮件给 HR,结果她不在办公室,请假了一天。当时就慌了。然后打电话给另一个北京的 HR,让她查一下我当前的状态,结果被告知,offer 在 5.6 号下午两点已经发送,是最早的几批。但是,我没有收到。于是,一番操作下,终于发出来了。。。真的是一波三折。想想如果自己没有找到另一个北京的 HR 的联系方式,或者我的 HR 没有请假(她回了句继续等待),可能就变成了我默拒了。还好最后的结果不错。 以上就是一个小插曲。就这几个月而言,其实投的公司挺多的,但是大部分都是去刷了个满分的笔试,然后鸽了面试。主要是,不是很喜欢某些公司的背书式面试,或者临时抓一个面试官过来面试毫无准备的面试,这让我觉得没有得到应有的尊重。其实,作为一名工程师,最主要的是解决问题的能力,比如面对某一个场景,会设计出来一个怎样的解决方案,同时,在实现这个方案的过程中,你会如何表现,是 bug free 的一次 AC,还是打回重来,而不是 Spring 的事务有多少种写法,或者数据库的第三范式的内容。所以整个求职中都偏向于考察算法的外企(其实也就是巨硬一家)。近段时间,国内互联网的负面新闻太多了。让我产生了一种,究竟实在 make the world better, 还是 make the world worse。所以选择了一个更加偏向于基础技术的公司。 记得巨硬面试的时候,有个流程是参观办公室,当时有个 50 岁左右的美国老太太,听说我们是来面试实习生的,很热情的张开双臂欢迎,这样的一个氛围确实给我留下了很深的印象。而且他的宣讲也特别的别出新裁,其他的公司都在极度的渲染自己的发展有多么迅速,或者未来有多么光明,而巨硬是指很平淡的描述,在巨硬工作会是一个怎样的场景,如何更好的 work life balance。我觉得这就是企业文化上的一个差异。而引申出来的可能就是两个截然不同的工作氛围。至少,我是喜欢后者的。至于技术上的提升,我觉得更多的是周围同事的水平,或者说公司的眼界。 希望之后一切顺利。

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 号机器。 如果 key = 1025 那么,就会 key = key % 1024 从而映射到 256 上。 Zookeeper 如何进行一致性保证 为什么需要 Zookeeper,上文也说过了,就是保证 Proxy 能获取到最新且一致的集群信息。也就是一致性保证。 一致性保障,其实比较完善的解决方案也就是 Raft 和 Paxos 两个算法。这边 Zookeeper 则是使用的叫 Fastleader 的选举算法,在多实例的情况下,通过选举出来一个 master 进行决策,从而避免了多机同时处理导致的不一致。 Fastleader 算法: 先上一个算法流程图: 第一反应就是和,Raft 算法好像啊。 以上是 Raft 协议的一个状态转移图,可以看到,和 Zookeeper 的选举不同的是,他没有固定的 Observing 状态(一直默默参与数据同步,但是不参与投票)。而且,ZooKeeper 中,一旦 server 进入 leader 选举状态则该 follower 会关闭与 leader 之间的连接,从而旧 leader 无法发送复制数据的请求到新的 leader 上,从而避免了干扰。 具体可以看 图解zookeeper FastLeader选举算法。 至此,基本上说了第一个方案。 Twemproxy 方案 这个也是最早的一个集群管理方案了,更倾向于一个基本的 client 端的静态 sharding。而且他的介绍也很简单,就是提供一个轻量级的代理服务,主要是为了减少后端的连接数。。。所以不是很明白为什么很多人都会写博客说用它做集群会很麻烦。。他本来就不是为了复杂集群管理业务而设计的。。 Redis 官方方案 也是一个使用了一致性 Hash 算法的方案。不过他有意思的一点就是去中心化。主要的好处就是,加入 {A, B, C} 三台机器作为一个集群,那么,你连上任一一台机器,你的所有请求都会在 Redis 内部进行处理,而不会暴露在外面。不过坏处也是显而易见的。访问缓存,基本上都是大量的短连接。所以,这边做并不会减少这个问题的产生(Twemproxy)就是因为这个而产生的。 具体的算法实现: A, B, C 三个节点,采用哈希槽 (hash slot) 的方式来分配 16384 个 slot ,三个节点分别承担的 slot 区间是: 节点 A 覆盖 0-5460; 节点 B 覆盖 5461-10922; 节点 C 覆盖 10923-16383. 获取数据: 如果存入一个值,按照redis cluster哈希槽的算法: CRC16(‘key’) % 16384 = 6782。 那么就会把这个key 的存储分配到 B 上了。同样,当我连接 (A, B, C) 任何一个节点想获取 ‘key’ 这个key时,也会这样的算法,然后内部跳转到B节点上获取数据 新增一个主节点 D,Redis 会从各个机器的前段,拿出一部分给 D: 节点 A 覆盖 1365 – 5460 节点 B 覆盖 6827 – 10922 节点 C 覆盖 12288 – 16383 节点 D 覆盖…

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%/ 即可,后者则是比较麻烦。因为不太想修改 WordPress 的源码(不太清楚有多少地方需要修改)。想了一会,最后确定添加 NGINX 重写规则的方案(还好会一点 NGINX)。 添加注释中的代码即可。将 ?post=(\d+) 的请求全都重定向到 WP 识别的请求上。 server { listen 443; server_name www.mikecoder.cn mikecoder.cn; … index index.html index.htm index.php; location / { #===================================================== if ($args ~* post=(\d+)) { set $args ”; set $id $1; rewrite ^ https://mikecoder.cn/post/$id; } #===================================================== try_files $uri $uri/ /index.php?$query_string; index index.php; } location ~ \.php$ { fastcgi_split_path_info ^(.+\.php)(/.+)$; fastcgi_pass unix:/run/php/php7.0-fpm.sock; fastcgi_index index.php; fastcgi_param SCRIPT_FILENAME $document_root$fastcgi_script_name; include fastcgi_params; } } 至此,基本上所有的配置已经完成。现在的主要任务又变成了,如何快速的了解 WordPress 的代码结构。同时争取成为 WordPress 的开发者。 最后感慨下,Wordpress 确实是做的最完善的一个博客系统。 为什么不用 hexo 作为一个稍微会一点 php 的人,还是想自己能魔改整个系统的。 作为一个 hexo 的插件开发者,我也知道 hexo 用来写博客的局限性。不是很愿意被限制。 我正好买了 3 年的云主机,不用也是浪费啊。 大量的数据不太好使用静态博客迁移。 为什么不用 typecho 其实和 emlog 一样的问题。WP 能满足所有的功能,且大部分做的更加完善。所以没理由使用 EM 和 TY(追求简单除外)。 论坛活跃度不如 WP,想获得新的主题或者插件,都比较困难。 EM 和 TY 的活跃用户仅限于国内。接轨世界的话,WP 确实是最好的选择。 最后的最后,感谢 EMLOG 的开发者。

2018 的目标

这个时间定下这个目标似乎有些晚了,不过也算是对之前的目标的一个总结: 不过这段时间的训练下来,总的来说还算是比较满意的。 Codeforce 因为才打了两场,…, 目前稳定在了蓝名,6000 名,LeetCode 目前是 2500 名,HackerRank 目前是 4000 名。 接下来的目的就是将 CF 达到紫名,然后 LC 刷进 1000,HR 就打进 2000 吧。 过段时间找到合适的网络环境之后,可以尝试下 TC 了。 一直吐槽没有一个量化的评判标准对一个程序员来说,现在,我自己觉得这些还不错,于是就开始玩这个游戏。 从之前的计划来看,应该是现在至少已经达到了 CF 紫名,只是很遗憾。。因为比赛时间的问题,一直没有一个很好的状态。 所以现在只能达到的几个目标是: LeetCode: 787 / 39565 (Global Ranking) HackerRank: 3097 / 158209 (Global Ranking) HackerRank: 2 金, 2 银, 6 铜 以上都是竞技比赛的成绩。不是刷题的。 自我感觉还是达到了预期的。 其实,最喜欢的就是这种竞技编程把对方踩在脚下的快感。 相对于 Codeforces 来说,这两边的比赛强度其实小很多,但是 CF 的时间点太不舒服了。也是不得不服老的一点。之前大学,通宵一天或者 2-3 点睡,第二天继续干活。现在,打一场比赛,到 2 点第二天完全是废人一个。只能说挑着比赛打。很明显的感觉不好刷。 说完之前的目标的完成度。现在说一下今年的几个小目标。 首先还是算法训练的。 LeetCode 进 500 Hackerrank 进 2000 Week of Code 每次都能金牌 HackHour 每次都能保银 其余比赛争取都能保银抢金 Codeforces 每次十点半的场都能参加,争取 Rank 在 300 内. 然后就是个人维护的几个项目: hexo 的几个插件,目前都是在修 bug 阶段。加密插件应该会在后期修改下密码输错之后的 alert,以及交互上的改进 firefox 的 json 插件,应该会添加上多个不同类型数据的判断,进行进一步的解析,将渲染层进一步的解耦 vim 的几个插件,主要还是进行维护,同时对 issue 进行跟进 其余没有人用的,还是保持着造轮子的心态进行学习 至于工作,目前首选和备选还有保底已经有了一个比较明确的规划,这个无须在此太费口舌。 总之,新的一年,应该会更加的好玩。

Gruvbox 显示 Syntastic 语法报错信息

Vim 的 Gruvbox 配色方案现在取代了我使用了两年的 Solarized,因为他的分辨率更胜一筹。所以,我决定了后者开始了退役。但是,遇到一个问题,因为 Syntastic 语法检测的时候,他和我现在使用的代码自动格式化插件有冲突。 在格式化之后,他的错误前标(sign)会出现在错误的位置。所以,为了更方便的查找错误,我一般是开语法错误高亮的。就像如下的效果: 但是在使用了 Gruvbox 之后,会出现这样的情况: 这个就很诡异了。他并没有给出对应的语法错误高亮。然后我又更换了几个其他主题,比如 desert,tomorrow 等,发现这个只是在 Gruvbox 上才会出现,所以我去他的 github 上提了这么个 issue 但是,并么有及时的得到回复。 所以,只好自己动手丰衣足食,在比对了 solarized 和 gruvbox 的代码之后,终于发现了端夷。 原来在语法配色中,有 SyntasticError 和 SyntasticWarning 这两个,而在 gruvbox/color/gruvbox.vim 中,它是如下的描述: ” Syntastic: {{{ call s:HL(‘SyntasticError’, s:none, s:none, s:undercurl, s:red) call s:HL(‘SyntasticWarning’, s:none, s:none, s:undercurl, s:yellow) hi! link SyntasticErrorSign GruvboxRedSign hi! link SyntasticWarningSign GruvboxYellowSign ” }}} 所以,理所当然的,它并不能很好的显示出对应的语法错误。只需要修改成如下就好了: ” Syntastic: {{{ call s:HL(‘SyntasticError’, s:red, s:none, s:underline, s:red) call s:HL(‘SyntasticWarning’, s:red, s:none, s:underline, s:red) hi! link SyntasticErrorSign GruvboxRedSign hi! link SyntasticWarningSign GruvboxYellowSign ” }}} 对应的修改之后的效果如下: 感觉不错。

使用非均匀量化处理图像数据

这篇文章其实也算是 “信息编码论” 的一个课程作业的总结吧. 因为之前对图像的处理, 基本都是作为一个 lib-caller , 对其中的原理部分一知半解. 正好研究生有这么个选修课程, 于是就硬着头皮选修了. 然后其中的一个实验就是要求实现一个 jpeg 压缩算法. 然后比较每个人的压缩效率, 同时还要比较信噪比. 所以正好有这个机会可以来尝试下好玩的部分. 我们首先拿到的数据是是 raw 文件. 一个 262144(512×512) bytes 的 raw 文件. 通过样例代码跑出来. 是著名的 Lena 图: 说道 raw 文件, 其实也很好理解, 这是最原始的图像数据, 其实就是一个 512×512 的二维数组, 每个点的数据为 0~255 的灰度值(现在只是黑白图片). 然后我们的任务就是使用各种可能的量化手段来进行图像的压缩. 为什么需要量化, 因为相比较于后期的压缩算法而言(在此也就是 jpeg 算法, 后面有机会再写), 分布越少, 后期的压缩效率更高. 所以, 这边开始最前期处理. 首先就是比较 low 的均匀量化. 将 0-255 均匀地分成四个部分 (0-64, 64-128, 128-192, 192-255). 然后将对应的中点值分别写入到对应的位置. 然后再跑一遍 jpeg 压缩算法. 可以得到均匀量化的图像: 当然, 结果也非常好, 信噪比也有: 22.88 , 在没有使用量化手段的情况下, jpeg 压缩为 262kb -> 66kb, 使用均匀量化之后, 最后的结果是 33kb. 节省了 50% 的空间. 然后就是重头戏了. 那就是非均匀量化. 以上, 我们都只是采用了人为设定的中心点, 进行强行的划分. 所以必然的一个结果就是, 并不能很好地表现出点的分布特性. 而最好的表现点的分布特性的算法莫过于聚类. 然后聚类中, 最常用的便是 k-means 算法. 但是, 在信息论领域, 有一个类似的但是名字不同的算法, 那就是 Lloyd 算法. 对应的数学表达是; 其实就是 k-means … 所以这边使用了这个算法进行设计. 也是从四个开始. 设定初始的四个中心之后, 跑一遍代码, 最后得到这样的一个结果: 可以看到已经好了很多, 对应的信噪比是: 25.98 了. 之后,为了更好地提高信噪比, 就人为地多设定几个初始点. 当达到 8 个的时候: 此时的结果已经很棒了. 信噪比达到了 31.68. 但是, 对应的理论结果就是图像结果变大, 但是实际上, 它是最小的一个. 具体的原因, 之后会写一篇关于 jpeg 算法的文章分析. 此时, 基本就明白了自己的大概思路, 为了写这个课程作业. 只需要不断地改变 kmeans 的初始点位, 找到最优解即可. 但是人工写太过麻烦. 所以我们有了 Kmeans++ 算法. 用它可以确定最优的 k 值. 基本这样, 课程的作业也能完成了. 但是, 为了追求优秀, 就要从一维的结果推广到 N 维. 也就是在多维空间的聚类算法. 其中, 最常用的就是最近邻算法(NN). 通常情况, 我们有三种进行距离判断的函数: Minkowski Distance Euclidean Distance CityBlock Distance 这三种近邻算法分别可以拿到如下的几个中心: 当数据到了多维之后, 就到了乘积量化. 乘积量化正好是我课程论文最后的主要内容. 其实也是一个简单地算法. 主要的原理就是分治. 将多维空间拆成多个低维空间, 然后分别求出不同低维空间的中心点. 然后通过笛卡尔积的方式, 求出多维空间的中心点阵. 最后通过排除法选出最优解. 这个的话, 之后可能有机会会再写个文章纪念下. 最后附一个测试代码: /****************************************************************************** Copyright © 2017 TangDongxin Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files…

使用 C 尝试内存管理

在之前苦读『垃圾回收的算法与实现』,也想着什么时候能够自己手动实现一把。加上自己对 redis 也还是算熟悉,也是知道他的内存碎片问题的严重性。所以,就想着这两者结合看看能有什么好玩的地方。 首先就是,如何进行内存的管理。众所周知,C 的内存管理通常使用 malloc 和 free 两个操作进行,于是乎,如果我们需要进行申请堆区的内存空间,(以下的讨论通通以堆区申请内存空间为主,栈区分配的内存通通不考虑),往往就会直接的 malloc(sizeof(xx)),然后再在不需要的时候直接调用 free 进行。但是,操作系统在进行内存分配的时候,并不能保证多次 malloc 的物理空间地址连续,加上内存的换页,就会导致性能的低下,操作系统需要不停的进行换页操作。 而且,在 MacOS(10.13.1) 上,malloc 的策略是,如果有可用的连续空间,直接分配,如果没有逻辑连续的可用空间,则会不停的继续申请。如果超过了系统限制,即使空白部分的总和大于你需要的大小,但是依旧会分配失败。其他的内存分配函数还有 realloc 和 calloc,不过也都是换汤不换药。总的还是选用第一个可用的地址。 接下来就是看,多次的内存申请和使用伪内存管理之后的效率差距: #include <ctype.h> #include <errno.h> #include <float.h> #include <iso646.h> #include <limits.h> #include <locale.h> #include <math.h> #include <setjmp.h> #include <signal.h> #include <stdarg.h> #include <stddef.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #include <wchar.h> #include <wctype.h> #define TIMES 100 #define SIZE 10 void print(void *mem, int size) { int i; unsigned char *p = mem; for (i = 0; i < size; i++) { printf(“%d “, *(p + i)); } printf(“”); } void *m_brw(void *mem, unsigned long long len) { return mem + len; } void m_rtn(void *ptr, unsigned long long len) { memset(ptr, 0, len); } int main() { clock_t start,finish; double totaltime; start=clock(); int i; for (i = 0; i < TIMES; i++) { int *a = (int *)malloc(sizeof(int)); printf(“%x”, a); *a = i; free(a); } finish=clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC; printf(“%lf”, totaltime); void *block = malloc(SIZE); memset(block, 0, SIZE); start=clock(); for (int i = 0; i < TIMES; i++) { int *a = (int *)m_brw(block, sizeof(int)); *a = i; /* print(block, SIZE); */ m_rtn(a, sizeof(int)); /* print(block, SIZE); */ } finish=clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC; printf(“%lf”, totaltime); return 0; } 以上便是测试代码,使用 m_brw 和…