Priority Queue 的基础操作:

• insert: 在Queue中加入一个带有对应优先级的item
• deleteMax: 移除优先级最高的item (此操作仅适用于maximum-oriented priority queue)
• deleteMin: 移除优先级最低的item (此操作仅适用于minimum-oriented priority queue)

三种Implementation:

1. 无序array (selection sort)
   
   
   • insert: O(1)
   • delete: O(n)
2. 有序array (insertion sort)
   
   
   • insert: O(n)
   • delete: O(1)
3. Heap (一种BST)
   
   
   • insert: O(log n)
   • delete: O(log n)

Heap的性质:

1. 从上到下, 从左到右, 必须在一层(level)填满以后再使用下一层
2. parent的优先级必须大于等于(小于等于 for min-heap)其children的优先级
3. Heap的高度是Θ(log n)

Heap Insertion:

• 将新item放入第一个空闲的位置 (参考heap的第一条性质)

• 对其执行bubble-up, 直到符合所有heap性质
  #bubble-up:

  
  
  

  while [parent(v) exists and key(parent(v)) < key(v)] do 
      swap v and parent(v) v <- parent(v)
  

Heap deleteMax/Min:

• 用heap中的最后一个item取代root

• 对其执行bubble-down, 直到符合所有heap性质

  
  
  

  bubble-down

  
  
  

  while [v is not a leaf] do 
      u <- child of v with largest key 
      if key(u) > key(v) then 
          swap v and u v <- u 
      else 
          break
  

Heap array的特点 (当前item的位置为i):

• Left child位于2i+1
• Right child位于2i+2
• Parent位于floor[(i-1)/2]

建立heap的两种方法:

• 以空heap为起始, 逐个item执行insert
• 以含有n个item的array为起始, 从index为floor[(n-1)/2]的item开始, 逐个执行bubble-down, 直到index 0

注: 使用第二种方法建立heap, 然后执行k次deleteMax/Min, 可快速查找array中第k大的iterm. 运行时间为Θ(n + k log n)

其他方法请参考: 找数组/VECTOR内第K大的数

更多CS 240总结请看: http://blog.gregwym.info/tag/cs240/

Runtime的符号

• Big-O 表示当c和n0在达到一定大小以后, runtime小于等于某一数级[g(x)]
• Little-O (与Big-O对应) 表示当c和n0为任意值时, runtime一定小于某一数级[g(x)]
• Ω 表示当c和n0达到一定大小以后, runtime大于等于某一数级[g(x)]
• ω (与Ω对应) 表示c和n0为任意值时, runtime一定大于某一数级[g(x)]
• Θ 为同时满足Big-O和Ω

• Logarithmic (log n)
• Linear (n)
• Linearithmic (n log n)
• Quadratic (n^2)
• Cubic (n^3)
• Exponential (2^n)

入了个新的域名, 打算做点小应用试试.

原来的Nginx设定里, 子域名会自动对应子目录. 如果碰巧有人输入了我为新域名设定的目录名, 就会造成域名不统一的情况出现...所以研究了下301定向, 发现Nginx的设置真的好简单.

在nginx.conf里的自动对应规则之前, 加入下边的内容

server { 
    server_name www.xxxx.com; 
    rewrite ^(.*) http://xxxx.com$1 permanent; 
}

继续去整理240的内容了...

我的QQ邮箱现在已经有3T容量了...
原来玩WordPress的时候其实就一直拿来做数据库备份, 现在容量变大几倍有余, 自然是备份的不二选择. 这可比FDC的大容量VPS划算多了, 特别是当你的网站并没有多大的时候. (书苑现在的数据库也都还没有1G...)

这个脚本来自小夜博客, 经我略加修改了一下.
下载: backup_to_mail.sh

很简单的一段bash script, 只需要自定义下mysql的用户名密码, 邮箱地址和要备份的目录.

然后进行下边的步骤:

首先要建立好放置备份文件的目录

mkdir /home/backup

然后安装发送邮件的程序

yum install sendmail mutt

把backup_to_mail.sh放到刚刚建立的目录中, 然后给脚本增加运行权限

chmod a+x /home/backup/backup_to_mail.sh

最后一步是设置定时运行, 输入

crontab -e

然后在vi编辑界面中加入下面这行文字

00 00 * * * /home/backup/backup_to_mail.sh

