2

我在 C 中有一个循环的、静态分配的缓冲区，我将其用作深度广度优先搜索的队列。我希望对队列中的前 N ​​个元素进行排序。只使用常规的 qsort() 会很容易——除了它是一个循环缓冲区，并且前 N 个元素可能会环绕。当然，我可以编写自己的排序实现，它使用模块化算法并且知道如何环绕数组，但我一直认为编写排序函数是一个很好的练习，但最好留给库。

我想到了几种方法：

  1. 使用单独的线性缓冲区 - 首先从循环缓冲区复制元素，然后应用 qsort，然后将它们复制回来。使用额外的缓冲区意味着额外的 O(N) 空间需求，这让我
    • 使用 qsort 对“顶部”和“底部”两半进行排序，然后使用附加缓冲区将它们合并
    • 与 2 相同。但在原地进行最终合并（我在原地合并方面没有发现太多，但我看到的实现似乎不值得降低空间复杂度）

另一方面，花一个小时思考如何优雅地避免编写我自己的快速排序，而不是添加那 25 行（左右）行可能也不是最有效率的......

更正：在切换 DFS 和 BFS 时犯了一个愚蠢的错误（我更喜欢编写 DFS，但在这种特殊情况下我必须使用 BFS），抱歉造成混淆。

原问题的进一步描述：

我正在实施广度优先搜索（对于类似于十五个难题的东西，只是更复杂，在每个状态下大约有 O(n^2) 个可能的扩展，而不是 4 个）。“蛮力”算法已经完成，但它是“愚蠢的”——在每一点，它以硬编码的顺序扩展所有有效状态。队列实现为循环缓冲区（无符号队列[MAXLENGTH]），它将整数索引存储到状态表中。除了对索引进行排队和出队的两个简单函数外，它没有封装——它只是一个简单的、静态分配的无符号数组。

现在我想添加一些启发式方法。我想尝试的第一件事是在展开后对展开的子状态进行排序（“以更好的顺序展开它们”）——就像我正在编写一个简单的最佳优先 DFS 一样。为此，我想加入队列（代表最近的扩展状态），并使用某种启发式对它们进行排序。我还可以以不同的顺序扩展状态（因此在这种情况下，如果我打破队列的 FIFO 属性并不重要）。

我的目标不是实现A*或基于深度优先搜索的算法（我无法扩展所有状态，但如果我不这样做，我将开始遇到状态空间中无限循环的问题，所以我必须使用诸如迭代深化之类的东西）。

4

6 回答 6

5

我认为您需要从问题中退后一步并尝试将其作为一个整体来解决 - 很有可能半排序的循环缓冲区不是存储数据的最佳方式。如果是，那么您已经提交了，您将不得不编写缓冲区来对元素进行排序——这是否意味着偶尔使用外部库执行排序，或者在插入元素时进行排序，我不知道。 但归根结底，它会变得丑陋，因为 FIFO 和排序缓冲区根本不同。

上一个答案，假设您的排序库具有强大且功能丰富的 API（根据您的问题的要求，这不需要您编写自己的 mod 排序或任何东西 - 它取决于支持任意定位数据的库，通常通过回调函数。如果你的排序不支持链表，它不能处理这个）：

循环缓冲区已经使用 % (mod) 算法解决了这个问题。QSort 等不关心内存中的位置——它们只需要一个方案来以线性方式寻址数据。

它们适用于链表（在内存中不是线性的），就像它们适用于“真正的”线性非循环数组一样。

因此，如果您有一个包含 100 个条目的循环数组，并且您发现您需要对前 10 个进行排序，而前 10 个恰好在顶部折叠成一半，那么您需要向排序提供以下两位信息：

  • 定位数组项的函数是 (x % 100)
  • 要排序的项目在位置 95 到 105

该函数会将排序使用的地址转换为实际数组中使用的索引，并且数组环绕的事实是隐藏的，尽管对超出其边界的数组进行排序可能看起来很奇怪，根据定义，循环数组具有没有界限。% 运算符会为您处理，您也可以将数组的部分称为 1295 到 1305 以了解它所关心的一切。

拥有一个包含 2^n 个元素的数组的奖励积分。

额外的考虑点：

在我看来，您使用的排序库无法对线性数组以外的任何内容进行排序 - 因此它无法对链表或具有简单排序以外的任何数组进行排序。你真的只有三个选择：

  • 您可以重新编写库以使其更灵活（即，当您调用它时，您会给它一组函数指针，用于比较操作和数据访问操作）
  • 您可以重写您的数组，使其以某种方式适合您现有的库
  • 您可以为您的特定解决方案编写自定义排序。

现在，就我而言，我将重新编写排序代码，使其更灵活（或复制它并编辑新副本，以便您拥有对线性数组快速的排序，以及对非线性数组灵活的排序）

但现实情况是，现在您的排序库非常简单，您甚至无法告诉它如何访问非线性存储的数据。

