飞

基本我一直用的是reiserfs，那大概是从有一次刚开始用linux不久时的突然断电开始的。那次没有正常关机以后，Linux系统就再也启动不了了。后来在LinuxSir.Org上面看到大家都说reiserfs能在断电以后自动修复，而且速度很快，我就开始了自己的reiserfs旅程。
自从以前看了王垠那篇著名的文章以后就认为linux的所有的文件系统(ext2,ext3,reiserfs,jfs,xfs等）都没有碎片，但是遇到了和windows一样的情况：刚装完系统时运行很快，而越用越慢。最近在Arch Linux的论坛上才看到有人说reiserfs有碎片，而且速度比较慢，于是让我开始怀疑我用了多年的reiserfs，于是也就去查找了一下这文面的文章。

Filesystems (ext3, reiser, xfs, jfs) comparison on Debian Etch是一篇最近才写的在Debian Etch上面对各种文件系统测试的报告，略去一些具体的数据，我把得出的结果放在这里，以备有同样需要的朋友参考：

• 要尽量最大化地使用分区的容量（也就是少浪费空间），请使用ReiserFS, JFS 或 XFS。
  
• 想快速地创建文件系统和快速地挂载分区，请使用 JFS 或 XFS
  
• 需要对大文件快速操作，请使用 JFS 或 XFS，若想最小化CPU使用量，JFS会更好。
  
• 对于大的目录树，使用EXT3或者XFS。有人建议对于大量小文件使用ReiserFS比较好好，不好对于由10KB到5MB之间的不同大小文件组成的目录树，使用XFS或ext3在现时中会更快一些。JFS虽然能最小化cpu占用率，不过在速度上还是有些慢。
  
• 列出目录中的内容和在某一特定的目录树下搜索，有两种情况。(1) 更快但是cpu使用率更高(ReiserFS,XFS)；(2)慢一些但是低cpu使用率(ext3,JFS)。XFS是一个很好的折中，它有比较快的速度，适度的cpu占使用率和可接受范围的页错误。
  

结论：ext3浪费过多的空间而且格式化比较慢；ReiserFS挂载时间长，而且对于日常操作会产生比较多的页错误；JFS是CPU占用率最低的。XFS应该是用来作家用和小型商用文件服务器综合起来看最合适的文件系统，因为：

• 它能最大化地使用分区。
  
• 它是创建，挂载和卸载最快的。
  
• 它是对于500MB以上大文件操作最快的。
  
• 它是对于中小文件操作第二快的
  
• 它在对于大的目录树的搜索的时间和cpu使用率间找到了一个比较好的平衡点。
  
• 它不是cpu使用率最使的但是占用的系统资源在比较老的机子上也是可以接受的。
  
  当然，对于日常应用来说鉴于XFS的速度和可伸缩性，它也是最佳的选择。

之前都是用去掉anti alias的字体来显示英文的，前几天看邮件的时候突然发现用AA的字体看这些比较长的东西眼睛会舒服得多，因此有个想法把字体的风格改成这种柔和的而不是以前那种尖锐的。经过了几天的修改和测试，已经有了一个比较不错的字体显示，总结一下经验：
这篇文章对linux下字体的设置有了一个比较全面的讲解，而且总结的比较好，不过对于LCD的屏幕，我想补充两点。

1.就是屏幕解析度的设置（dpi）。Windows默认的dpi(Dots per inch)是96，因此也有人喜欢设置成这个样子的，但是这不一定就是某个特定屏幕的解析度。因为每个液晶屏幕都有一个Native Resolution，也就是说在这个分辨率下最清晰，而它也有它固定的物理尺寸。举个例子，比如一个LCD显示器的Native Resolution是1024x768，而他的长度是286mm(1 inch = 25.4 mm)，它横向的dpi就是 1024*25.4/286=90 dpi，所以应该设置成90而不是96.而如果dpi设置的不对的话，字体可能显示的不是很清晰，尤其是gtk的程序。因此这是需要注意的。具体应该这样设置：先找一把尺子量一量自己屏幕的长和宽（我不是在开玩笑），比如是286mm 214mm，在xorg.conf文件里面加入一句：

 DisplaySize 286 214

，重启x以后x会自动计算dpi。然后计算一下正确的dpi是什么，假设是90，在/etc/fonts/local.conf里面添加一句

<match target="pattern">
  <edit name="dpi" mode="assign"><double>90</double></edit>
 </match>

就可以了。

2.sub-pixel亚像素微调。这里要说一点LCD显示器的原理。它的每一个像素其实是由三个亚像素（小一点的像素）组成的，一个红的，一个绿的，一个蓝的。它们一起够成了我们平时所看到的像素。因此如果以亚像素为单位，其实把我们的屏幕横向的分辨率扩大了三倍，因此在抗锯齿的时候可以做得更细致，而在多出一两个亚像素时我们的眼睛是分辨不出它们的颜色来的，因为它们还是按照rgb(或bgr)的顺序来排列的。所以使用亚像素微调会带来更好的显示效果。此时面临的一个问题就是，LCD屏幕制造的时候，不同种类屏幕rgb三种亚像素的排列顺序是不同的，也就是说，有的是rgb的顺序，有的是bgr的顺序，所以亚像素微调还要设置一下顺序。我们怎么才能知道自己屏幕是什么样的顺序呢？可以用这篇文章中的两幅图片来测试一下：




第一张图片是用rgb的顺序进行的亚像素微调，而第二张是bgr，如果你发现某一幅图片很清晰，线条比较平滑而另一张看上去非常糟，那么你的屏幕的rgb顺序就跟是清晰的那张图片一样。知道了这个以后，就只是简单的在~/.fonts.conf或者/etc/local.conf里面加上下面这一段（假设是rgb）就OK了：

<match target="font" >
  <edit mode="assign" name="rgba" >
   <const>rgb</const>
  </edit>
 </match>

本文参考了一下文章：
How Sub-Pixel Font Rendering Works
HOWTO Xorg and Fonts

2006-03-30 13:01:55 Accepted 0.008 Minimum C++ 103 - Stacking Boxes

这道题不是很难，是一个典型的动态规划。
首先，我们先要找到一个高效的算法来判断一个盒子是不是能放在另一个盒子里，这很简单，我们可以推出这样一个结论

如果一个盒子能放在另一个盒子里，当且仅当把这两个盒子的坐标排序后，第一个盒子的每一维都严格小于第二个盒子的每一维。

来证明一下。如果把这两个盒子的坐标排序后，第一个盒子

(a1,a2,...,an)，其中a1<a2<...<an

的每一维都严格小于第二个盒子

(b1,b2,...,bn)，其中b1<b2<..<bn

的每一维，那么跟据题意，第一个盒子可以放到第二个盒子里。反过来，如果第一个盒子可以放到第二个盒子里，跟据题意，则第一个盒子的坐标存在一种排列

(ak1,ak2,ak3,...,akn)

满足：

ak1<b1
ak2<b2
...
akn<bn

如果ak1<ak2<...<akn，则符合结论。如果存在一个aki>akj(其中i<j)，

因为akj<aki,aki<bi,所以akj<bi
因为aki<bi,bi<bj,所以aki<bj

可见将它们互换，同样满足条件。所以可以通过这种互换，来达到a1<b1,a2<b2,...,an<bn，所以结论成立。

这样以后问题就简单多了。可以先将每个盒子的坐标排成非降序，然后再把整个盒子序列按照如下规则排序
比较第一个坐标，如果想同再比较第二个坐标，如果还相同则比较第三个坐标，依此类推。
这样的依据是把所有可能被第i个盒子包含的盒子都放在第i个盒子的前面，这样才可以进行动态规划。
通过这样的处理以后剩下的就是”最长非降子序列“式的动规了。
时间复杂度O(kn^2)