请教一道算法题

Andrew007

wengjn 发表于 2021-3-19 04:37
circular queue?

是的，取完的位置要重复使用。

funmastermike

本帖最后由 wengjn 于 2021-3-18 13:20 编辑

Andrew007 发表于 2021-3-18 12:38
是的，取完的位置要重复使用。

谢谢
那算常规medium题吧

应该是时刻注意track front, rear pointer 看看什么时候full拉啥得

class HelloWorld {
static void Main() {
CircularQueue q = new CircularQueue(3);
q.Enqueue(11);
q.Enqueue(12);
q.Enqueue(13);
var test = q.Dequeue();
Console.WriteLine(test);
Console.WriteLine(q.Dequeue());
q.Enqueue(14);
q.Enqueue(15);
q.Enqueue(16);
Console.WriteLine(q.Dequeue());
Console.WriteLine(q.Dequeue());
Console.WriteLine(q.Dequeue());
Console.WriteLine(q.Dequeue());
}
}
public class CircularQueue {
private int size;
private int front;
private int rear;
private int[] data;
public CircularQueue(int capacity) {
size = capacity;
front = -1;
rear = -1;
data = new int[size];
}
public void Enqueue(int val) {
// if the queue is full
if ((front == 0 && rear == size-1) || (rear == front-1)) {
Console.WriteLine("queue full, add failed.");
} else if (front == -1) {
// empty queue
front = 0;
rear = 0;
data[rear] = val;
} else if (rear == size-1) {
rear = 0;
data[rear] = val;
} else {
rear++;
data[rear] = val;
}
}
public int Dequeue() {
if (front == -1) {
// empty queue
Console.WriteLine("queue empty, dequeue failed.");
return -1;
}
int val = data[front];
if (front == rear) {
// only one item in the queue
front = rear = -1;
} else if (front == size-1) {
front = 0;
} else {
front++;
}
return val;
}
}

复制代码

MareBone

wengjn 发表于 2021-3-19 05:04
谢谢
那算常规medium题吧

这样只有一个queue。题目要求是两个queue

magicsets

可以把4MB分成1024个4kB的内存块，然后以4kB内存块为单位进行动态分配与释放。

那么对于任一个Queue来说，它最“浪费”的情况就是首尾两个内存块为空，也就是8kB，只有 4MB的 0.2% —— 这种情况下我们可以认为内存是被高效利用的。

另一方面的考虑是动态内存分配的额外开销，注意到一个int类型是4 bytes，那么当我们每处理4kB / 4 bytes = 1024个元素的时候才会有一次内存分配（内存分配其实本来就是O(1)) 的额外开销，那么平摊后可以忽略不计 —— 也就是说，使用4kB内存块的方法性能应该是和一开始就开个足够大的数组不需要resize的性能没什么差别。

参考代码：