如果就这么简单，那么应该毫不犹豫地根据您的特定需求调整库本身，或者调整您的缓冲区以适应库。

尝试一个丑陋的杂物，例如以某种方式将您的缓冲区变成一个线性数组，对其进行排序，然后将其放回原处就是这样 - 一个丑陋的杂物，您以后必须理解和维护。您将“闯入”您的 FIFO 并摆弄内脏。

-亚当

于 2008-11-11T17:11:37.283 回答
3

我没有看到您在 c 中要求的解决方案。您可能会考虑以下想法之一：

  • 如果您可以访问libc's的源代码qsort()，则可以复制它并简单地将所有数组访问和索引代码替换为适当通用的等效代码。这为您提供了一些适度的保证，即下级排序是有效的并且几乎没有错误。当然，对于引入自己的错误的风险没有帮助。大 O 喜欢这个系统qsort，但可能有一个更差的乘数。

  • 如果要排序的区域与缓冲区的大小相比较小，则可以使用直接线性排序，使用测试换行保护调用并执行复制到线性缓冲区排序然后-仅在需要时复制回例程。O(n)在使守卫绊倒的情况下引入额外的操作（对于n要排序的区域的大小），这使得平均O(n^2/N) < O(n).

我看到 C++ 不适合您。::sigh:: 我会把它留在这里以防其他人可以使用它。

  • 如果 C++ 是一个选项，您可以（如果需要，子类化缓冲区并）重载[]运算符以使标准排序算法工作。同样，应该像带有乘数惩罚的标准排序一样工作。
于 2008-11-11T18:24:01.070 回答
2

也许可以调整优先队列来解决您的问题。

于 2008-11-11T17:22:59.837 回答
2

您可以旋转循环队列，直到有问题的子集不再环绕。然后只需将该子集传递给qsort正常。如果您需要频繁排序或数组元素大小非常大，这可能会很昂贵。但是，如果您的数组元素只是指向其他对象的指针，那么旋转队列可能就足够快了。事实上，如果它们只是指针，那么您的第一种方法也可能足够快：制作子集的单独线性副本，对其进行排序，然后将结果写回。

于 2008-11-11T18:20:39.627 回答
1

你知道关于优化的规则吗？你可以谷歌他们（你会找到几个版本，但他们都说几乎一样的东西，不要）。

听起来您在没有测试的情况下进行优化。这是一个巨大的禁忌。另一方面，您使用的是直接 C，因此您可能在需要一定程度注意速度的受限平台上，所以我希望您需要跳过前两条规则，因为我假设您别无选择：

优化规则：

  1. 不要优化。

  2. 如果您知道自己在做什么，请参阅规则 #1

您可以转到更高级的规则：

优化规则（续）：

  1. 如果您的规范需要一定的性能水平，请编写未优化的代码并编写测试以查看它是否符合该规范。如果它满足它，你就完成了。在达到这一点之前，切勿编写考虑性能的代码。

  2. 如果您完成了第 3 步，但您的代码不符合规范，请重新编码，将原始“最明显”的代码保留在其中作为注释并重新测试。如果不符合要求，就扔掉，使用未优化的代码。

  3. 如果您的改进使测试通过，请确保测试保留在代码库中并重新运行，并且您的原始代码作为注释保留在那里。

注意：那应该是 3. 4. 5. 有些事情搞砸了——我什至没有使用任何标记。

好的，所以最后——我不是在说这个，因为我在某处读过它。我花了几天时间试图解开其他人编码的一些可怕的混乱，因为它是“优化的”——真正有趣的部分是，十分之九，编译器可以比他们更好地优化它。

我意识到有时您需要优化，我所说的只是在未优化的情况下编写它，对其进行测试和重新编码。它真的不会花费你太多时间——甚至可能使编写优化代码更容易。

我发布这篇文章的唯一原因是因为您写的几乎每一行都与性能有关，而且我担心下一个看到您的代码的人会像我一样是个可怜虫。

于 2008-11-11T19:09:01.027 回答
0

像这里这样的例子怎么样。这个例子可以轻松地对零件或任何您想要的东西进行排序，而无需重新定义大量额外的内存。它只需要两个指针，一个状态位和一个用于 for 循环的计数器。

#define _PRINT_PROGRESS
#define N 10
BYTE buff[N]={4,5,2,1,3,5,8,6,4,3};
BYTE *a = buff;
BYTE *b = buff;
BYTE changed = 0;
int main(void)
{
    BYTE n=0;
    do
    {
        b++;
        changed = 0;
        for(n=0;n<(N-1);n++)
        {
            if(*a > *b)
            {
                *a ^= *b;
                *b ^= *a;
                *a ^= *b;
                changed = 1;
            }
            a++;
            b++;
        }
        a = buff;
        b = buff;
#ifdef _PRINT_PROGRESS
        for(n=0;n<N;n++)
            printf("%d",buff[n]);
        printf("\n");
    }
#endif
    while(changed);
    system( "pause" );
}
于 2008-11-13T22:32:31.590 回答