c - qsort() 性能问题

Question

我成功地对结构数组进行了排序，其中每个结构仅包含一个 char 字符串。然而，我的问题是，对于大约的结构数组。 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);

感谢您的输入。

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