2

I have an assignment that requires me to sort a heap based C style array of names as they're being read rather than reading them all and then sorting. This involves a lot of shifting the contents of the array by one to allow new names to be inserted. I'm using the code below but it's extremely slow. Is there anything else I could be doing to optimize it without changing the type of storage?

//the data member
string *_storedNames = new string[4000];

//together boundary and index define the range of elements to the right by one
for(int k = p_boundary - 1;k > index;k--)
   _storedNames[k]=_storedNames[k - 1];

EDIT2: As suggested by Cartroo I'm attempting to use memmove with the dynamic data that uses malloc. Currently this shifts the data correctly but once again fails in the deallocation process. Am I missing something?

int numberOfStrings = 10, MAX_STRING_SIZE = 32;

char **array = (char **)malloc(numberOfStrings);

for(int i = 0; i < numberOfStrings; i++)
    array[i] = (char *)malloc(MAX_STRING_SIZE);

array[0] = "hello world",array[2] = "sample";   

    //the range of data to move
int index = 1, boundary = 4;
int sizeToMove = (boundary - index) * sizeof(MAX_STRING_SIZE);

memcpy(&array[index + 1], &array[index], sizeToMove);

free(array);
4

4 回答 4

1

如果您对方法进行了最小的更改，则可以使用该memmove()功能，这可能比您自己的手动版本更快。您不能memcpy()按照一位评论者的建议使用，因为不允许内存区域重叠（如果重叠，则行为未定义）。

如果不更改存储类型或算法，您将无能为力。但是，如果您更改为使用链表，则操作会变得更加高效，尽管您将进行更多的内存分配。如果分配确实是一个问题（除非您使用的是有限的嵌入式系统，否则可能不是），那么池分配器或类似方法可能会有所帮助。

编辑： 重新阅读您的问题，我猜您实际上并没有使用 Heapsort，您只是表示您的数组是在堆上分配的（即 using malloc()）并且您正在执行简单的插入排序。在这种情况下，下面的信息对您没有太大用处，尽管您应该知道插入排序与批量插入相比效率非常低，然后使用更好的排序算法（例如，您可以使用标准库qsort()函数实现的快速排序） ）。如果您只需要最低（或最高）的项目而不是完整的排序顺序，那么 Heapsort 仍然是有用的阅读。

如果您使用的是标准堆排序，那么您根本不需要此操作 - 项目被附加到数组的末尾，然后使用“heapify”操作将它们交换到堆中的正确位置。每次交换只需要一个临时变量来交换两个项目 - 它不需要像您的代码片段中那样洗牌。它确实要求数组中的所有内容都具有相同的大小（固定大小的就地字符串，或者更有可能是指针），但是您的代码似乎已经假设无论如何（并且在标准char数组中使用可变长度的字符串会做一件很奇怪的事情）。

请注意，严格来说，Heapsort 在二叉树上运行。由于您正在处理一个数组，我假设您正在使用一个连续数组的实现，其中索引处的节点的子节点n分别存储在索引2n中2n+1。如果不是这种情况，或者您根本没有使用 Heapsort，您应该更详细地解释您正在尝试做什么以获得更有帮助的答案。

编辑： 以下是对您上面更新的代码的回应。

您在释放期间看到问题的主要原因是如果您践踏了一些内存 - 换句话说，您正在复制超出分配区域大小的内容。这是一件非常糟糕的事情，因为您覆盖了系统用于跟踪您的分配的值并导致各种问题，这些问题通常会导致您的程序崩溃。

首先，您似乎对内存分配和释放的性质有些困惑。你分配一个数组char*，它本身就很好。然后为每个字符串分配数组char，这也很好。但是，您只需调用free()初始数组 - 这还不够。需要调用 tofree()以匹配对 的每次调用malloc()，因此您需要释放分配的每个字符串，然后释放初始数组。

其次，您设置sizeToMove为 的倍数sizeof(MAX_STRING_SIZE)，这几乎肯定不是您想要的。这是用于存储MAX_STRING_SIZE常量的变量的大小。相反，你想要sizeof(char*). 在某些平台上，这些可能是相同的，在这种情况下，一切仍然有效，但不能保证这一点。例如，我希望它可以在 32 位平台上工作（int它们char*的大小相同），但不能在 64 位平台上工作（它们不是）。

第三，您不能只将字符串常量（例如"hello world"）分配给已分配的块——您在这里所做的是替换指针。您需要使用类似strncpy()或memcpy()将字符串复制到分配的块中。我建议snprintf()为方便起见，因为strncpy()它的问题是它不能保证终止结果，但这取决于你。

第四，你仍然在使用memcpy()而不是memmove()在移动物品。

最后，我刚刚看到您的评论，您必须使用newand delete。这些没有等价物realloc()，但如果一切都提前知道，那就没关系了。看起来你想要做的是这样的：

bool addItem(const char *item, char *list[], size_t listSize, size_t listMaxSize)
{
    // Check if list is full.
    if (listSize >= listMaxSize) {
        return false;
    }
    // Insert item inside list.
    for (unsigned int i = 0; i < listSize; ++i) {
        if (strcmp(list[i], item) > 0) {
            memmove(list + i + 1, list + i, sizeof(char*) * (listSize - i));
            list[i] = item;
            return true;
        }
    }
    // Append item to list.
    list[listSize] = item;
    return true;
}

我还没有编译和检查过，所以要注意一个错误之类的错误，但希望你能明白。无论您使用malloc()andfree()还是newand ，此函数都应该可以工作delete，但它假定您已经将字符串复制item到您将保留的已分配缓冲区中，因为它当然只存储一个指针。

请记住，您当然需要listSize在此函数之外更新自己 - 这只是为您将一个项目插入数组中的正确点。如果函数返回true，则将您的副本增加listSize1 - 如果它返回，false则说明您没有分配足够的内存，因此您的项目没有被添加。

另请注意，在 C 和 C++ 中，对于数组list的语法&list[i]和语法是完全等价的 -如果您发现它更容易理解，请list + i在调用中使用第一个。memmove()

于 2013-03-31T23:32:33.770 回答
0

为了最大限度地减少移动数组的成本，您可以将其设为指向字符串的指针数组：

string **_storedNames = new string*[4000];

现在您可以使用memmove（尽管您现在可能会发现逐个元素的复制已经足够快了）。但是您必须自己管理各个字符串的分配和删除，这有点容易出错。

其他建议memmove在您的原始数组上使用的海报似乎没有注意到每个数组元素都是一个string（不是一个string*！）。您不能使用memmove或memcpy在这样的课程上。

于 2013-04-01T08:49:13.640 回答
0

我认为您正在寻找的是堆排序：http ://en.wikipedia.org/wiki/Heapsort#Pseudocode

数组是实现二叉搜索树（即左子节点小于当前节点而右子节点大于当前节点的树）的常用方法。

Heapsort 对指定长度的数组进行排序。在您的情况下，由于数组的大小将“在线”增加，您需要做的就是调用更改传递给 heapsort 的输入大小（即将考虑的元素数量增加 1）。

于 2013-03-31T23:28:58.777 回答
0

由于您的数组已排序并且您不能使用任何其他数据结构，您最好的选择可能是执行二进制搜索，然后将数组向上移动一个以在插入位置释放空间，然后在该位置插入新元素.

于 2013-03-31T23:31:17.003 回答