Archive for ‘边走编程’ Category

August 25, 2009
bt的signal 
1

void (*signal (int sigNum, void (*sigHandler)(int))) (int);

乍一看这个函数原型就被唬住了，跟个指针似的。仔细分析一下，
*signal (int sigNum, void (*sigHandler)(int))
部分里面
(int sigNum, void (*sigHandler)(int))
优先级高于signal前面的*，所以这是个函数，*只是返回值的一部分，即返回的应该是一个指针。这个指针式什么类型的取决于
(*signal (int sigNum, void (*sigHandler)(int)))
外面的部分，前面是void，后面是(int)，可见signal函数返回的是一个函数指针，其函数原型为void f(int)。返回的这个指针与signal的第二个参数的类型是一样的。于是乎，这个bt的函数原型声明还可以这样来定义：

1
2

typedef void sigHandler(int);
sigHandler *signal(int, sigHandler *);

抑或是

1
2

typedef void (*psigHandler)(int);
psigHandler signal(int, psigHandler);

这种声明看起来真累！

Tags: ,. 15 views
Filed under: 边走编程 — dutor @ 1:09 pm Comments (0)
August 24, 2009
二分查找

没啥好说的，只是要注意防止m = (r + l) / 2;时m会发生上溢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

template <class T>
int BSearch(T *a, size_t n, T v)
{
    assert(a != NULL && n > 0); //! a == NULL || n <= 0 就坏了:-(
    size_t l = 0,
           r = n -1,
           m = l + (r - l) / 2; //! 勿用m=(l+r)/2;
    while(l <= r)
    {
        if(a[m] == v)
            return (int)m;
        else if(a[m] < v)
            l = m + 1;
        else
            r = m - 1;
    }
    return -1;
}
Tags: ,. 10 views
Filed under: 边走编程 — dutor @ 7:10 pm Comments (4)
August 23, 2009
原地归并算法一例

归并排序算法(mergesort)是将一个序列划分为同样大小的两个子序列，然后对两个子序列分别进行排序，最后进行合并操作，将两个子序列合成有序的序列。在合成的过程中，一般的实现都需要开辟一块与原序列大小相同的空间，以进行合并操作。这里介绍一种不需要开辟新的空间就可以进行归并操作的原地归并算法。代码来说事儿：

1
2
3
4
5
6
7
8
9

//~ 原地归并
while(l < r && r < size) //~ 核心算法
{
	while(v[l] <= v[r] && l < r) ++l; //~ 找到左面第一个比v[r]大的v[l]
	size_t to_mv = 0; //~ 计数器
	while(v[r] < v[l] && r < size) ++r, ++to_mv; //~ 右侧找到to_mv个比v[l]小的数
	Exchange(v+l, r-l-to_mv, r-l);//~ 将此to_mv个数移到v[l]前面
	l += to_mv; //~ 改变l，继续下一轮循环
}//~ l >-r 或者 r >= size时归并结束
Tags: ,,. 68 views
Filed under: 之算法神奇,边走编程 — dutor @ 9:36 pm Comments (1)
生产者-消费者问题
生产者-消费者问题：

生产者-消费者问题是经典的同步问题，它描述一组生产者进程(线程)向一组消费者进程(线程)提供消息。它们共享一个有界的缓冲池，生产者向其中投放消息，消费者从中取得消息。生产者-消费者问题是许多具体问题中进程(线程)合作的一个很好的抽象。假定缓冲区中有N个位置，每个位置存放一个消息。当缓冲区未满时，生产者可以投入一个消息，否则该进程(线程)阻塞，直到缓冲区内有空位可放；当缓冲区非空时，消费者可以从中取得一个消息，否则该进程(线程)阻塞，直到缓冲区内有消息可取。

为了模拟这一过程，首先需要设置一个大小为N的缓冲区。修改缓冲区时，需要同步各个进程(线程)以免发生错误(向满的缓冲区投放消息或者从空缓冲区内取出消息)。为此，需要设置两个信号量empty和full用以标识缓冲区中空位数和消息数。另外还需要一个互斥锁mutex以互斥地修改缓冲区。为了便于测试，这里缓冲区的大小设置为5，实际情况下，应该尽量大些，以免生产者和消费者相互等待。

Tags: ,,. 277 views
Filed under: Unix/Linux,边走编程 — dutor @ 4:40 pm Comments (0)
August 22, 2009
线程消息队列
  1. 减少pthread_cond_signal和sem_post的调用，只在有必要的时候调用；
  2. 尽量避免pthread_mutex进入竞争态。增大消息队列的大小，可以有效减少竞态条件的出现。

/*
* 此处循环判断的原因如下：假设2个线程在getq阻塞，然后两者都被激活，
* 而其中一个线程运行比较块，快速消耗了2个数据，
* 另一个线程醒来的时候已经没有新数据可以消耗了。
* 另一点，man pthread_cond_wait可以看到，
* 该函数可以被信号中断返回，此时返回EINTR。
* 为避免以上任何一点，都必须醒来后再次判断睡眠条件。
* 更正：pthread_cond_wait是信号安全的系统调用，不会被信号中断。
*/

Tags: ,,. 148 views
Filed under: Unix/Linux,之语言特性,边走编程 — dutor @ 6:09 pm Comments (0)
还是delete

