全局最小割算法

05 Jun 2015

问题描述

给出一个无向图$G=(V, E)$,要求删除一些边,使得整个图不联通,同时删去的边尽量少。

算法一

如果我们可以求出任意一个$s-t$最小割$C$,那么$G$的全局最小割是$C$与的全局最小割中较小的一个。

在图$G$中求任意一个$s-t$最小割的方法如下。

设$a$是$V$中任意一个顶点,点集$A$是$V$的一个子集,初始时等于。我们每次在$V-A$中选取一个$w(A, x)$最大的点$x$加入$A$中,直到$A=V$时停止。这里,对于一个不属于$A$的点$x$,有

令$x$为倒数第二个加入$A$中的点,$t$为最后一个加入$A$中的点,$t$和其它所有点的连边组成的集合就是一个$s-t$最小割。

如果使用Fibonacci堆存储$V-A$中的点,时间复杂度为$O(mn+n^2\log n)$。

算法二

这是个概率算法,同样运用点的合并。算法包括$n-2$此迭代。每次迭代中,算法从图的现有边中随机选出一条边并将边的两个顶点合并。每一次迭代会使顶点减少一个,经过$n-2$次迭代之后,图只剩下两个顶点。算法输出连接这两个顶点保留的边的集合。

设$E_i$表示第$i$次迭代时不在最小割集$C$中这一事件,$F_i = \bigcap_{j=1}^{i} E_j$表示前$i$次迭代中没有缩减$C$中的边。我们需要计算$P(F_{n-2})$。

令$k=| C |$,则图中至少有$\frac{nk}{2}$条边。所以

类似地

所以

假设进行$n(n-1)\ln n$次此随机算法,并输出所有结果的最小者,输出不是一个最小割集的概率是

这里我们用到了$1-x\le e^{-x}$.

进程间通信

13 Apr 2015

管道

popen

可能最简单的在两个进程之间通信的方法就是popen和pclose函数了。

popen

pclose会等待进程结束。如果pclose之前执行了wait,被调用进程退出状态会丢失,此时pclose返回-1并设置errno为ECHILD。

演示: 读取外部程序的输出

 1 #include <unistd.h>
 2 #include <stdlib.h>
 3 #include <stdio.h>
 4 #include <string.h>
 5 
 6 int main() {
 7     FILE *read_fp;
 8     char buffer[BUFSIZ + 1];
 9     int chars_read;
10     memset(buffer, '\0', sizeof(buffer));
11     read_fp = popen("uname -a", "r");
12     if (read_fp != NULL) {
13         chars_read = fread(buffer, sizeof(char), BUFSIZ, read_fp);
14         if (chars_read > 0) {
15             printf("Output was: -\n%s\n", buffer);
16         }
17         pclose(read_fp);
18         exit(EXIT_SUCCESS);
19     }
20     exit(EXIT_FAILURE);
21 }

演示: 输出到外部程序

 1 #include <unistd.h>
 2 #include <stdlib.h>
 3 #include <stdio.h>
 4 #include <string.h>
 5 
 6 int main() {
 7     FILE *write_fp;
 8     char buffer[BUFSIZ + 1];
 9     sprintf(buffer, "Once upon a time, there was...\n");
10     write_fp = popen("od -c", "w");
11     if (write_fp != NULL) {
12         fwrite(buffer, sizeof(char), strlen(buffer), write_fp);
13         pclose(write_fp);
14         exit(EXIT_SUCCESS);
15     }
16     exit(EXIT_FAILURE);
17 }

pipe

pipe是较popen底层的函数。

pipe

关于errno的设置,linux手册中定义了下面的错误:

  • EMFILE: 进程使用的文件描述符过多。
  • ENFILE: 系统文件表已满。
  • EFAULT: 文件描述符无效。

写到file_descriptor[1]的所有数据可以从file_descriptor[0]读回来。

