我在C中有一个循环的,静态分配的缓冲区,我将其用作深度广度优先搜索的队列.我想排队队列中的前N个元素.使用常规qsort()会很容易 - 除了它是一个循环缓冲区,并且前N个元素可能会环绕.当然,我可以编写自己的排序实现,它使用模块化算法并知道如何包装数组,但我一直认为编写排序函数是一个很好的练习,但最好留给库.
我想到了几种方法:
使用单独的线性缓冲区 - 首先从循环缓冲区复制元素,然后应用qsort,然后将它们复制回来.使用额外的缓冲区意味着额外的O(N)空间要求,这使我有了
使用qsort对"top"和"bottom"half进行排序,然后使用其他缓冲区合并它们
与2.相同但是就地进行最终合并(我在就地合并方面没有找到太多内容,但我看到的实现似乎不值得降低空间复杂度)
另一方面,花一个小时考虑如何优雅地避免编写我自己的快速排序,而不是添加那些25(左右)线可能也不是最有效率...
更正:切换DFS和BFS时犯了一个愚蠢的错误(我更喜欢编写DFS,但在这种特殊情况下我必须使用BFS),对不起存在困惑.
进一步描述原始问题:
我正在实施广度优先搜索(对于与十五个难题不同的东西,只是更复杂,在每个状态中有大约O(n ^ 2)个可能的扩展,而不是4).完成了"强力"算法,但它是"愚蠢的" - 在每个点上,它以硬编码的顺序扩展所有有效状态.队列实现为循环缓冲区(unsigned queue [MAXLENGTH]),并将整数索引存储到状态表中.除了两个简单的函数来排队和出列索引之外,它没有封装 - 它只是一个简单的,静态分配的无符号数组.
现在我想添加一些启发式方法.我想要尝试的第一件事是在扩展后对扩展的子状态进行排序("以更好的顺序扩展它们") - 就像我编写一个简单的最好的第一个DFS一样.为此,我想参与队列(代表最近的扩展状态),并使用某种启发式对它们进行排序.我也可以按不同的顺序扩展状态(所以在这种情况下,如果我打破队列的FIFO属性,这并不重要).
我的目标不是实现A*,或者是基于深度优先搜索的算法(我不能扩展所有状态,但如果我不这样做,我将开始在状态空间中出现无限循环问题,所以我'必须使用迭代加深之类的东西).
我认为您需要从问题中退一步并尝试将其作为一个整体来解决 - 半排序循环缓冲区不是存储数据的最佳方式.如果是,那么你已经提交了,你必须编写缓冲区来对元素进行排序 - 这是否意味着偶尔对外部库进行排序,或者在插入元素时进行,我不知道. 但是在一天结束时它会变得很丑陋,因为FIFO和排序缓冲区根本不同.
以前的答案,假设您的排序库具有强大且功能丰富的API(在您的问题中要求,这不需要您编写自己的mod排序或任何东西 - 它取决于支持任意位置数据的库,通常通过回调如果你的排序不支持链表,它就无法解决这个问题):
循环缓冲区已经使用%(mod)算法解决了这个问题.QSort等不关心内存中的位置 - 它们只需要一种以线性方式处理数据的方案.
它们对于链接列表(在内存中不是线性的)也适用于"真实"线性非圆形数组.
因此,如果您有一个包含100个条目的圆形数组,并且您发现需要对前10个进行排序,并且前十个恰好在顶部包裹了一半,那么您将对以下两位信息进行排序:
定位数组项的函数是(x%100)
要分类的项目位于95到105的位置
该函数将sort排序使用的地址转换为真实数组中使用的索引,并且数组环绕的事实是隐藏的,尽管将数组排序超出其边界可能看起来很奇怪,根据定义,圆形数组具有没有界限.%运算符为您处理,您也可以将数组的部分称为1295到1305,只关注它.
具有2 ^ n个元素的数组的加分点.
听起来你正在使用一个排序库,它不能排序除线性数组之外的任何东西 - 因此它不能对链接列表或除了简单排序之外的任何数组进行排序.你真的只有三个选择:
您可以重新编写库以使其更加灵活(即,当您调用它时,您可以为其提供一组用于比较操作和数据访问操作的函数指针)
您可以重新编写数组,以便它以某种方式适合您现有的库
您可以为特定解决方案编写自定义排序.
现在,就我而言,我会重新编写排序代码,因此它更灵活(或复制它并编辑新副本,因此您可以对线性数组进行快速排序,并对非线性数组进行灵活排序)
但实际情况是,现在您的排序库非常简单,您甚至无法告诉它如何访问非线性存储的数据.
如果它很简单,那么应该毫不犹豫地使库本身适应您的特定需求,或者将缓冲区调整到库中.
尝试一个丑陋的kludge,就像以某种方式将你的缓冲区变成一个线性阵列,对它进行排序,然后将其重新放入其中 - 这是一个你将不得不理解和维护的丑陋的kludge.你将"打破"你的先进先出,然后摆弄内脏.
-亚当
京公网安备 11010802040832号 | 京ICP备19059560号-6 