qsort()性能问题

Question

我成功地对一个结构体数组进行了排序，每个结构体只包含一个字符字符串。然而，对于一个大约有900,000个元素的结构体数组，qsort所需时间比我预期的要长得多（qsort花费大约2分钟来对这个数组进行排序）；这让我觉得我可能忽略了某些东西。

排序是我正在处理的任务中微不足道的一部分，但它独自就完全超过了我程序的时间限制。

以下是我代码中相关的部分：

struct WordsArray //Just a struct thath holds a *char
{
    char word[25];
};

qsort函数中传递的比较函数：

int cmpfunc(const void *a, const void *b)
{
    const struct WordsArray *a1;
    a1 = (WordsArray*)malloc(sizeof(WordsArray));
    const struct WordsArray *b1;
    b1 = (WordsArray*)malloc(sizeof(WordsArray));
    a1 = (struct WordsArray*)a;
    b1 = (struct WordsArray*)b;

    return strcmp(a1->word, b1->word);
}

我的qsort调用：

WordsArray *AllWordsArray;
AllWordsList = (WordsArray*)malloc(sizeof(WordsArray)*ListSize);
qsort(AllWordsList->word, ListSize, sizeof(struct WordsArray), cmpfunc);

感谢您的反馈。

- osalin3

---

在你的比较函数中不要使用malloc！ - Peter G.

你在比较函数中分配了内存。这是不必要的，会减慢程序的速度并导致内存泄漏，因为你从未释放它。查看比较函数并修复它。 - Alex Reynolds

Answer 1

问题出在你的cmpfunc实现上：它比消防栓还快地泄漏内存！你只是分配了(WordsArray*)指针，接着就在下一行把它们覆盖掉了，这样就会创建一个内存泄漏。你只需要去掉malloc即可：

int cmpfunc(const void *a, const void *b) {
    const struct WordsArray *a1 = (struct WordsArray*)a;
    const struct WordsArray *b1 = (struct WordsArray*)b;
    return strcmp(a1->word, b1->word);
}

- Sergey Kalinichenko

---

为什么不直接将a和b转换而不是复制到a1和b1中（编译器可能会这样做）？返回strcmp(((const struct WordsArray*)a)->word,((const struct WordsArray*)b)->word)。 - rcgldr

不需要进行强制转换，毕竟这还是C!;-) - alk

@rcgldr：“为了可读性，我想。” - alk

非常感谢！我在 cmpfunc 上遇到了很大的困难，一旦我能够得到一些有效的东西，我就会继续使用它。至于转换，我会尝试一下。 - osalin3