请教一道算法题

昨天面了一道题，感觉自己可能理解有问题，或者是没有问清楚，到现在也没有想清楚该怎么实现，请教各位大佬。

给你一个固定大小的memory buffer，比如4MB，让实现2个动态增长的Queue. 需要O(1) 实现 insert 和 read， 也就是写入和取出. 只能实现int array，要保证空间充分使用。
我当时给的solution。
1: 建int array，存取数据，需要时，然后动态扩容。面试官说这个空间利用率可能不高。
2: 建一个大的array，第一个queue从头存取，第二个queue从尾存取，分布用两个pointer来维护存存的位置，然后跑例子的时候，有bug，面试官也否定了这个方法。

不知道有没有其他的方法可以解决，或者我可能miss掉了一些重要的点。 谢谢。

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

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

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

参考代码：

1. #include <cstdint>
   
2. #include <iostream>
   
3. #include <memory>
   
4. #include <stack>
   
5. #include <stdexcept>
   
6. #include <utility>
   
7. 
   
8. // CPU分支预测hint
   
9. #define UNLIKELY(x) __builtin_expect(!!(x), 0)
   
10. 
    
11. #define CHECK(cond) \
    
12.   if (UNLIKELY(!(cond))) { throw std::runtime_error("CHECK failed: " #cond); }
    
13. 
    
14. // 设置一个数据块为4kB
    
15. static constexpr int64_t kBlockSize = 4096;
    
16. 
    
17. // 用于管理内存池的抽象
    
18. class Arena {
    
19. public:
    
20.   explicit Arena(int64_t size)
    
21.       : memory_buffer_(std::make_unique<char[]>(size)) {
    
22.     // size要求是4kB的整数倍
    
23.     CHECK(size % kBlockSize == 0);
    
24.     // 如果size是4MB的话，那么就有4MB / 4kB = 1024个内存块
    
25.     // 初始化只有一次，并且时间可以忽略不计
    
26.     // 更理想的是bitmap来记录可用块信息，那么只需要初始化1024 bits = 128 bytes
    
27.     for (int64_t i = size / kBlockSize - 1; i >= 0; --i) {
    
28.       available_blocks_.push(i);
    
29.     }
    
30.   }
    
31. 
    
32.   // 分配一个数据块
    
33.   template <typename BlockType>
    
34.   std::unique_ptr<BlockType> Allocate() {
    
35.     CHECK(!available_blocks_.empty());
    
36.     const int64_t block_id = available_blocks_.top();
    
37.     std::cout << "Allocate block " << block_id << "\n";
    
38.     available_blocks_.pop();
    
39.     return std::make_unique<BlockType>(
    
40.         memory_buffer_.get() + block_id * kBlockSize, block_id, this);
    
41.   }
    
42. 
    
43.   // 回收一个数据块
    
44.   void Release(int64_t block_id) {
    
45.     std::cout << "Release block " << block_id << "\n";
    
46.     available_blocks_.push(block_id);
    
47.   }
    
48. 
    
49. private:
    
50.   // 总体的内存块 (例如4MB)
    
51.   const std::unique_ptr<char[]> memory_buffer_;
    
52. 
    
53.   // 理想的实现是用bitmap来维护可用内存块，不过代码量比较大
    
54.   std::stack<int64_t> available_blocks_;
    
55. };
    
56. 
    
57. // 4kB数据块的封装
    
58. class Block {
    
59. public:
    
60.   Block(void* block_data, int64_t block_id, Arena* arena)
    
61.       : block_data_(block_data), block_id_(block_id), arena_(arena) {}
    
62. 
    
63.   // RAII机制回收数据块
    
64.   ~Block() { arena_->Release(block_id_); }
    
65. 
    
66.   // 读取某个位置的数据
    
67.   template <typename T>
    
68.   T Get(int64_t index) const {
    
69.     return static_cast<const T*>(block_data_)[index];
    
70.   }
    
71. 
    
72.   // 设置某个位置的数据
    
73.   template <typename T>
    
74.   void Set(int64_t index, T value) const {
    
75.     static_cast<T*>(block_data_)[index] = value;
    
76.   }
    
77. 
    
78.   std::unique_ptr<Block>& next_block() { return next_block_; }
    
79. 
    
80. private:
    
81.   // 每个数据块需要额外32 bytes的内存指针 + block id + next pointer
    
82.   // 这点开销比起4kB不到1%所以可以忽略不计
    
83.   void* block_data_;
    
84.   int64_t block_id_;
    
85.   Arena* arena_;
    
86.   std::unique_ptr<Block> next_block_;
    
87. };
    
88. 
    
89. // Queue的实现
    
90. template <typename T>
    
91. class Queue {
    
92. public:
    
93.   explicit Queue(Arena* arena)
    
94.       : arena_(arena),
    
95.         block_capacity_(kBlockSize / sizeof(T)) {
    
96.     CHECK(block_capacity_ > 0);
    
97.   }
    
98. 
    
99.   // 往队列头添加一个新元素
    
100.   void PushFront(T value) {
     
101.     if (UNLIKELY(front_ == nullptr)) {
     
102.       // Block链表为空
     
103.       back_ = arena_->Allocate<Block>();
     
104.       front_ = back_.get();
     
105.     } else if (UNLIKELY(head_exclusive_ >= block_capacity_)) {
     
106.       // front_已经满了
     
107.       front_->next_block() = arena_->Allocate<Block>();
     
108.       front_ = front_->next_block().get();
     
109.       head_exclusive_ = 0;
     
110.     }
     
111.     ++size_;
     
112.     front_->Set(head_exclusive_++, value);
     
113.   }
     
114. 
     
115.   // 从队列尾取出一个元素
     
116.   T PopBack() {
     
117.     if (UNLIKELY(back_.get() == front_)) {
     
118.       // 链表里只有一个数据块的情况
     
119.       CHECK(tail_inclusive_ < head_exclusive_);
     
120.     } else if (UNLIKELY(tail_inclusive_ >= block_capacity_)) {
     
121.       // back_没有剩余元素了，对其回收并移动到下一个数据块
     
122.       back_ = std::move(back_->next_block());
     
123.       tail_inclusive_ = 0;
     
124.       CHECK(back_ != nullptr);
     
125.     }
     
126.     --size_;
     
127.     return back_->Get<T>(tail_inclusive_++);
     
128.   }
     
129. 
     
130.   size_t size() const { return size_; }
     
131.   bool IsEmpty() const { return size_ == 0; }
     
132. 
     
133. private:
     
134.   Arena* const arena_;
     
135.   const int64_t block_capacity_;
     
136.   int64_t size_ = 0;
     
137. 
     
138.   // 这里back_是链表头，但是是队列尾
     
139.   std::unique_ptr<Block> back_;
     
140.   int64_t tail_inclusive_ = 0;
     
141. 
     
142.   // front_是链表尾，但是是队列头
     
143.   Block* front_ = nullptr;
     
144.   int64_t head_exclusive_ = 0;
     
145. };
     
146. 
     
147. // 测试代码
     
148. int main(int argc, char* argv[]) {
     
149.   Arena arena(/*size=*/4 * 1024 * 1024);
     
150. 
     
151.   Queue<int> a(&arena);
     
152.   Queue<int64_t> b(&arena);
     
153. 
     
154.   for (int i = 1; i <= 10000; ++i) {
     
155.     a.PushFront(i);
     
156.     b.PushFront(i);
     
157.   }
     
158.   while (!a.IsEmpty()) {
     
159.     b.PushFront(a.PopBack() * 10);
     
160.   }
     
161. 
     
162.   int64_t b_sum = 0;
     
163.   while (!b.IsEmpty()) {
     
164.     b_sum += b.PopBack();
     
165.   }
     
166.   std::cout << "b sum = " << b_sum << "\n";
     
167. 
     
168.   return 0;
     
169. }
     

复制代码

Andrew007 发表于 2021-3-19 04:24
非常感谢回复。有一个问题，就是这个array里面只能放Integer，不能有其他的信息，跟面试官确认了很多遍， ...

其实写Node的初衷就是为了方便访问，如果不能写Node的话，我觉得可以用index%2来区分是数据还是next指针，麻烦了一点但是还是可以正常跑的，我可是改一下代码再看看。

这里做了一个延伸，不限制queue的数量，从参数里指定。

1. 
   
2. 
   
3. #include <iostream>
   
4. #include <vector>
   
5. using namespace std;
   
6. 
   
7. 
   
8. struct MultiQueue
   
9. {
   
10.     int tail;
    
11.     int capacity;
    
12.     int queueCount;
    
13.     vector<int> data;
    
14.     vector<int> heads;
    
15.     vector<int> tails;
    
16.     MultiQueue(int count, int cap)
    
17.     {
    
18.         queueCount = count;
    
19.         capacity = cap;
    
20.         tail = 0;
    
21.         data.resize(cap*2);
    
22.         heads.assign(count, -1);
    
23.         tails.assign(count, -1);
    
24.     }
    
25. 
    
26.     bool push(int index, int val)
    
27.     {
    
28.         if(index<0||index>=queueCount||tail*2>=capacity) return false;
    
29.         data[tail*2] = val;
    
30.         data[tail*2+1] = -1;
    
31.         if(heads[index] == -1)
    
32.             heads[index] = tail;
    
33.         if(tails[index] != -1) data[tails[index]*2+1] = tail;
    
34.         tails[index] = tail;
    
35.         tail++;
    
36.         return true;
    
37.     }
    
38.      
    
39.     bool pop(int index, int& res)
    
40.     {
    
41.         if(index<0||index>=queueCount||heads[index]==-1||tails[index]==-1) return false;
    
42.         res = data[heads[index]*2];
    
43.         heads[index] = data[heads[index]*2+1];
    
44.         return true;
    
45.     }
    
46.      
    
47. };
    
48. 
    
49. int main()
    
50. {
    
51.     int queueCount = 3;
    
52.     MultiQueue q(queueCount, 1024);
    
53.     q.push(0, 0);
    
54.     q.push(1, 1);
    
55.     q.push(1, 3);
    
56.     q.push(0, 2);
    
57.     q.push(0, 4);
    
58.     q.push(2, 2);
    
59.     for(int i=0;i<queueCount; ++i)
    
60.     {
    
61.         int val = -1;
    
62.         while(q.pop(i, val))
    
63.             cout << val << " ";
    
64.         cout << endl;
    
65.     }
    
66.     return 0;
    
67. }
    
68. 
    

复制代码

不确定我是否理解了题意，大概是这样的思路
做一个数据结构，用来保存数据值和下一个数据的index
做一个数据结构，用来保存整个数组，其中记录heads 和tails，分别用来记录queue的起始index和结尾index。insert就保存数据到tails的位置，同时修改把tails的值。 read就读取heads位置的值，同时修改heads的值为next。
因为不清楚是不是要清除数据，所以这里没有考虑。

贴个代码吧，也不知道对不对，仅供讨论。
老规矩，求米：）

1. 
   
2. #include <iostream>
   
3. #include <vector>
   
4. using namespace std;
   
5. 
   
6. struct Node
   
7. {
   
8.     int val;
   
9.     int next;
   
10.     Node(int val, int next){this->val = val;this->next = next;}
    
11.     Node(){}
    
12.     Node& operator=(Node n)
    
13.     {
    
14.         this->val = n.val;
    
15.         this->next = n.next;
    
16.         return *this;
    
17.     }
    
18. };
    
19. 
    
20. struct MultiQueue
    
21. {
    
22.     int tail;
    
23.     int capacity;
    
24.     int queueCount;
    
25.     vector<Node> data;
    
26.     vector<int> heads;
    
27.     vector<int> tails;
    
28.     MultiQueue(int count, int cap)
    
29.     {
    
30.         queueCount = count;
    
31.         capacity = cap;
    
32.         tail = 0;
    
33.         data.resize(cap);
    
34.         heads.assign(count, -1);
    
35.         tails.assign(count, -1);
    
36.     }
    
37.    
    
38.     bool push(int index, int val)
    
39.     {
    
40.         if(index<0||index>=queueCount||tail>=capacity) return false;
    
41.         data[tail] = Node(val, -1);
    
42.         if(heads[index] == -1)
    
43.             heads[index] = tail;
    
44.         if(tails[index] != -1) data[tails[index]].next = tail;
    
45.         tails[index] = tail;
    
46.         tail++;
    
47.         return true;
    
48.     }
    
49.    
    
50.     bool pop(int index, int& res)
    
51.     {
    
52.         if(index<0||index>=queueCount||heads[index]==-1||tails[index]==-1) return false;
    
53.         res = data[heads[index]].val;
    
54.         heads[index] = data[heads[index]].next;
    
55.         return true;
    
56.     }
    
57.    
    
58. };
    
59. 
    
60. int main()
    
61. {
    
62.     int queueCount = 2;
    
63.     MultiQueue q(2, 1024);
    
64.     q.push(0, 0);
    
65.     q.push(1, 1);
    
66.     q.push(1, 3);
    
67.     q.push(0, 2);
    
68.     q.push(0, 4);
    
69.     for(int i=0;i<queueCount; ++i)
    
70.     {
    
71.         int val = -1;
    
72.         while(q.pop(i, val))
    
73.             cout << val << " ";
    
74.         cout << endl;
    
75.     }
    
76.     return 0;
    
77. }
    

复制代码

小菜鸡来围观答案，double linked list这种因为不算array所以不能考虑是不是？

用所有memory做个循环数组？可以充分利用所有空间，然后用两个pointer表示当前queue的head和tail

这个也是我第二个solution，但是面试官明显不接受这个，一堆challenge，尝试让我用其他方法。

maandma 发表于 2021-3-19 01:37
小菜鸡来围观答案，double linked list这种因为不算array所以不能考虑是不是？

只能用 Int array

dorisH 发表于 2021-3-19 02:11
用所有memory做个循环数组？可以充分利用所有空间，然后用两个pointer表示当前queue的head和tail

这个也是我第二个solution，但是面试官明显不接受这个，一堆challenge，尝试让我用其他方法。

twtypsj 发表于 2021-3-19 03:56
不确定我是否理解了题意，大概是这样的思路
做一个数据结构，用来保存数据值和下一个数据的index
做一个 ...

非常感谢回复。有一个问题，就是这个array里面只能放Integer，不能有其他的信息，跟面试官确认了很多遍，所以感觉这个Node应该是不支持的。已加米。

circular queue?