mac

1. Tools

Mac with 10.9, another screen, guard, livereload, rails, chrome

Install Addon for chrome

1
https://chrome.google.com/webstore/detail/jnihajbhpnppcggbcgedagnkighmdlei

2. Install Gem

1
2
3
group :development do
  gem 'guard-livereload', require: false
end
1
2
bundle install
guard init livereload

3. Configure your Mac

System Preferences -> Displays

4. Enjoy it

1
guard

Click the LiveReload button in Chrome. Now Chrome will load the new content automatically!

Load config

1
2
3
4
5
6
7
8
9
10
11
12
13
RAILS_ENV  = ENV['RAILS_ENV']  = 'production'
RAILS_ROOT = ENV['RAILS_ROOT'] = '/path/to/your_app/current'
PID_DIR    = '/path/to/your_app/shared/pids'
BIN_PATH   = "/usr/local/rvm/gems/ruby-2.0.0-p247/bin"
UID = 'root'
GID = 'root'

God.log_file  = "#{RAILS_ROOT}/log/god.log"
God.log_level = :info

%w(unicorn sidekiq).each do |config|
  God.load "#{RAILS_ROOT}/config/god/#{config}.god"
end
Read on →

DB SERVER

msyql

1
2
3
4
yum install mysql-server
service mysqld start
chkconfig mysqld on
/usr/bin/mysql_secure_installation

mysql -uroot -p

GRANT ALL PRIVILEGES ON . TO root@myip IDENTIFIED BY 'rootpassword' WITH GRANT OPTION;

vi /etc/sysconfig/iptables -A RH-Firewall-1-INPUT -s intranet_local -m state –state NEW -m tcp -p tcp –dport 3306 -j ACCEPT

Read on →

Load Engine

Gemfile

1
gem 'enginename',    :path => "./engines/enginename"

config/application.rb

1
config.paths['db/migrate'] << 'engines/engine_name/db/migrate'

app/assets/stylesheets/application.css

1
*= require engine_name/application

app/assets/javascripts/application.js

1
//= require engine_name/application

load engine routes, config/routes.rb

1
mount EngineName::Engine => "/engine_name"

Read on →

1. Create about page

1
rake new_page["about"]

will generate following output

1
2
mkdir -p source/about
Creating new page: source/about/index.markdown

2. Edit about page

vi source/about/index.markdown

3. Add about link to navigation

vi source/_includes/custom/navigation.html

1
2
3
4
5
<ul class="main-navigation">
  <li><a href="/">Blog</a></li>
  <li><a href="/blog/archives">Archives</a></li>
  <li><a href="/about">About</a></li>
</ul>

1. Setup Octopress

1
2
3
4
5
6
git clone git://github.com/imathis/octopress.git octopress
cd octopress
  
gem install bundler
bundle install
rake install

2. Configuring Octopress

1
vi _config.yml

3. Install Greyshade Theme

https://github.com/shashankmehta/greyshade

1
2
3
4
$ git clone git@github.com:shashankmehta/greyshade.git .themes/greyshade
$ echo "\$greyshade: color;" >> sass/custom/_colors.scss //Substitue 'color' with your highlight color
$ rake "install[greyshade]"
$ rake generate
Read on →

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>

//邻接表
#define MAX_VERTICES 50
typedef struct node *node_pointer;
typedef struct node{
    int vertex;
    struct node *link;
}node;
node_pointer graph[MAX_VERTICES];
int n=0;

#define FALSE 0
#define TRUE 1
short int visited[MAX_VERTICES];

深度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int v)
{
    //depth first search of a graph beginning with vertex 
    node_pointer w;
    visited[v] = TRUE;
    printf("%5d",v);
    for(w=graph[v];w;w=w->link){
        if(!visited[w->vertex]){
            dfs(w->vertex);
        }
    }
}

广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
typedef struct queue *queue_pointer;
typedef struct queue{
    int vertex;
    queue_pointer link;
}queue;
void addq(queue_pointer *,queue_pointer *,int);
int deleteq(queue_pointer *);

void bfs(int v){
    node_pointer w;
    queue_pointer front,rear;
    front=rear=NULL;
    printf("%5d",v);
    visited[v] = TRUE;
    addq(&front, &rear, v);
    while(front){
        v= deleteq(&front);
        for(w=graph[v];w;w=w->link){
            if(!visited[w->vertex]){
                printf("%5d",w->vertex);
                addq(&front, &rear, w->vertex);
                visited[w->vertex]=TRUE;
            }
        }
    }
}
C

1
2
#include <stdio.h>
#define COMPARE(x,y) ((x)>(y) ? 1 : ((x) == (y)) ? 0 : -1)

