问题标签 [circular-buffer]

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

我想到了几种方法：

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

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

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

原问题的进一步描述：

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

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

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

我想知道是否有比这更简单（单一）的方法来计算循环缓冲区中的剩余空间？

我不是要求任何人为我做这个作业，但我提出它是因为它是对 C# 和线程的非常好的实用介绍，但同时我觉得它可能有点太简单了。

这真的是教授线程的最好方法吗？在本练习中“丢失”了哪些关键线程概念，第一次使用线程的新程序员可能无法观察到什么？

我有很多关于线程的理论知识，但过去我自己不需要做很多，写它时有人对我有什么警告吗？

这是原始作业的链接

这是目标文本：

1) 创建一个线程安全的通用循环队列类并创建一个 GUI 来使用它（参见下一节）。在这种情况下，线程安全意味着更改队列内容的每个操作（方法）一次只能由一个线程执行，以避免数据损坏。循环队列被实现为一个固定大小的数组，其中队列的开始和结束是数组中的索引。随着队列填满，队列的开头和结尾将随着元素的添加而转移到更高的值，并最终环绕到数组中的第一个索引以重用内存。如果操作无效，此类还应向调用者抛出异常（如下指定）。

2) 创建一个 GUI 以生产者-消费者的方式控制两个线程。GUI 将能够启动和启动和停止生产者和消费者线程，并控制它们修改 GenericCircularQueue 的速率。

我需要一个固定大小（在创建时可以在运行时选择，而不是在编译时选择）循环缓冲区，它可以保存任何类型的对象，并且它需要非常高性能。我认为不会出现资源争用问题，因为尽管它是在多任务嵌入式环境中，但它是一个协作环境，因此任务本身可以管理它。

我最初的想法是在缓冲区中存储一个简单的结构，该结构将包含类型（简单枚举/定义）和一个指向有效负载的 void 指针，但我希望它尽可能快，所以我愿意接受涉及绕过的建议堆。

实际上，我很高兴绕过任何标准库以获得原始速度 - 从我所看到的代码来看，它并没有针对 CPU 进行大量优化：看起来他们只是为之类的东西编译了 C 代码，strcpy()没有手工编码组装。

任何代码或想法将不胜感激。所需的操作是：

• 创建具有特定大小的缓冲区。
• 放在尾部。
• 从头上得到。
• 返回计数。
• 删除一个缓冲区。

在Ring Buffer 的 Wikipedia entry中，有一个示例代码显示了UNIX系统的一个 hack，其中一块内存的相邻虚拟内存被映射到相同的物理内存，从而实现了一个不需要任何memcpy等的环形缓冲区。我想知道如果有办法在Windows中进行类似的操作？

谢谢，弗雷泽

我需要一个 CircularBuffer IDictionary。谁能给我指出一个好的开源实现。

因此，具有最大容量的 IDictionary，例如配置为 100 个项目，当添加项目 101 时，会从字典中弹出/删除原始第一个项目，从而确保项目计数永远不会超过 100。

谢谢

有人已经在 J​​avaScript 中实现了循环缓冲区吗？如果没有指针，您将如何做到这一点？

我的主要目的是拥有一个可用于传输的通用数据缓冲区。

我正在考虑 XCopy 所做的事情。

是否有一些已经做出来的东西或者一个可以效仿的好例子？

我需要将不同长度的项目存储在闪存芯片的循环队列中。每个项目都有它的封装，所以我可以弄清楚它有多大以及下一个项目从哪里开始。当缓冲区中有足够的项目时，它将换行到开头。

将循环队列存储在闪存芯片中的好方法是什么？

我想存储数以万计的物品的可能性。所以从头开始读取到缓冲区的末尾并不理想，因为搜索到末尾需要时间。

另外，因为它是循环的，我需要能够区分第一个项目和最后一个项目。

最后一个问题是它存储在闪存中，因此擦除每个块既耗时又只能为每个块执行一定次数。

我正在用 Java 实现事件流上的滑动窗口。所以我想要一个允许我执行以下操作的数据结构：

1. 当新事件发生时添加到数据结构的末尾；

2. 处理旧事件时从数据结构的开头删除；

3. 获得对数据结构元素的标准随机访问（size(), ）；get(i)一般来说，典型的列表“读取”操作；

4. 对上述所有操作都是有效的；

5. 是无界的。

不需要其他访问权限。并且不需要线程安全。

我目前正在使用ArrayList执行此操作，以启动和运行。但我想要更有效的东西；remove(0)方法 (2. above)对于ArrayList.

数字 1. 和 2. 是标准的Queue式操作。但是，QueueJDK 中的实现（例如ArrayDeque）不允许get(i)in 3.

所以，我想知道是否有任何库有这样的实现，并且适合商业用途。

如果没有，我想我会求助于自己写...