Exploring the world

last update:

概要 Permutation(排列) 和 Combination(组合) 是数学中的经典计数问题, 高中的数学中有一 小部分知识是关于计算排列数和组合数的, 在大学的后续学习中, 排列和组合更是在统计概 率应用颇多. 而在计算机科学领域, 我们更关心的是列出排列和组合. 本文是我在完成 hackerrank 上面的Project Euler #24 后, 以及之前在Leetcode刷题的时 候碰到的排列相关的问题, 决定写篇小文章来记述一下其中涉及到 nth permutation 和 next permutation 问题. 名词解释 在进行下一步行文之前, 个人认为有必要介绍一下何为排列的顺序. 排列的顺序跟元素本身 的大小无关(有些元素之间本身并不具有可比性), 而是跟元素在序列(或者数组)中的索引相 关. 具体举一个例子会更加清楚. 序列[1, 2, 3] 的全部排列依序为[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. 序列[3, 2, 1] 的全部排列依序为[3,2,1], [3,1,2], [2,3,1], [2,1,3], [1,3,2], [1,2,3]. 上面两个序列之间相同的便是索引的摆列顺序: [0,1,2], [0,2,1], [1,0,2], [1,2,0], [2,0,1], [2,1,0] 那么如果序列中有相同的元素该如何处理? 仍然跟索引相关, 但有相同的元素便会导致出现 相关的索引. 具体的一个例子如下: 序列[1, 2, 3, 1] 的全部排列依序为:[1,1,2,3], [1,1,3,2], [1,2,1,3], [1,2,3,1], [1,3,1,2], [1,3,2,1], [2,1,1,3], [2,1,3,1], [2,3,1,1], [3,1,1,2], [3,1,2,1], [3,2,1,1] 对应的索引排列顺序为: [0,0,1,2], [0,0,2,1], [0,1,0,2], [0,1,2,0], [0,2,0,1], [0,2,1,0], [1,0,0,3], [1,0,2,0], [1,2,0,0], [2,0,0,1], [2,0,1,0], [2,1,0,0] Cantor Expression 何为康托展开?

最近在学习Coursera上的Algorithms, Part I,其每个week除了正常的Programming Assignment外还有面试问题.由于面试问题没有提交评分要求,想来在blog这里分享解决方案应该是没有违反honor code的.故这篇blog将是Algorithms面试问题题解系列的第一篇.

Question 1

原题引用如下:

Social network connectivity. Given a social network containing N members and a log file containing M timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at which all members are connected (i.e., every member is a friend of a friend of a friend … of a friend). Assume that the log file is sorted by timestamp and that friendship is an equivalence relation. The running time of your algorithm should be MlogN or better and use extra space proportional to N.