Seqsearch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//O(n)
int seqsearch(int list[],int n,int searchnum){
    int i;
    list[n]=searchnum;  //内存会溢出么?
    for(i=0;list[i]!=searchnum;i++)
        ;
    return ((i<n)?i:-1);
}

int my_seqsearch(int list[],int n,int searchnum){
    int i;
    for(i=0;i<n;i++){
        if(list[i]==searchnum) return i;
    }
    return -1;
}

Binsearch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//O(log n)
int binsearch(int list[],int n,int searchnum){
    int left,right,middle;
    left = 0;
    right = n-1;
    
    while(left<=right){
        middle = (left + right) / 2;
        switch(COMPARE(list[middle],searchnum)){
            case 1:
                right = middle - 1;
                break;
            case 0:
                return middle;
                break;
            case -1:
                left = middle + 1;
                break;
        }
    }
    return -1;
}

Verify

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//顺序查找进行表验证O(mn)
#define MAX_SIZE 1024
void verify1(int list1[],int list2[],int n,int m){
    int i,j;
    int marked[MAX_SIZE];
    
    for(i=0;i<m;i++){
        marked[i] = 0;
    }
    for(i=0;i<n;i++){
        if((j=seqsearch(list2,m, list1[i]) < 0))
            printf("%d is not in list 2 \n",list1[i]);
        else
            marked[j]=1;
    }
    for(i=0;i<m;i++){
        if(marked[i]==0){
            printf("%d is not in list1 \n",list2[i]);
        }
    }
}

//两个表的快速验证
//O(tsort(n)+tsort(m)+m+n),假如sort()为O(nlogn),则最终O(max[nlogn,mlogm])
void verify2(int list1[],int list2[],int n,int m){
    int i,j;
    sort(list1,n);
    sort(list2,n);
    i=j=0;
    while(i<n && j<m){
        if(list1[i] <list2[j]){
            printf("%d is not in list 2",list1[i]);
            i++;
        } else if (list1[i]==list2[j]){
            i++;j++;
        } else {
            printf("%d is not in list1 \n" ,list2[j]);
            j++;
        }
    }
    for(;i<n;i++){
        printf("%d is not in list 2 \n",list1[i]);
    }
    for(;j<n;j++){
        printf("%d is not in list 1 \n",list2[j]);
    }
}

1
2
3
4
// 排序n个不同元素的判定树的高度至少为(log2 (n!))+1
// 任何基于关键字比较的排序算法,在最坏情况下的时间复杂度为O(n(logn2 n))

#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))

Bubble sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//冒泡排序O(n2),稳定
void bubblesort(int list[],int n){
    int i,j,temp,flag;
    for(i=0;i<n;i++){
        flag=0;
        for(j=n-1;j>i;j--){
            if(list[j-1]>list[j]){
                SWAP(list[j], list[j-1], temp);
                flag=1;
            }
        }
        if(flag == 0) break;  //没有交换则跳出。
    }

}

Select sort

1
2
3
4
5
6
7
8
9
10
11
//选择排序 O(n2),不稳定
void select_sort(int list[],int n){
    int temp,i,j,min;
    for(i=0;i<n-1;i++){
        min=i;
        for(j=i+1;j<n;j++){
            if(list[j] < list[min]) min=j;
        }
        SWAP(list[i],list[min],temp); //导致不稳定
    }
}

Insert sort

1
2
3
4
5
6
7
8
9
10
11
12
13
//插入排序 O(n2),稳定,适合规模小的序列表
//变形:折半插入排序,减少查找次数,移动次数不变
//     链表插入排序,不需移动记录,只能使用顺序查找
void insert_sort(int list[],int n){
    int i,j,next;
    for(i=1;i<n;i++){
        next = list[i];
        for(j=i-1;j>=0 && next < list[j];j--){
            list[j+1]=list[j];
        }
        list[j+1]=next;
    }
}

Quick sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//快速排序O(n2),平均O(nlogn),不稳定
void quicksort(int list[],int left,int right){
    int i,j,pivot;
    int temp; //用于swap

    if(left<right){
        i=left;j=right+1;
        pivot=list[left];
        do{
            do
                i++;
            while(list[i]<pivot);
            do
                j--;
            while(list[j]>pivot);
            if(i<j)
                SWAP(list[i], list[j], temp);
        }while(i<j);
        SWAP(list[left], list[j], temp);
        quicksort(list, left, j-1);
        quicksort(list, j+1, right);
    }
}