#include <cstdint>
#include <iostream>
#include <memory>
#include <stack>
#include <stdexcept>
#include <utility>
// CPU分支预测hint
#define UNLIKELY(x) __builtin_expect(!!(x), 0)
#define CHECK(cond) \
if (UNLIKELY(!(cond))) { throw std::runtime_error("CHECK failed: " #cond); }
// 设置一个数据块为4kB
static constexpr int64_t kBlockSize = 4096;
// 用于管理内存池的抽象
class Arena {
public:
explicit Arena(int64_t size)
: memory_buffer_(std::make_unique<char[]>(size)) {
// size要求是4kB的整数倍
CHECK(size % kBlockSize == 0);
// 如果size是4MB的话，那么就有4MB / 4kB = 1024个内存块
// 初始化只有一次，并且时间可以忽略不计
// 更理想的是bitmap来记录可用块信息，那么只需要初始化1024 bits = 128 bytes
for (int64_t i = size / kBlockSize - 1; i >= 0; --i) {
available_blocks_.push(i);
}
}
// 分配一个数据块
template <typename BlockType>
std::unique_ptr<BlockType> Allocate() {
CHECK(!available_blocks_.empty());
const int64_t block_id = available_blocks_.top();
std::cout << "Allocate block " << block_id << "\n";
available_blocks_.pop();
return std::make_unique<BlockType>(
memory_buffer_.get() + block_id * kBlockSize, block_id, this);
}
// 回收一个数据块
void Release(int64_t block_id) {
std::cout << "Release block " << block_id << "\n";
available_blocks_.push(block_id);
}
private:
// 总体的内存块 (例如4MB)
const std::unique_ptr<char[]> memory_buffer_;
// 理想的实现是用bitmap来维护可用内存块，不过代码量比较大
std::stack<int64_t> available_blocks_;
};
// 4kB数据块的封装
class Block {
public:
Block(void* block_data, int64_t block_id, Arena* arena)
: block_data_(block_data), block_id_(block_id), arena_(arena) {}
// RAII机制回收数据块
~Block() { arena_->Release(block_id_); }
// 读取某个位置的数据
template <typename T>
T Get(int64_t index) const {
return static_cast<const T*>(block_data_)[index];
}
// 设置某个位置的数据
template <typename T>
void Set(int64_t index, T value) const {
static_cast<T*>(block_data_)[index] = value;
}
std::unique_ptr<Block>& next_block() { return next_block_; }
private:
// 每个数据块需要额外32 bytes的内存指针 + block id + next pointer
// 这点开销比起4kB不到1%所以可以忽略不计
void* block_data_;
int64_t block_id_;
Arena* arena_;
std::unique_ptr<Block> next_block_;
};
// Queue的实现
template <typename T>
class Queue {
public:
explicit Queue(Arena* arena)
: arena_(arena),
block_capacity_(kBlockSize / sizeof(T)) {
CHECK(block_capacity_ > 0);
}
// 往队列头添加一个新元素
void PushFront(T value) {
if (UNLIKELY(front_ == nullptr)) {
// Block链表为空
back_ = arena_->Allocate<Block>();
front_ = back_.get();
} else if (UNLIKELY(head_exclusive_ >= block_capacity_)) {
// front_已经满了
front_->next_block() = arena_->Allocate<Block>();
front_ = front_->next_block().get();
head_exclusive_ = 0;
}
++size_;
front_->Set(head_exclusive_++, value);
}
// 从队列尾取出一个元素
T PopBack() {
if (UNLIKELY(back_.get() == front_)) {
// 链表里只有一个数据块的情况
CHECK(tail_inclusive_ < head_exclusive_);
} else if (UNLIKELY(tail_inclusive_ >= block_capacity_)) {
// back_没有剩余元素了，对其回收并移动到下一个数据块
back_ = std::move(back_->next_block());
tail_inclusive_ = 0;
CHECK(back_ != nullptr);
}
--size_;
return back_->Get<T>(tail_inclusive_++);
}
size_t size() const { return size_; }
bool IsEmpty() const { return size_ == 0; }
private:
Arena* const arena_;
const int64_t block_capacity_;
int64_t size_ = 0;
// 这里back_是链表头，但是是队列尾
std::unique_ptr<Block> back_;
int64_t tail_inclusive_ = 0;
// front_是链表尾，但是是队列头
Block* front_ = nullptr;
int64_t head_exclusive_ = 0;
};
// 测试代码
int main(int argc, char* argv[]) {
Arena arena(/*size=*/4 * 1024 * 1024);
Queue<int> a(&arena);
Queue<int64_t> b(&arena);
for (int i = 1; i <= 10000; ++i) {
a.PushFront(i);
b.PushFront(i);
}
while (!a.IsEmpty()) {
b.PushFront(a.PopBack() * 10);
}
int64_t b_sum = 0;
while (!b.IsEmpty()) {
b_sum += b.PopBack();
}
std::cout << "b sum = " << b_sum << "\n";
return 0;
}

复制代码

funmastermike

magicsets 发表于 2021-3-18 22:36
可以把4MB分成1024个4kB的内存块，然后以4kB内存块为单位进行动态分配与释放。

那么对于任一个Queue来说 ...

高手啊赞谢谢了

1m3fdstring

JAVA还没碰到要我们处理内存的问题，因为有垃圾回收器。

果然是c++和c#才会有的问题，长见识了

[数组] 请教一道算法题

评分

评分

浏览过的版块