演示: 跨越fork调用的管道

 1 #include <stdio.h>
 2 #include <unistd.h>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 
 6 int main() {
 7     int data_processed;
 8     int file_pipes[2];
 9     const char some_data[] = "294753618";
10     char buffer[BUFSIZ + 1];
11     pid_t fork_result;
12 
13     memset(buffer, 0, sizeof(buffer));
14 
15     if (pipe(file_pipes) == 0) {
16         fork_result = fork();
17         if (fork_result == -1) {
18             fprintf(stderr, "Fork failure");
19             exit(EXIT_FAILURE);
20         }
21 
22         if (fork_result == 0) { // child
23             data_processed = read(file_pipes[0], buffer, BUFSIZ);
24             printf("Read %d bytes: %s\n", data_processed, buffer);
25             exit(EXIT_SUCCESS);
26         } else { // father
27             data_processed = write(file_pipes[1], some_data, strlen(some_data));
28             printf("Write %d bytes\n", data_processed);
29             wait(fork_result);
30         }
31     }
32     exit(EXIT_SUCCESS);
33 }

命名管道FIFO

FIFO在文件系统中以文件名的形式存在。

fifo

打开FIFO文件的模式有几种不同组合

open(const char *path, O_RDONLY);

这种情况下,open会阻塞,除非有一个进程以写的方式打开同一个FIFO。

open(const char *path, O_RDONLY | O_NONBLOCK);

open立刻返回。

open(const char *path, O_WRONLY);

open阻塞,知道有一个进程以读的方式打开同一个FIFO。

open(const char *path, O_WRONLY | O_NONBLOCK);

立刻返回,但如果没有一个进程以读的方式打开FIFO文件,open将返回-1并且FIFO也不会被打开。

信号量机制

使用下面这组函数就够了。

1 #include <sys/sem.h>
2 
3 int semctl(int sem_id, int sem_num, int command, ...);
4 int semget(key_t key, int num_sems, int sem_flags);
5 int semop(int sem_id, struct sembuf *sem_ops, size_t num_sem_ops);

参数key的作用很像一个文件名,它代表程序可能要使用的某个资源,如果多个程序使用相同的key值,它将负责协调工作。

semget的作用是创建一个新信号量或取得一个已有信号量的键值。

semget

semop用于改变信号量的值。

semop

semctl函数用来直接控制信号量信息。

semctl

演示: 使用信号量

使用这个命令编译运行

$ gcc sem.c -o sem
$ ./sem 1 &
$ ./sem

字符XO分别表示第一个和第二个调用实例。

  1 /*
  2    file: sem.c
  3    If the program is the first to be called (i.e. it's called with a parameter
  4    and argc > 1), a call is made to set_semvalue to initialize the semaphore and op_char is
  5    set to X. */
  6 
  7 #include <unistd.h>
  8 #include <stdlib.h>
  9 #include <stdio.h>
 10 
 11 #include <sys/sem.h>
 12 
 13 #if defined(__GNU_LIBRARY__) && !defined(_SEM_SEMUN_UNDEFINED)
 14     /* union semun is defined by including <sys/sem.h> */
 15 #else
 16     /* according to X/OPEN we have to define it ourselves */
 17     union semun {
 18         int val;                    /* value for SETVAL */
 19         struct semid_ds *buf;       /* buffer for IPC_STAT, IPC_SET */
 20         unsigned short int *array;  /* array for GETALL, SETALL */
 21         struct seminfo *__buf;      /* buffer for IPC_INFO */
 22     };
 23 #endif
 24 
 25 static int set_semvalue(void);
 26 static void del_semvalue(void);
 27 static int semaphore_p(void);
 28 static int semaphore_v(void);
 29 
 30 static int sem_id;
 31 
 32 
 33 int main(int argc, char *argv[]) {
 34     int i;
 35     int pause_time;
 36     char op_char = 'O';
 37 
 38     srand((unsigned int)getpid());
 39 
 40     sem_id = semget((key_t)1234, 1, 0666 | IPC_CREAT);
 41 
 42     if (argc > 1) {
 43         if (!set_semvalue()) {
 44             fprintf(stderr, "Failed to initialize semaphore\n");
 45             exit(EXIT_FAILURE);
 46         }
 47         op_char = 'X';
 48         sleep(2);
 49     }
 50 
 51     for(i = 0; i < 10; i++) {
 52 
 53         if (!semaphore_p()) exit(EXIT_FAILURE);
 54         printf("%c", op_char);fflush(stdout);
 55         pause_time = rand() % 3;
 56         sleep(pause_time);
 57         printf("%c", op_char);fflush(stdout);
 58 
 59         if (!semaphore_v()) exit(EXIT_FAILURE);
 60         pause_time = rand() % 2;
 61         sleep(pause_time);
 62     }
 63 
 64     printf("\n%d - finished\n", getpid());
 65 
 66     if (argc > 1) {
 67         sleep(10);
 68         del_semvalue();
 69     }
 70 
 71     exit(EXIT_SUCCESS);
 72 }
 73 
 74 static int set_semvalue(void) {
 75     union semun sem_union;
 76 
 77     sem_union.val = 1;
 78     if (semctl(sem_id, 0, SETVAL, sem_union) == -1) return(0);
 79     return(1);
 80 }
 81 
 82 static void del_semvalue(void) {
 83     union semun sem_union;
 84 
 85     if (semctl(sem_id, 0, IPC_RMID, sem_union) == -1)
 86         fprintf(stderr, "Failed to delete semaphore\n");
 87 }
 88 
 89 static int semaphore_p(void) {
 90     struct sembuf sem_b;
 91 
 92     sem_b.sem_num = 0;
 93     sem_b.sem_op = -1; /* P() */
 94     sem_b.sem_flg = SEM_UNDO;
 95     if (semop(sem_id, &sem_b, 1) == -1) {
 96         fprintf(stderr, "semaphore_p failed\n");
 97         return(0);
 98     }
 99     return(1);
100 }
101 
102 static int semaphore_v(void) {
103     struct sembuf sem_b;
104 
105     sem_b.sem_num = 0;
106     sem_b.sem_op = 1; /* V() */
107     sem_b.sem_flg = SEM_UNDO;
108     if (semop(sem_id, &sem_b, 1) == -1) {
109         fprintf(stderr, "semaphore_v failed\n");
110         return(0);
111     }
112     return(1);
113 }

