代码之家 › 专栏 › 技术社区 › Tool

使用堆存储而不是堆栈(K&R 5.7)

benchmarking memory-management arrays c

Tool · 技术社区 · 15 年前

我有一个程序可以按字典顺序对输入行进行排序,我在K&R中进行了以下练习:

重写readlines以将行存储在由main提供的数组中,而不是调用alloc来维护存储。这个节目快多少?

这是原始程序,使用 malloc 保持线路的储存。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXLINES 5000

char *lineptr[MAXLINES];

int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);

void qsort(char *lineptr[], int left, int right);

char *alloc(int n);

#define MAXSIZE 10000
int main(int argc, char *argv[])
{
     int nlines;

     if((nlines = readlines(lineptr, MAXLINES)) >= 0) {
          qsort(lineptr, 0, nlines-1);
          writelines(lineptr, nlines);
          getchar();
          return 0;
     } 
     else {
          printf("error: input too big to sort\n");
          getchar();
          return 1;
     }

}


#define MAXLEN 1000
int getline(char *, int);

int readlines(char *lineptr[], int maxlines)
{
    int len, nlines;
    char *p;
    char line[MAXLEN];

    nlines = 0;
    while((len = getline(line, MAXLEN)) > 0)
       if(nlines >= maxlines || (p = alloc(len)) == NULL)
          return -1;
       else {
            line[len-1] = '\0';
            strcpy(p, line);
            lineptr[nlines++] = p;
       }

    return nlines;
}

void writelines(char *lineptr[], int nlines)
{
     while(nlines-- > 0)
         printf("%s\n", *lineptr++);
}

#define MAXALLOC 5000
char allocbuf[MAXALLOC];
char *allocp = allocbuf;

char *alloc(int n)
{
     if(allocbuf + MAXALLOC - allocp >= n) {
        allocp += n;
        return allocp - n;
     }
     else
         return 0;
}

int getline(char s[], int lim)
{
  int c, i;

  for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; i++)
    s[i] = c;                                                         
  if (c == '\n') {
    s[i++] = c;   
  }
  s[i] = '\0';
  return i;
}

void swap(char *v[], int i, int j)
{
     char *temp;

     temp = v[i];
     v[i] = v[j];
     v[j] = temp;
}

void qsort(char *v[], int left, int right) {

    int i, last;

    if(left >= right) 
       return;

    swap(v, left, (left+right)/2);
    last = left;

    for(i = left + 1; i <= right; i++)
      if(strcmp(v[i], v[left]) < 0)
         swap(v, ++last, i);

    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

我是这样编辑的:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXLINES 5000

char *lineptr[MAXLINES];

int readlines(char *lineptr[], int nlines, char buf[]);
void writelines(char *lineptr[], int nlines);

void qsort(char *lineptr[], int left, int right);

#define MAXSIZE 10000
int main(int argc, char *argv[])
{
     int nlines;
     char buf[MAXSIZE];

     if((nlines = readlines(lineptr, MAXLINES, buf)) >= 0) {
          qsort(lineptr, 0, nlines-1);
          writelines(lineptr, nlines);
          getchar();
          return 0;
     } 
     else {
          printf("error: input too big to sort\n");
          getchar();
          return 1;
     }
}

#define MAXLEN 1000
int getline(char *, int);

int readlines(char *lineptr[], int maxlines, char buf[])
{
    int len, nlines;
    char *p = buf;
    char line[MAXLEN];

    nlines = 0;
    while((len = getline(line, MAXLEN)) > 0)
       if(nlines >= maxlines || MAXSIZE + buf - p < len)
          return -1;
       else {
            line[len-1] = '\0';
            strcpy(p, line);
            lineptr[nlines++] = p;
            p+=len;
       }

    return nlines;
}

void writelines(char *lineptr[], int nlines)
{
     while(nlines-- > 0)
         printf("%s\n", *lineptr++);
}

int getline(char s[], int lim)
{
  int c, i;

  for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; i++)
    s[i] = c;                                                         
  if (c == '\n') {
    s[i++] = c;   
  }
  s[i] = '\0';
  return i;
}

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