Merge sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//归并两个已排序的表,空间复杂性O(n)
void merge(int list[],int sorted[],int i,int m,int n){
    //merge two sorted files : list[i]..list[m] and list[m+1]..list[n] to a sorted list sorted[i]..sorted[n]
    int j,k,t;
    j=m+1;//index for the second sublist
    k=i;//index for the sorted list
    while(i<=m && j<=n){
        if(list[i] <= list[j])
            sorted[k++]=list[i++];
        else
            sorted[k++]=list[j++];
    }


        //sorted[k]..sorted[n] = list[j]..list[n]
        while(j<=n)
            sorted[k++]=list[j++];

        //sorted[k]..sorted[n] = list[i]..list[m]
        while(i<=m)
            sorted[k++]=list[i++];
}

void merge_pass(int list[],int sorted[],int n,int length){
    //perform one pass of the merge sort.
    //It merges adjacent(邻近) pairs of subfiles from list int sorted
    //n is the number of list,length is the length of the subfile
    int i,j;
    for(i=0;i<=n-2*length;i+=2*length){
        merge(list, sorted, i, i+length-1, i+2*length-1);
    }
    //#如果一段是正好可归并的数量而另一段则少于正好可归并的数量#
    if(i+length < n){
        merge(list, sorted, i, i+length-1, n-1);
    } else {
        for(j=i;j<n;j++){//#如果只剩下一段或者更少的数量#
            sorted[j]=list[j];
        }
    }

}

//总归并次数log2 n,每遍归并时间O(n),所以O(nlogn)
//额外空间开销与待排文件的记录个数成比例
void iter_merge_sort(int list[],int n){
    int length = 1;
//    int extra[MAX_SIZE];
    int extra[n];

    while(length < n){
        merge_pass(list, extra, n, length);
        length *=2;
        merge_pass(extra, list, n, length);
        length *=2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
void wiki_merge(int array[], int low, int mid, int high)
{
    int i, k;
    int begin1 = low;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = high;

    //申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
    int *temp = (int *) malloc((high-low+1) * sizeof(int));

    //比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
    for (k = 0; begin1 <= end1 && begin2 <= end2; ++k)
    {
        if(array[begin1]<=array[begin2])
        {
            temp[k] = array[begin1++];
        }
        else
        {
            temp[k] = array[begin2++];
        }
    }

    //若第一个序列有剩余,直接拷贝出来粘到合并序列尾
    if(begin1 <= end1)
    {
        memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
    }
    //若第二个序列有剩余,直接拷贝出来粘到合并序列尾
    if(begin2 <= end2)
    {
        memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
    }
    //将排序好的序列拷贝回数组中
    memcpy(array+low, temp, (high-low+1)*sizeof(int));
    free(temp);
}

void wiki_merge_sort(int array[], unsigned int first, unsigned int last)
{
    int mid = 0;
    if(first<last)
    {
        /*mid = (first+last)/2;*/ /*注意防止溢出*/
        /*mid = first/2 + last/2;*/
        mid = (first & last) + ((first ^ last) >> 1);
        wiki_merge_sort(array, first, mid);
        wiki_merge_sort(array, mid+1,last);
        wiki_merge(array,first,mid,last);
    }
}

Heap sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//调整最大堆
//该函数的参数为一颗二叉树T,T的左右子树均满足堆的性质,只有根节点可能不满足
//该函数调整T,使得整个二叉树都满足堆的性质
void adjust(int list[],int root,int n){
    int child;
    int temp;
    temp = list[root];
    child = 2* root; // left child
    while(child <=n){
        if ((child < n) && (list[child] < list[child+1])){
            child++;
        }
        if(temp > list[child]){ // compare root and max child
            break;
        } else {
            list[child/2]=list[child]; // move to parent
            child*=2;
        }
    }
    list[child/2]=temp;
}

//第二个for循环中,调用adjust共n-1次,且树的最大深度为log(2)(n+1),所以O(nlogn),不稳定
//注意堆的下标从1开始,list[0]不排序
void heapsort(int list[],int n){
    int i;
    int temp;

    for(i=n/2;i>0;i--){
        adjust(list, i, n);
    }
    for(i=n-1;i>0;i--){
        SWAP(list[1], list[i+1], temp);
        adjust(list, 1, i);
    }
}

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int main (int argc, const char * argv[])
{
    int list[] = {5,2,4,1,3};
    bubblesort(list,5);

    int i;
    for(i=0;i<5;i++){
        printf("%d",list[i]);
    }
    printf("\n");

    int list1[]={1,3,5,7,2,4,6,8};
    iter_merge_sort(list1,8);
    for(i=0;i<8;i++)
        printf("%d ",list1[i]);

    printf("\n");
    int list2[]={-1,26,5,77,1,61,11,59,15,48,19};
    heapsort(list2,10);
    for(i=1;i<=10;i++)
        printf("%d ",list2[i]);


    return 0;
}