共享内存

共享内存的函数类似于信号量函数。

1 #include <sys/shm.h>
2 
3 void *shmat(int shm_id, const void *shm_addr, int shmflg);
4 int shmctl(int shm_id, int cmd, struct shmid_ds *buf);
5 int shmdt(const void *shm_addr);
6 int shmget(key_t key, size_t size, int shmflg);

我们用shmget函数来创建共享内存,如果失败,返回-1。

shmget

接下来,为了启动对该共享内存的访问,必须将其链接到一个进程的地址空间中,这项工作由shmat函数完成。

shmat

shmdt函数的作用是将共享内存从当前进程中分离。

shmdt

共享内存的控制函数要稍微简单一些。

shmctl

需要注意的是,进程同步部分需要自己写。

消息队列

和前面的方式类似。

1 #include <sys/msg.h>
2 
3 int msgctl(int msqid, int cmd, struct msqid_ds *buf);
4 int msgget(key_t key, int msgflg);
5 int msgrcv(int msqid, void *msq_ptr, size_t msg_sz, long int msgtype, int msgflg);
6 int msgsnd(int msqid, const void *msg_ptr, size_t msg_sz, int msgflg);

用msgget创建和访问一个消息队列。

用msgsnd把消息添加到消息队列中。

int msgsnd(int msqid, const void *msg_ptr, size_t msg_sz, int msgflg);

消息的结构必须以长整形开始。

1 struct my_massage {
2     long int massage_type;
3     /* data */
4 }

msgrcv从一个消息队列中获取消息。

int msgrcv(int msqid, void *msq_ptr, size_t msg_sz, long int msgtype, int msgflg);

如果msgtype为0,就获取第一个可用消息,如果大于0,就获取具有相同消息类型(massage_type)的第一个可用消息。如果想获取类型小于或等于n的消息,就传递-n。

msgctl与共享内存的控制函数非常相似。

int msgctl(int msqid, int cmd, struct msqid_ds *buf);

msqid_ds用至少包含以下成员:

struct shmid_ds {
    uid_t shm_perm.uid;
    uid_t shm_perm.gid;
    mode_t shmperm.mode;
};

cmd也和共享内存的一样。

演示: 消息队列

程序1

 1 /* Here's the receiver program. */
 2 
 3 #include <stdlib.h>
 4 #include <stdio.h>
 5 #include <string.h>
 6 #include <errno.h>
 7 #include <unistd.h>
 8 
 9 #include <sys/msg.h>