:x + enter就ok了.

其中00 00表示在每日00分, 00点的时候运行该脚本.

下边是脚本的内容, 以备附件失效和以后学习...

#!/bin/bash
MYSQL_USER=root                             #mysql username
MYSQL_PASS=***********                      #mysql password
MAIL_TO=*******@***.**                      #mailling to
WEB_DATA=/home/wwwroot/                     #to be backup dir

#define variables
DataBakName=Data_$(date +%Y%m%d).tar.gz
WebBakName=Web_$(date +%Y%m%d).tar.gz
OldData=Data_$(date -d -3day +%Y%m%d).tar.gz
OldWeb=Web_$(date -d -3day +%Y%m%d).tar.gz
DataSubject="Backup: gregwym.info database "$(date +%Y%m%d)
WebSubject="Backup: gregwym.info web dir "$(date +%Y%m%d)

#delete data from 3days earlier
rm -rf /home/backup/$OldData /home/backup/$OldWeb
cd /home/backup

#export database to compressed gz files
for db in `/usr/local/mysql/bin/mysql -u$MYSQL_USER -p$MYSQL_PASS -B -N -e 'SHOW DATABASES' | xargs`; do
    (/usr/local/mysql/bin/mysqldump --single-transaction -u$MYSQL_USER -p$MYSQL_PASS ${db} | gzip -9 - > ${db}.sql.gz)
done

#compress database files
tar zcf /home/backup/$DataBakName /home/backup/*.sql.gz
rm -rf /home/backup/*.sql.gz
#mail database
echo $DataSubject | mutt -a /home/backup/$DataBakName -s "${DataSubject}" $MAIL_TO

#compress backup dir
tar zcf /home/backup/$WebBakName $WEB_DATA
#mail dir
echo $WebSubject | mutt -a /home/backup/$WebBakName -s "${WebSubject}" $MAIL_TO

echo "bye"
#END

如果不希望备份网页文件, 或者希望数据库和网页分别备份的, 可以自行拆分脚本为两个文件.

如果只是想降低备份网页文件的频率, 可以将#mail dir部分替换为:

if [ $(date +%A) = "Sunday" ]; then 
    echo $WebSubject | mutt -a /home/backup/$WebBakName -s "${WebSubject}" $MAIL_TO 
fi

弄完最后的物理作业本想接着把STAT也搞定`可看看有8页之多...还是先睡一觉再说吧, 这两天时差又乱套了, 要调回来.
距离12点还有点时间, 换换脑子随便写点东西...

高中的时候就折腾过WordPress, 借朋友的空间搭了个小博`写了两句就没兴致继续下去了. 大部分时间都花在了研究各种插件上边. 但不知道为什么, WordPress一直就没有让我有强烈的归属感. 虽然它插件很多, 主题很多, 能高度定制化...可都少了点什么.

啊`是他太乱了...

添加了各种杂七杂八的插件以后, 单侧栏恐怕都塞不下了, 再配上本就没什么几篇的博文列表, 整个页面显得臃肿杂乱`主次颠倒, 自然也就没有了继续下去的动力.
虽然这算是我自己的客观因素...但WordPress越长越肥, 功能繁多却不实用的现状是毋庸置疑的.

不记得到底是先注意到Typecho, 还是先动了玩VPS的主意, 反正这俩分不开. 在某博看到Typecho的介绍和他简洁的风格时就决定了我肯定要抛弃WordPress了.

他实在太简单了...

• 安装只要填写管理员, 站点信息和数据库配置就万事大吉, 一步到位.
• 一个博客需要的东西, 五脏俱全. 在添加了代码加亮, 博客友联等几个常用插件之后, 可以直接开拔.
• 后台就是简简单单的内容+评论管理, 和外观设定.
• 主题导入后, 自己调整些零碎也很得心应手.
• 数据库一共只有6张表.
• 主题文件只分, 头`脚`内容`评论`侧栏`列表...外加一张style-sheet. 从头到脚透露这简单的概念.

按Typecho官方说法, 一个完全重写的全新后台系统正在开发中, 实在是非常期待.
有想法要好好学习下Typecho的源码, 不过还是先考完试再说吧.

附个在别处看到的相关短文, 深以为然:

为什么放弃Wordpress使用Typecho?

时间差不多了...睡觉睡觉`