lz4介绍 Google Code项目上的介绍文字. {% blockquote Yann Collet http://code.google.com/p/lz4/ lz4介绍 %} LZ4 is a very fast lossless compression algorithm, providing compression speed at 400 MB/s per core, scalable with multi-cores CPU. It also features an extremely fast decoder, with speed in multiple GB/s per core, typically reaching RAM speed limits on multi-core systems. {% endblockquote %} lz4是一个非常快速的无损压缩算法,单核压缩能达到400M/s,对多核cpu的性能扩展也很好.同时lz4的解压缩实现也是极速,单核能够达到GB/s的速度,对于多核的系统来说能够达到内存的极限. lz4各个语言的实现 lz4最初的实现是用c来实现的.但除了c之外,其他人也实现了包括下面语言的lz4压缩.更多的见google code项目的说明 Java : by Adrien Grand, at la4-java C++11 multi-threads : by Takayuki Matsuoka, at lz4mt Python : by Steeve Morin, at py-lz4 Ruby : by Komiya Atsushi, at lz4-ryby 基本上主流语言都有对lz4压缩算法的实现,这个对于后续的应用开发带来了很大的便利.

背景 大约一个月前,我们的开发向我们提出他们一直在用的mongodb集群插入速度极其缓慢,希望我们能够登录到机器查看一下机器的状态信息. 我上去mongodb集群(这个原先不是我维护的)一看,发现他们创建的索引过多,索引的大小基本把整个集群所拥有的内存占完了.当然,同时 集群机器的负载,磁盘io一切正常.对于这样的现象,我首先要求他们将多余的索引删除,比如说是用于专门删除数据的ttl索引.对于这类索引 在数据量比较大的情况下,其实占用的内存量还是比较大的.但删除部分索引只能解放一部分索引,在综合考虑业务逻辑后,我向他们提出按时间对数据库进行分库. 为什么不进行分表呢?主要有以下几个原因 mongodb删除collection并不会释放硬盘空间,mongodb认为数据库申请硬盘空间是个比较费时的操作. mongodb的写锁是数据库级别的,也即是对某个collection的写操作会block掉对其他collection的操作,这个是不太能容忍的事情. 我们的拆分的依据是时间,这样分库的话,对删除数据非常有好处,直接将超过一定时间的数据库drop掉就ok了. 补充: 伴随着上述插入缓慢的一个现象是mongod和一个shard机器上有非常大的网络流速,这个其实是后续根源问题的一个表象,但当时 太年轻,没能据此抓住问题的核心. 第一个问题 确定好了分库的方案后,数据的导出和导入的工作是交由我来完成.由于接手的另一个mongodb集群的经验:在使用hash字段做shard键的时候,balancer 还是不能跑匀新增数据的不平衡.上面的经验让我做出了关闭balancer的决定.这直接导致了 导入速度的缓慢,要导入数据的集群没有使用hash字段来做分区键,新建立的数据库默认只在primary上,导入数据的时候所有写只在一个磁盘上 由于balancer关闭,数据保持不动,也即本来应该是均匀分散到各个shard的数据只呆在了一个shard上,这个完全违背了做sharding集群的初衷 解决 最初的解决方案,便是将balancer打开,慢慢等待balancer将数据均匀地分散到各个shard上,但由于mongodb本身对balancer做了限制,每次只能移动 一个chunk,加之数据量比较大,有较多的chunk,在默默等待一天无太大进展后,直接采取了重导数据的方案.具体步骤如下: 停掉balancer 设置shard collection的分区键 根据分区键的范围,将默认的一个chunk比较均匀地划分和移动到各个shard上. 开始导数据 重新开启balancer,等待之前导入的可能不平衡的数据均衡. 其实这个方案10gen官方在faq已经有提到过,可惜只是匆匆扫过的表示强调的不够.具体见http://docs.mongodb.org/manual/faq/sharding/###can-i-change-the-shard-key-after-sharding-a-collection 第二个问题 在完成数据库的分库后,我们预想中的速度提升并没有出现.在导入数据进行到一定时间后,导入数据的速度极度缓慢,具体的表现是mongos和某个shard上的mongod 有巨大的网络流量,同时该mongod的cpu占用达到了100%,但磁盘io基本为0,cpu是在计算而不是在等待io.在mongod上运行db.currentOp()命令发现有多条ns记录为空的 记录. 问题分析 网络问题的分析 有大量的网络流量,必然是数据在传输,但是我们的mongos传输出去的网络数据和接受回来的网络数据相差了一个数量级,而且这只在一个mongod和mongos发生.对于网络传输的问题, 我们的第一判断便是client在做文档更新的时候也把文档返回回来了.经过和开发沟通后,发现开发使用的是findAndModify,他在返回field上设置了None,认为这个是不返回数据.但实际上 JAVA的mongodb client api默认就是None,也即返回更新前的数据. 网络问题的解决 确定了findAndModify的问题后,我们的开发在仔细比较了一下findAndModify和update后,使用了update来代替findAndModify.这样解决了在更新的时候出现的网络流量暴涨的问题. 但实际上,这样的解决问题的方式,掩盖了为什么只有一个mongod和mongos会出现网络暴涨而其他mongod正常的问题.当时我们对于这个问题的解释是可能有太多的写操作同时打到了 那个出问题的shard上了,解决方法便是将前端导入程序的多线程数限制在一定shard总数的一定倍数上,这样既可以发挥多线程的高效,也不至于让后端mongod被插入请求打死. 实际上,这样的解决方案是错误的,因为问题的根源不是有太多的读写操作,具体的就引出了下文的问题. 第三个问题 修改了findAndModify和限制线程数后,我们觉得应该解决问题了,结果,第二个问题除了网络流量问题之外的问题又出现了.数据导入到一定时间后,导入速度缓慢的问题再一次出现,和 上面第二个问题表现一致!!其实这个还是第二个问题,我们还没解决. What the fuck! 插入缓慢问题分析 在经过几天毫无头绪,以头撞墙的绝望后,我们终于开始注意到刚开始导入数据是正常的,但导入数据到晚上的时间后就开始变得极度缓慢,直接从8k+records/s到200+records/s,同时ns 为空的记录里看到了多条指向同一个文档的记录.该文档的记录是某个特定用户的文档,我们抱着试一试的态度去看了一下那个用户的记录.砰!如瀑布般的好几百屏的数据奔腾而出!这对 我们简直是当头棒喝!原来如此,是该用户产生了巨量的数据导致了整个导入速度的缓慢. 数据存储说明 这里有必要提一下啊我们是如何在mongodb存储数据的.简单来说,我们有出现问题的数据是用户的登录数据.考虑到数据量的问题,我们将用户一个小时之内的数据进行了聚合,也就是将该小时 的所有登录数据都放到了数组里面.也即是将一个小时内的所有数据都放在了一个文档上面. 示例的数据是下面这个样子的. {k1 : v1, k2 : v2, k3 : v3, lt : [t1,t2,t3,t4,...], ip : [ip1, ip2, ip3, ip4, ...]} 分析继续 回到我们之前看到的那个特殊用户,对于一般用户而言,一个小时的登录次数是20-30次,而这个特殊用户在晚上7,8,9这几个小时的登录次数是每小时7w+,最高的一个小时的登录次数超过了10W次.

hhkb pro 2 入手

缘起

hhkb一直是心中的神器,执念甚深.去年在北京实习的时候,买了个hhkb lite的键盘,个人用下来感觉还是不错的.当然,身边多位基友提出:

  1. 键盘太难看
  2. 键盘布局不习惯
  3. 键盘手感不行

上述这些评价都无损我的hhkb的喜爱.个人认为既然薄膜的键盘都能够契合我的心意,想来hhkb pro的电容键盘应该是更加让人满意.于是, 在拿到全币卡的信用卡后就在日亚上入手了.

购买

最开始是想入手hhkb pro type s,想着反正就差小几百的钱,直接一步到位了.可惜,在日亚上看下来发现type s不是amazon官方销售的,而是 PFU出售的,这样发货速度就慢下去了.并且,下单后一段时间内,信用卡还没扣钱,觉得速度太慢,就改下单pro 2了.

购买方式

我的做法是直接在日亚上海淘,这个网上教程很多,我这边就不在赘述了,可以直接Google搜索一下,或者在什么值得买上搜一下海淘的教程. 另外不想自己怎么动手的且不怎么在乎钱的可以直接在萌购上直接购买,具体网址就自己google一下吧.萌购上的话,汇率偏高,手续费较高,运费 也偏贵,好在它帮你将所有的事情都处理好,你只需更在淘宝一样下个单就够了.

转运公司

最开始的选择是Tenso,可惜不仅要上传身份证还要提供证明现居地的文件,这个折腾起来太麻烦了.最终放弃了.Tenso之外的选择就是Jshopper了, 这个公司看起来物廉价美的样子.手续费低,且运费有5%的discount.当然网上有评价说,该公司在货物的称重上偏高.不过,就我这次键盘收到的情况 来看,该公司在货物的包装上花了功夫的,多余的包装导致的重量当然也是在运费范围内的.

转运速度

上张图吧,一图胜千言

起因 早就想将blog迁移到自己的vps上,但 之前的vps还是buyvm的屌丝机子,配置太低,而且不太稳定,一直是当ssh机子来用的,不太想跑blog 已经有几个小网站跑在vps上了,访问速度实在是不理想 我准备想迁移的时候,在buyvm的vps居然已经被墙了 于是由于上述种种原因,便将迁移工作搁置不动了。 7月份入职后,手里有了点闲钱,便准备入手个linode的vps,不过之前已经有好友在用linode的vps,个人觉得用linode就跑个 blog太浪费资源了。便和商量一起担负linode的vps费用。于是,机子备好,只剩代码跑起来了。 部署 客户端发布 octopress发布其实简单,其本身就自带了rsync同步部署的方式。在配置文件里写好你的vps帐号就可以完成配置了。具体可以参考这篇文章。 web server配置 上面那边参考文章在server端使用了nginx做为web server,这其实是个比较不错的选择,如果: 你的vps内存比较少,配置比较低。nginx占用的资源比较少 你自己独享vps或者别人没有使用其他web server的需要。 nginx的做为web server的基本功能是齐全的 但博主这个vps已经有apache的服务跑在上面了,于是就改用apache作为web server. 波折 机子自带的apache的版本是2.2.15,且博主想把documentRoot放在非Apache的默认路径下,结果一直报403 forbidden错误。具体解决方案可参照下面两个网址: stackoverflow 上的问答 noah上的文章 但上面noah上提出的解决方案有缺陷,apache只需要到documentRoot目录下所有的父目录的可执行权限就可以了。也就是说如果你的Documentroot在/path/to/www这个路径, 则/path, /path/to这两个路径需要提供给Apache可执行权限。