10 
11 
12 struct my_msg_st {
13     long int my_msg_type;
14     char some_text[BUFSIZ];
15 };
16 
17 int main() {
18     int running = 1;
19     int msgid;
20     struct my_msg_st some_data;
21     long int msg_to_receive = 0;
22 
23     msgid = msgget((key_t)1234, 0666 | IPC_CREAT);
24 
25     if (msgid == -1) {
26         fprintf(stderr, "msgget failed with error: %d\n", errno);
27         exit(EXIT_FAILURE);
28     }
29 
30     while(running) {
31         if (msgrcv(msgid, (void *)&some_data, BUFSIZ,
32                    msg_to_receive, 0) == -1) {
33             fprintf(stderr, "msgrcv failed with error: %d\n", errno);
34             exit(EXIT_FAILURE);
35         }
36         printf("You wrote: %s", some_data.some_text);
37         if (strncmp(some_data.some_text, "end", 3) == 0) {
38             running = 0;
39         }
40     }
41 
42     if (msgctl(msgid, IPC_RMID, 0) == -1) {
43         fprintf(stderr, "msgctl(IPC_RMID) failed\n");
44         exit(EXIT_FAILURE);
45     }
46 
47     exit(EXIT_SUCCESS);
48 }

程序2

 1 #include <stdlib.h>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <errno.h>
 5 #include <unistd.h>
 6 
 7 #include <sys/msg.h>
 8 
 9 #define MAX_TEXT 512
10 
11 struct my_msg_st {
12     long int my_msg_type;
13     char some_text[MAX_TEXT];
14 };
15 
16 int main() {
17     int running = 1;
18     struct my_msg_st some_data;
19     int msgid;
20     char buffer[BUFSIZ];
21 
22     msgid = msgget((key_t)1234, 0666 | IPC_CREAT);
23 
24     if (msgid == -1) {
25         fprintf(stderr, "msgget failed with error: %d\n", errno);
26         exit(EXIT_FAILURE);
27     }
28 
29     while(running) {
30         printf("Enter some text: ");
31         fgets(buffer, BUFSIZ, stdin);
32         some_data.my_msg_type = 1;
33         strcpy(some_data.some_text, buffer);
34 
35         if (msgsnd(msgid, (void *)&some_data, MAX_TEXT, 0) == -1) {
36             fprintf(stderr, "msgsnd failed\n");
37             exit(EXIT_FAILURE);
38         }
39         if (strncmp(buffer, "end", 3) == 0) {
40             running = 0;
41         }
42     }
43 
44     exit(EXIT_SUCCESS);
45 }

Design Patterns

29 Mar 2015

Table of Contents:

Observer Pattern

You know the newspaper or magazine subscriptions work:

  1. A newspaper publisher goes into business and begins publishing newspapers.
  2. You subscribe to a particular publisher, and every time there’s a new edition it gets delivered to you. As long as you remain a subscriber, you get new newspapers.
  3. You unsubscribe when you don’t want papers anymore, and they stop being delivered.
  4. While the publisher remains in business, people, hotels, airlines and other businesses constantly subscribe and unsubscribe to the newspaper.

Publisher + Subscribers = Observer Pattern

closerlook

The Observer Pattern defined: the class diagram

opd

notifyObserver() may call update() of every Observer that had been registered.

Decorator Pattern

Constructing a drink order with Decorators

We start with our DarkRoast object.

drink

The customer wants Mocha, so we create a Mocha object and wrap it around the DarkRoast.

drink1

The customer also wants Whip, so we create a Whip decorator and wrap Mocka with it.

drink2

Now it’s tome to compute the cost for the customer.

  1. First, we call cost() on the outmost decorator, Whip.
  2. Whip calls cost() on Mocha.
  3. Mocha calls cost() on DakRoast.
  4. DarkRoast returns its cost, 99 cents.
  5. Mocha adds its cost, 20 cents, to the result from DarkRoast, and returns the new total, $1.19.
  6. Whip adds its total, 10 cents, to the result from Mocha, and returns the final result–$1.29.

The Decorator Pattern defined

decoretordefine

