我在C中有一个循环的,静态分配的缓冲区,我将其用作深度广度优先搜索的队列.我想排队队列中的前N个元素.使用常规qsort()会很容易 - 除了它是一个循环缓冲区,并且前N个元素可能会环绕.当然,我可以编写自己的排序实现,它使用模块化算法并知道如何包装数组,但我一直认为编写排序函数是一个很好的练习,但最好留给库.
我想到了几种方法:
另一方面,花一个小时考虑如何优雅地避免编写我自己的快速排序,而不是添加那些25(左右)线可能也不是最有效率...
更正:切换DFS和BFS时犯了一个愚蠢的错误(我更喜欢编写DFS,但在这种特殊情况下我必须使用BFS),对不起存在困惑.
进一步描述原始问题:
我正在实施广度优先搜索(对于与十五个难题不同的东西,只是更复杂,在每个状态中有大约O(n ^ 2)个可能的扩展,而不是4).完成了"强力"算法,但它是"愚蠢的" - 在每个点上,它以硬编码的顺序扩展所有有效状态.队列实现为循环缓冲区(unsigned queue [MAXLENGTH]),并将整数索引存储到状态表中.除了两个简单的函数来排队和出列索引之外,它没有封装 - 它只是一个简单的,静态分配的无符号数组.
现在我想添加一些启发式方法.我想要尝试的第一件事是在扩展后对扩展的子状态进行排序("以更好的顺序扩展它们") - 就像我编写一个简单的最好的第一个DFS一样.为此,我想参与队列(代表最近的扩展状态),并使用某种启发式对它们进行排序.我也可以按不同的顺序扩展状态(所以在这种情况下,如果我打破队列的FIFO属性,这并不重要).
我的目标不是实现A*,或者是基于深度优先搜索的算法(我不能扩展所有状态,但如果我不这样做,我将开始在状态空间中出现无限循环问题,所以我'必须使用迭代加深之类的东西).
我有一个Vec循环缓冲区的分配.假设缓冲区已满,因此分配中没有元素不在循环缓冲区中.我现在想把那个循环缓冲区变成一个Vec循环缓冲区的第一个元素也是第一个元素的地方Vec.作为一个例子,我有这个(分配)功能:
fn normalize(tail: usize, buf: Vec<usize>) -> Vec<usize> {
let n = buf.len();
buf[tail..n]
.iter()
.chain(buf[0..tail].iter())
.cloned()
.collect()
}
显然,这也可以在不分配任何东西的情况下完成,因为我们已经有足够大的分配,并且我们有一个swap操作来交换分配的任意元素.
fn normalize(tail: usize, mut buf: Vec<usize>) -> Vec<usize> {
for _ in 0..tail {
for i in 0..(buf.len() - 1) {
buf.swap(i, i + 1);
}
}
buf
}
遗憾的是,这需要buf.len() * tail交换操作.我很确定它可以在buf.len() + tail交换操作中完成.对于具体的价值tail和buf.len()我已经能够找出解决方案,但我不知道如何在一般情况下这样做.
我的递归部分解决方案可以在行动中看到.
所以这就是我的清单.
[0], [1], [2], [3], [4]
我希望能够遍历这些 - 但这里的诀窍是我想从一个偏移开始然后循环回到那个偏移量？
恩.
[0], [1], [2], [3], [4]
o-->
//Start at offset 1 then get 2, 3, 4 then loop back around to zero
EX2.
[0], [1], [2], [3], [4]
o-->
//Start at offset 3 then get 4, then loop back around to zero, then 1, 2
我考虑使用常规List<T>并尝试将此概念实现为for循环但我不确定我是否想要这样做,如果他们这样做更简洁的方式.
基本上不要从0开始并循环回到开始并通过元素返回到偏移量.
什么数据结构最适合存储循环中的对象？例如,我有一个对象列表,A,B,C,D,E,我需要循环处理它们,A-> B-> C-> D-> E,然后是E-> A-> B- > C-> d -...
处理这种情况的最佳方法是什么？谢谢.我正在考虑一个循环数组,但根据维基百科,循环数组最好用于实现一个队列.
我正在寻找一个允许在磁盘上获得循环缓冲区的库.
在Boost中有类似的东西,但它是一个基于内存的容器:circular_buffer.
我有2个进程:一个生产者和"消费者",它仍然将值保留在缓冲区中,它们将被覆盖.
但让消费者跟踪是一个问题.当缓冲区已满并且值被覆盖时,指向索引0的值是刚刚覆盖的值之前的值(即下一个最旧的值),刚刚插入的值是最后一个索引,移动所有值之间.
cb.push_back(0)
cb.push_back(1)
cb.push_back(2)
consumer reads to cb[1], cb[2] should == 2 when next read
cb.push_back(3)
cb[2] now == 1 effectively reading the old value
有趣的是在循环缓冲区迭代器也保持相同的值,即使在缓冲开始被改写,并除非阅读当你达到这样的工作好吗end()迭代器,它会永远等于end()甚至将更多的值之后迭代器,所以那么你必须std::prev(iter, 1)经过你已经完成了消费,然后当你插入更多的值后再次阅读,std::next(iter, 1)这样你就不会读取你已经读过的值.
下午好 ！
我正在尝试制作某种圆形堆栈。它应该像一个普通的 LIFO 堆栈，但没有明显的限制。它应该消除或跳过当时引入的第一个元素，而不是达到最大容量！
例如：
假设我们有一个包含 3 个元素的堆栈：stack[3]
我们通过将 3 个元素“推入”内部来填充它：push[a], push[b], push[c]。
但随后我们需要添加第四个和第五个元素：push[d], push[e]。
标准堆栈会说堆栈已达到极限，无法添加更多元素。
但我想要一个循环堆栈，它将消除或跳过aand b，记住c，dande并输出e，dand c；
该项目是在 ESP32 上的 PlatformIO 中完成的，因此我无法访问 C++ STL，即使可以访问，我也认为仅为 1 个堆栈编译这么大的库是没有意义的。即使曾经有一段时间我认为我应该编译一个类似的库来让我访问stackor deque，但那个时候已经过去了，因为现在我感觉自己像一个无法解决数学问题的白痴。这已经困扰我一个多星期了。
我在网上找到的只是以下 FIFO 循环缓冲区：
class circular_buffer {
public:
explicit circular_buffer(size_t size) :
buf_(std::unique_ptr<T[]>(new T[size])),
max_size_(size)
{
}
void put(T item)
{
std::lock_guard<std::mutex> lock(mutex_);
buf_[head_] = item;
if(full_) {
tail_ …我正在使用'TPCircularBuffer'类来创建一个循环缓冲区对象,来自这个网站.这是我目前的代码:
TPCircularBufferRecord bufferRecord; //1
TPCircularBufferInit(&bufferRecord, kBufferLength); //2
第1行工作正常,这意味着链接器已找到该类的.cpp和.h文件.但是,第2行没有编译,错误如下:
Undefined symbols:
"TPCircularBufferInit(TPCircularBufferRecord*, int)", referenced from:
StereoEffect3::StereoEffect3(ComponentInstanceRecord*)in StereoEffect3-1DB483EC8D75827.o
StereoEffect3::StereoEffect3(ComponentInstanceRecord*)in StereoEffect3-1DB483EC8D75827.o
ld: symbol(s) not found
collect2: ld returned 1 exit status
我不认为这是原始源代码的问题,但无论如何我都会在这里包含它: TPCircularBuffer.c
有谁知道为什么链接器/编译器找不到函数TPCircularBufferInit？TPCircularBufferInit函数如下:
inline void TPCircularBufferInit(TPCircularBufferRecord *record, int length) {
record->head = record->tail = record->fillCount = 0;
record->length = length;
}
我很确定我正在将正确类型的参数传递给它......
我在用户空间中搜索C中的ringbuffer实现,所以我可以在我的库中使用它.
因为我需要一个铃声缓冲器
我搜索了一段时间,并记得我在内核模式中使用wait_event_interruptible&wake_up_interruptible做了类似的事情.
但是在用户空间中使用了什么,所以我可以搜索与该方法结合的ringbuffer？我不想重新发明轮子 - 周围有许多环形缓冲解决方案.
在此先感谢并亲切的问候!
编辑:
似乎也许pthread_cond_wait可能相当于wait_event_interruptible.