Используйте кучу вместо стека (K & R 5.7) - PullRequest
Новая
       24

Используйте кучу вместо стека (K & R 5.7)

2 голосов
/ 06 января 2010

У меня есть программа, которая сортирует строки ввода лексикографически, и я пришел к этому упражнению в 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);
}

Это то, что хотел автор, или я сделал это неправильно?

Кроме того, измеряя разницу во времени, правильно ли просто запускать часы в начале основного и затем останавливать их после окончания чтения строк и сравнивать время, затрачиваемое? 

#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);
}

Это оригинальный код.

1 Ответ

1 голос
/ 06 января 2010

Трудно сказать, не видя оригинальный код, но выглядит правильно.

Время зависит от того, какой тип часов вы используете. Если все, что вы делаете, это считывает такты с глобальных часов, то этот метод плох Если вы читаете с часов процесса, он будет работать.

edit: вы можете не увидеть большой разницы во времени. Однако попробуйте поместить массив в другую функцию (назовем ее foo ()) и вызвать readlines из этой функции, используя локальный массив в foo (). Вызовите foo () 5000 раз. Попробуйте старый метод с alloc () 5000 раз.

Скорее всего, это приведет к другому времени выполнения, так как alloc () требует системных вызовов, которые являются медленными.

edit: этот псевдо-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();  
}
...