表明看来似乎合情合理，由于C++的多态特性，允许我们将一个子类地址赋给父类型的指针pb，释放对象时理所当然的对pb进行delete。但，在程序运行时，并没有输出M destructed…，即D::m的析构函数没有被调用，而m的析构函数是需要D::~D()来调用的，所以子类D的析构函数也没有被调用。这是很容易理解的，因为父类的析构函数不是virtual的。由此，我们得出结论，用来继承的父类的析构函数总应该是virtual的，除非你确定它绝对不会被用于多态。关于这一点，《Effective C++》里面已经讲到了。

除了上面的问题，我们还应该关心的是，尽管析构函数没有被调用，那M::i的空间被释放了吗？It’s a question！由于析构函数没有被调用，那么释放M::i的任务就完全落在了delete身上的了，那么delete做到了吗？It’s a very question！这又回到了上一篇日志中所描述的问题上了。我的观点是delete做到了它应该做的事情，它只负责释放当初new申请的空间，即对象本身，至于对象里面是否有动态申请的内存，那就不是delete而是对象析构函数自己的工作了。

Tags: ,,. 18 views
Filed under: 之语言特性,边走编程 — dutor @ 10:35 am Comments (0)
August 21, 2009
pthread_mutex一例 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int
main()
{
	pthread_mutex_init(&mutex, NULL); //~ 初始化互斥锁mutex
	pthread_t thread_id;
	void *exit_status;
	pthread_create(&thread_id, NULL, thread_function, NULL); //~ 创建新线程
	for(int i = 0; i < 10; ++i)
	{
		usleep(10000); //~ 延时10ms
		//~ 访问共享数据
		pthread_mutex_lock(&mutex);
		cout<<share<<endl;
		pthread_mutex_unlock(&mutex);
	}
	pthread_join(thread_id, &exit_status); //~ 等待线程结束
	pthread_mutex_destroy(&mutex); //~ 销毁互斥锁
	return 0;
}
Tags: ,. 163 views
Filed under: 之语言特性,边走编程 — dutor @ 8:11 pm Comments (0)
August 19, 2009
用streambuf更改fstream的缓冲区

源码之前，了无秘密。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

//~ demo.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <streambuf>
using namespace std;
//~ 测试代码 :)
int main()
{
	ifstream in("demo.cpp");
	char buffer[4096]="original content in this buffer";
	cout<<buffer<<endl;
	streambuf * ptrbuff = in.rdbuf(); //~ 将streambuf与文件句柄关联
	ptrbuf->pubsetbuf(bufer, 4096); //~ 设置缓冲区，即设置in的缓冲区
	cout<<buffer<<endl; //~ 此时bufer里面的内容还是original content in this buffer
	string str;
	in>>str; //~ 真正要输入时bufer才被填充为in的内容
	cout<<str<<endl;
	cout<<buffer<<endl;
	return 0;
}

另外，还有一个filebuf，用法相近。看了很多C++方面的书，从来没有那本书对I/O流做过详细的介绍。C里面有setbuf可以修改缓冲区，但我在fstream里面却没看到这么个setbuf，rdbuf倒是有一个，它返回streambuf类型的指针。搜索streambuf的用法，无果，MSDN里面看到streambuf有一个setbuf的成员，甚喜。编译器说，setbuf是私有的，再看MSDN，还有一个pubsetbuf，哟西！

Tags: ,. 430 views
Filed under: 之语言特性,边走编程 — dutor @ 8:09 pm Comments (0)
August 18, 2009
if/else vs ?: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

	call ___main
	movl $1,-4(%ebp) ; a
	movl $2,-8(%ebp) ; b
	movl -4(%ebp),%eax ;if/else开始
	cmpl -8(%ebp),%eax
	jge L2
	movl -4(%ebp),%eax
	movl %eax,-12(%ebp)
	jmp L3
	.p2align 4,,7
L2:
	movl -8(%ebp),%eax
	movl %eax,-12(%ebp) ; if/else结束
L3:
	movl -8(%ebp),%eax ; ? :开始
	cmpl -4(%ebp),%eax
	jle L4
	movl -4(%ebp),%eax
L4:
	movl %eax,-12(%ebp) ; ? :结束

if/else用了8条指令，?:用了5条，这个差距可不算小了啊！因为，程序里面是要有循环的，多数循环里面会有分支语句，且很多情况下是二分支。
呃……又学到一个单词，ternary：三元。:-)

Tags: ,. 13 views
Filed under: 边走编程 — dutor @ 12:55 pm Comments (0)
August 17, 2009
反转链表小算法 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void reverse(Node * T)
{
	assert(T); //~ 表头非空
	Node* p = T->next, *t;
	if(p)
	{	//~ 将第一个结点，即未来的表尾next域置空
		t = p->next;
		p->next = NULL;
		p = t;
	}
	while(p)
	{	//~ 将余下结点依次插入表头
		t = p->next;
		p->next = T->next;
		T->next = p;
		p = t;
	}
}
Tags: ,. 64 views
Filed under: 之语言特性 — dutor @ 12:39 pm Comments (3)
Page 7 of 16« First...3456789101112...Last »