递归中的改进

在上一篇(一次面试)中, 我用递归实现了输出所有可接受序列的排队方法. 后来, 我意识到, 在递归中, 频繁地申请内存来存储新增加的可接受序列的字符串, 再释放掉这片存储区域的方法是不必要的. 因为在递归中每调用一次新的递归后, 这时的可接受序列的字符串前面部分是一样的, 可以每次调用递归函数都用这块存储区域. 这时我们就不能用strcat()函数来加入新的字符了, 而是要先计算出目前要修改的字符的位置(pstr + (num_of_push_fiftycents * 2 - sum_of_fiftycents_inbox)), 然后直接在这个位置上修改要加入的字符. 改进后的代码如下:



#include 
#include 
#include 
#include 

#define USEMALLOC   0

static unsigned int COUNT = 0;

static void
sale_ticket(int num_of_push_fiftycents, int sum_of_fiftycents_inbox, char *pstr, const int num_of_fiftycents)
{
	/*
	 * 若钱箱内五角钱币为空, 且还有五毛游客排队时, 
	 * 则下次只能接受五毛游客购票
	 */
	if (sum_of_fiftycents_inbox == 0 && num_of_push_fiftycents < num_of_fiftycents) {
#if USEMALLOC
		strcat(pstr, "F");	/* 把"F"加到字符串尾部表示有五角进了售票员的钱箱 */
#else
        *(pstr + (num_of_push_fiftycents * 2 - sum_of_fiftycents_inbox)) = 'F';
#endif
		sale_ticket(num_of_push_fiftycents + 1, 1, pstr, num_of_fiftycents);
	}

	/*
	 * 若钱箱内五毛钱币非空, 且还有五毛游客排队,
	 * 则下次可以接受两种游客的购票请求
	 */
    if (sum_of_fiftycents_inbox > 0 && num_of_push_fiftycents < num_of_fiftycents) {
		/* 情况1: 下一张票卖给1元游客 */
#if USEMALLOC
		strcat(pstr, "T");	/* 把"T"加到字符串尾部表示有1元进了售票员的钱箱 */
#else
        *(pstr + (num_of_push_fiftycents * 2 - sum_of_fiftycents_inbox)) = 'T';
#endif
		sale_ticket(num_of_push_fiftycents, sum_of_fiftycents_inbox - 1, pstr, num_of_fiftycents);

		/* 情况2: 下一张票卖给五毛游客 */
#if USEMALLOC
		strcat(pstr, "F");
#else
        *(pstr + (num_of_push_fiftycents * 2 - sum_of_fiftycents_inbox)) = 'F';
#endif
		sale_ticket(num_of_push_fiftycents + 1, sum_of_fiftycents_inbox + 1, pstr, num_of_fiftycents);
	}

    /* 
     * 排队的只剩下手持一元的游客,
     * 下一张票只能卖给这类游客了
     */
    if (sum_of_fiftycents_inbox > 0 && num_of_push_fiftycents == num_of_fiftycents) {
#if USEMALLOC
        strcat(pstr, "T");
#else
        *(pstr + (num_of_push_fiftycents * 2 - sum_of_fiftycents_inbox)) = 'T';
#endif
        sale_ticket(num_of_push_fiftycents, sum_of_fiftycents_inbox - 1, pstr, num_of_fiftycents);
    }

    /*
	 * 当所有游客都买到票了,
	 * 则输出之前记录的买票顺序字符串
	 */
	if (sum_of_fiftycents_inbox == 0 && num_of_push_fiftycents >= num_of_fiftycents) {
		COUNT++;
		printf("%s\n", pstr);
		return;
	}
}

int
main(int argc, char **argv)
{
    char *prt;
    int max_push;   /* 五毛游客数, 即五毛进钱箱的最大次数 */

    if (argc < 2) {
        fprintf(stderr, "usage: %s num\n", argv[0]);
        exit(0);
    }
    max_push = atoi(argv[1]);
#if 0
    if (max_push <= 0) {
        fprintf(stderr, "usage: %s num\n", argv[0]);
        exit(0);
    }
#endif
    if ((prt = malloc(2 * max_push + 1)) == NULL) {
        perror("main: malloc");
        exit(1);
    }
    memset(prt, 0, 2 * max_push + 1);

    sale_ticket(0, 0, prt, max_push);
    printf("The total number is: %d\n", COUNT);
	free(prt);

    return 0;
}

不过, 频繁的申请, 释放内存并不是这个程序的瓶颈. 修改后的程序运行时间基本是和原来一样的. 原因之一是每一次调用malloc申请到的其实是同一片区域, 没有调用到sbrk()申请过一片大的存储区域. 另一个原因是递归实在是效率低下, 没有留给别的东西当瓶颈的机会.

hmgle's blog

递归中的改进