Comparison-based sorting

最优Runtime为Ω(n log n)

QuickSelect

用QuickSort algorithm快速查找第k大的数 (avg rumtime: Θ(n))

组成函数

• choose-pivot(A) 在数据中选择其中一个作为pivot
• partition(A, p) 使用A[p]作为pivot, 将A中的数据分为
  
  
  • 所有小于等于pivot的数据
  • pivot本身
  • 所有大于pivot的数据

Implementation

下载: quickselect.cc

void swap(int *A, int i, int j){ 
    int temp; 
    temp = A[i]; 
    A[i] = A[j]; 
    A[j] = temp; 
    return; 
}

Read more...

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