void qsort(char *v[], int left, int right) {
    int i, last;

    if(left >= right) 
       return;

    swap(v, left, (left+right)/2);
    last = left;

    for(i = left + 1; i <= right; i++)
      if(strcmp(v[i], v[left]) < 0)
         swap(v, ++last, i);

    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

这是作者想要的,还是我做错了?

另外,测量时间差,在主时钟开始时开始计时,在阅读结束后停止计时,并比较所用的时间是否正确?

#包括<stdio.h>
#包括<stdlib.h>
#包括<string.h>

#定义MaxLines 5000

char*lineptr[maxlines];

int readlines(char*lineptr[],int nlines);
void writelines(char*lineptr[],int nlines);

void qsort(char*lineptr[],int-left,int-right);

char*alloc(int n);

#定义最大值10000
int main(int argc,char*argv[])
{
int行;

如果((nlines=readlines(lineptr,maxlines))>=0){
qsort(lineptr,0,nlines-1);
写入行(lineptr,nlines);
GETCHARE();
返回0;
}
否则{
printf(“错误:输入太大,无法排序”);
GETCHARE();
返回1;
}

}


#定义maxlen 1000
int getline(char*,int);

int readlines(char*lineptr[],int maxlines)
{
内线、内线;
字符*P;
字符行[maxlen];

nLe= 0;
同时((len=getline(line,maxlen))>0)
if(nlines>=maxlines(p=alloc(len))=null)
返回-1;
否则{
行[len-1]='\0';
strcpy(p,线);
lineptr[nlines++]=p;
}

返回n行;
}

void writelines(char*lineptr[],int nlines)
{
while(nlines-->0)
printf(“%s\n”,*lineptr++);
}

#定义maxalloc 5000
char allocbuf[maxalloc];
char*allocp=allocbuf;

char*分配(int n)
{
如果(allocbuf+maxalloc-allocp>=n){
AlcP++n;
返回allocp-n;
}
其他的
返回0;
}

int getline(char s[],int lim)
{
In C,I;

对于(i=0;i<lim-1&c=getchar())!=eof&c!='\n';i++)
S[i]=C;
如果(c='\n')。{
S[i++]=C;
}
S [i]=‘0’;
返回我;
}

无效交换(char*v[],int i,int j)
{
字符温度;

温度= v[i];
v[i]=v[j];
v[j]=温度;
}

void qsort(char*v[],int left,int right){

int i,最后;

如果(左>=右)
返回;

交换(V,左,(左+右)/2);
最后=左;

对于(i=左+1;i<=右;i++)
if(strcmp(v[i],v[left])<0)
交换(V,++Last,I);

交换(V,左,后);
qsort(V,左,后-1);
qSort(V,Last+1,右);
}

这是原始代码。

1 回复 | 直到 15 年前

San Jacinto 14 年前

很难说没有看到原始代码,但它看起来是正确的。

对于计时,它取决于您使用的时钟类型。如果您所做的只是从全局时钟中读取时钟滴答声,那么这个方法是错误的。如果您正在读取进程的时钟,那么它将工作。

编辑:你可能看不到很大的时间差异。但是,尝试将数组放入另一个函数(让我们将其命名为foo())中,并使用foo()中的本地数组从该函数调用readlines。调用foo()5000次。使用alloc()5000次尝试旧方法。

这可能会产生不同的运行时间,因为alloc()需要系统调用,而系统调用速度很慢。

编辑:这个伪C将告诉您如何计时动态内存分配与堆栈分配。这很复杂,因为您的进程可能会阻塞,直到系统给它想要的内存,所以您可能需要修补不同的时钟才能得到更好的图像。

您将希望在不进行优化的情况下编译此文件。

void call1()
{
    char* i;
    i = (char*)malloc(1000);
    //we should free(), but this would add timing overhead.
}

void call2()
{
   char x[1000];
}


int main()
 {
   int i=0;

   timer_start();
   for(i = 0; i < 5000; i++)
       call1();
   timer_stop();

   report_time();

   timer_start();
   for(i = 0; i < 5000; i++)
       call2();
    timer_stop();

  report_time();  
}