c - qsort 无法对大型字符串数组进行排序

Question

我正在使用 qsort 对大小为 256 的 i 字符串数组进行排序，例如 char *arr = malloc (i * 256) -- 实际上是在一个循环中使用 reallocs 完成的。每个字符串在文本中包含一个数字，我将其用作比较元素:

int                                                               
cmp(const void *a, const void *b)                                               
{                                                                               
  double atime = get_time((char*)a);                                            
  double btime = get_time((char*)b);                                            
  return (atime > btime) - (atime < btime);                                     
}

当 i 较小时，它起作用。对于较大的 i，它无法正确排序数组。 get_time 正在运行。我之前将它与自定义堆排序实现一起使用，效果很好。

我将以下内容添加到 cmp 以检查发生了什么:

fprintf(stderr, "Comparing %f to %f, result: %d.\n", atime, btime, (atime > btime) - (atime < btime));

似乎所有的比较都是正确的，但并不是所有的比较都在进行。 arr 有几个包含 1.something 的字符串，但是我在输出中找不到大于 1 的数字之间的任何比较。 qsort的调用如下:

qsort((void*)arr, i-1, MAX_ROW_LEN, cmp);

它与我过去传递给我的堆排序函数的参数相同，但它不起作用。

Complete code , 和 example file (fails to sort) .

#include <errno.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define MAX_ROW_LEN 256
#define MAX_FILENAME_LEN 256

/* Return the start time of the event or -1 if no time. */
static double
get_time(const char *event)
{
  if (!event || event[0] == '%')
    return -1;
  size_t tok = strcspn(event, " ") + 2;
  double ans = strtod(event + tok, NULL);
  if (!ans)
    return -1;
  return ans;
}

/*static inline*/ int
cmp(const void *a, const void *b)
{
  double atime = get_time((char*)a);
  double btime = get_time((char*)b);
  return (atime > btime) - (atime < btime);
}

int
main(int argc, char **argv)
{
  /* process parameters */
  if (argc < 2) {
    fprintf(stderr, "Supply a file to sort.\n");
    exit(EXIT_FAILURE);
  }
  if (strlen(argv[1]) > MAX_FILENAME_LEN) {
    fprintf(stderr, "Filename too long.\n");
    exit(EXIT_FAILURE);
  }
  /* read the file */
  printf("Now processing %s.\n", argv[1]);
  FILE *f = fopen(argv[1], "r");
  if (!f) {
    fprintf(stderr, "Failed to open out. Errno %d.\n", errno);
    exit(EXIT_FAILURE);
  }
  char *trace = malloc(MAX_ROW_LEN);
  char *header = malloc(MAX_ROW_LEN);
  size_t i = 1, j = 1;
  while (fgets(trace + (i-1)*MAX_ROW_LEN, MAX_ROW_LEN, f)) {
    /* (if we can't get the time, it's part of the header) */
    if (get_time(trace + (i-1)*MAX_ROW_LEN) != -1) {
      trace = realloc((void*)trace, (++i)*MAX_ROW_LEN);
    } else {
      strncpy(header + (j-1)*MAX_ROW_LEN, trace + (i-1)*MAX_ROW_LEN,
          MAX_ROW_LEN);
      header = realloc((void*)header, (++j)*MAX_ROW_LEN);
    }
  }
  if (!feof(f)) {
    fprintf(stderr, "Error reading file. Errno %d.\n", ferror(f));
    exit(EXIT_FAILURE);
  }
  printf("Read %zu lines.\n", i);
  fclose(f);
  /* write the header */
  f = fopen("out_fixed", "w");
  if (!f) {
    fprintf(stderr, "Failed to open out_fixed. Errno %d.\n", errno);
    exit(EXIT_FAILURE);
  }
  for (size_t k = 0; k < j-1; ++k) {
    /* (there is '%' in comments, can't print formatted) */
    fputs((void*)(header + k*MAX_ROW_LEN), f);
  }
  /* sort */
  printf("Started sorting.\n");
  time_t start = time(NULL);
  qsort((void*)trace, i-1, MAX_ROW_LEN, cmp);
  printf("Ended sorting, took %fs.\n", difftime(time(NULL), start));
  /* write the sorted trace */
  printf("Started writting to disk.\n");
  start = time(NULL);
  for (size_t k = 0; k < i-1; ++k) {
    fprintf(f, "%s", trace + k*MAX_ROW_LEN);
  }
  printf("Took %fs.\n", difftime(time(NULL), start));
  /* flush */
  printf("Closing file (fflush)\n");
  start = time(NULL);
  if (fclose(f)) {
    fprintf(stderr, "Failed to close out_fixed. Errno %d.\n", errno);
    exit(EXIT_FAILURE);
  }
  printf("Took %fs.\n", difftime(time(NULL), start));
  exit(EXIT_SUCCESS);
}

Answer 1

我已经测试了您的代码和您的示例输入文件，它似乎工作正常。在你的问题中你说:

... has several strings containing 1.something, however I couldn't find any comparison between numbers greater than 1 in the output.

但是您的示例输入文件中没有这样的行。

鉴于您的输入示例行:

12 0.475183170 rank3 STATE fill_row

This line in get_time is going to skip over any leading digits in your double:

size_t tok = strcspn(event, " ") + 2;

strcspn 返回在找到“针”之前必须读取的字符数，因此在本例中它将返回 2。然后将 2 添加到该数字上，然后将其用作指针偏移量到您的 event 字符串中，这意味着您传递的是指向 .475183170 而不是 0.475183170 的指针。

无论如何，你最好只在这里使用 strchr:

char *tok = strchr(event, ' ');
if (!tok) {
    return -1;
}
double ans = strtod(tok, NULL);

随后的 strtod 将为您跳过前导空格，因此您无需太花哨。