Example: The Beverage code

 1 public abstract class Beverage {
 2     String description = "Unknown Beverage";
 3     public String getDescription() {
 4         return description;
 5     }
 6     public abstract double cost();
 7 }
 8 
 9 public abstract class CondimentDecorator extends Beverage {
10     public abstract String getDescription();
11 }
12 
13 public class Espresso extends Beverage {
14     public Espresso() {
15         description = "Espresso";
16     }
17     public double cost() {
18         return 1.99;
19     }
20 }
21 
22 public class HouseBlend extends Beverage {
23     public HouseBlend() {
24         description = "House Blend Coffee";
25     }
26     public double cost() {
27         return 0.89;
28     }
29 }
30 
31 public class Mocha extends CondimentDecorator {
32     Beverage beverage;
33     public Mocha(Beverage beverage) {
34         this.beverage = beverage;
35     }
36     public String getDescription() {
37         return beverage.getDescription() + ", Mocha";
38     }
39     public double cost() {
40         return 0.20 + beverage.cost();
41     }
42 }
43 
44 public class OpenCoffee {
45     public static void main(String args[]) {
46         Beverage beverage = new Espresso();
47         System.out.println(beverage.getDescription() + " $" + beverage.cost());
48 
49         Beverage beverage2 = new HouseBlend();
50         beverage2 = new Mocha(beverage2);
51         beverage2 = new Mocha(beverage2);
52         beverage2 = new Whip(beverage2);
53         System.out.println(beverage2.getDescription() + " $" + beverage2.cost());
54     }
55 }

Command Pattern

In object-oriented programming, the command pattern is a behavioral design pattern in which an object is used to represent and encapsulate all the information needed to call a method at a later time. This information includes the method name, the object that owns the method and values for the method parameters.

command

 1 public interface Order {
 2     public abstract void execute();
 3 }
 4 
 5 // Receiver
 6 class StockTrade {
 7     public void buy() {
 8         System.out.println("You want to buy stocks");
 9     }
10     public void sell() {
11         System.out.println("You want to sell stocks ");
12     }
13 }
14 
15 // Invoker
16 class Agent {
17     private m_ordersQueue = new ArrayList();
18 
19     public Agent() {
20     }
21 
22     void placeOrder(Order order) {
23         ordersQueue.addLast(order);
24         order.execute(ordersQueue.getFirstAndRemove());
25     }
26 }
27 
28 //ConcreteCommand
29 class BuyStockOrder implements Order {
30     private StockTrade stock;
31     public BuyStockOrder (StockTrade st) {
32         stock = st;
33     }
34     public void execute() {
35         stock.buy();
36     }
37 }
38 
39 //ConcreteCommand
40 class SellStockOrder implements Order { 
41     private StockTrade stock;
42     public SellStockOrder (StockTrade st) {
43         stock = st;
44     }
45     public void execute() {
46         stock.sell();
47     }
48 }
49 
50 // Client
51 public class Client {
52     public static void main(String[] args) {
53         StockTrade stock = new StockTrade();
54         BuyStockOrder bsc = new BuyStockOrder (stock);
55         SellStockOrder ssc = new SellStockOrder (stock);
56         Agent agent = new Agent();
57 
58         agent.placeOrder(bsc); // Buy Shares
59         agent.placeOrder(ssc); // Sell Shares
60     }
61 }

Singleton Pattern

There are many objects we only need one of: thread pools, caches, dialog, boxes, object that handle preferences and registry settings, objects used for logging, and objects that act as device drivers to devices like printers and graphics cards. In fact, for many of these types of objects, if we were to instantiate more than one we’d run into all sort of problems like incorrect program behavior, overuse of resources, or inconsistent results.

how

 1 public class Singleton {
 2     private static Singleton uniqueInstance;
 3     // other useful instance varuables here
 4 
 5     private Singleton() {}
 6 
 7     public static synchronized Singleton getInstance() {
 8         if (uniqueInstance == null) {
 9             uniqueInstance = new Singleton();
10         }
11         return uniqueInstance;
12     }
13 
14     // other useful methods here
15 }

Or move to an eagerly created instance rather than a lazily create one.

1 public class Singleton {
2     private static Singleton uniqueInstance = new getInstance();
3 
4     private Singleton() {}
5 
6     public static Singleton getInstance() {
7         return uniqueInstance;
8     }
9 }

Use “double-checked locking” to reduce the use of synchronization in getInstance().

 1 public class Singleton {
 2     private volatile static Singleton uniqueInstance;
 3 
 4     private Singleton() {}
 5 
 6     public static Singleton getInstance() {
 7         if (uniqueInstance == null) {
 8             synchronized (Singleton.class) {
 9                 if (uniqueInstance == null) {
10                     uniqueInstance = new getInstance();
11                 }
12             }
13         }
14         return uniqueInstance;
15     }
16 }

Adapter Pattern

The Adapter Pattern converts the interface of a class into another interface the clients expect. Adapter lets classes work together that couldn’t otherwise because of incompatible interfaces.

Object Adapter

objectadapter

Class Adapter

ClassAdapter