哪种数据结构更适合 - 堆还是有序数组？

Question

我有一个程序需要实现以下功能：

1. 从磁盘中读取一些数据并加载到内存中的 std::map，该容器可以保持数据排序。

2. 将排序后的数据保存到磁盘中。

我想知道使用堆是不是更快：

1. 从磁盘中读取一些数据并加载到内存中的 std::vector 中。

2. 对向量进行排序。

3. 将排序后的数据保存到磁盘中。

或者使用堆：

1. 从磁盘中读取一些数据并加载到内存中的 std::vector 中。

2. 在向量中创建一个堆。

3. 从堆中弹出数据并将其保存到磁盘中。

请问哪种方案最快？

- Nick

---

为什么不试试两种方法，然后用你的特定工作负载进行基准测试（当然要使用优化构建）？ - Jesper Juhl

你可以对其进行基准测试，但我预计将向量排序为最快的选项。 - HolyBlackCat

@FrançoisAndrieux 平面向量对，按键（pair.first）排序 - Nick

@ThomasMatthews 这是一个玩具项目，我想尽可能地让它执行得更好。此外，我们正在谈论内存中的20-30 M对。将它们构建到内存中比将它们顺序写入磁盘花费的时间更长。 - Nick

我把更新作为答案。谢谢。 - Nick

Answer 1

你所有的方法在渐进意义下都是O(n log n)：

• 在std::map中插入元素的时间复杂度与容器大小的对数成比例。插入n个元素的时间复杂度为O(n log n)。
• 对一个std::vector应用std::sort的时间复杂度为O(n log n)。
• 使用std::make_heap可以在线性时间内创建堆。然而，从堆中弹出一个元素的时间复杂度与堆的大小的对数成比例。从堆中弹出n个元素的时间复杂度为O(n log n)。

然而，我预计使用排序std::vector和堆的方法比使用std::map更快，因为它们利用了更好的数据局部性，即这两种情况下的元素由内存中连续分配的块组成，而不是像std::map一样在内存中分散的节点。

还要注意，与其他两种方法相比，使用std::map的方法需要更多的空间，因为指针连接映射的节点。

- ローウ

---

我的想法确实是这样的。此外，映射比你想象的浪费更多的内存。当然，它在插入时给你排序，但我并不真正需要它。 - Nick

Answer 2

我想分享一些测试。

在两种情况下，我都使用了自定义分配器，因此我可以检查实际使用了多少内存。

但是我的自定义分配器无法与vector一起使用，因此不计算内部vector内存（每个记录8字节），同时分配也传递给标准分配器（operator new/malloc）。

我没有预留向量的空间，因为我不知道会有多少记录。

结论 Vector更快，使用的内存远远少于其他方式！

---

使用类STL的跳表标准实现- 比std::map慢4-5％，但使用的内存要少得多。

Processed    9940000 records. In memory    9940000 records,  310162322 bytes. Allocator  663018328 bytes.
Processed    9950000 records. In memory    9950000 records,  310477634 bytes. Allocator  663688048 bytes.
Processed    9960000 records. In memory    9960000 records,  310793005 bytes. Allocator  664357320 bytes.
Processed    9970000 records. In memory    9970000 records,  311108063 bytes. Allocator  665025016 bytes.
Processed    9980000 records. In memory    9980000 records,  311422710 bytes. Allocator  665694536 bytes.
Processed    9990000 records. In memory    9990000 records,  311738268 bytes. Allocator  666363680 bytes.
Processed   10000000 records. In memory    9999999 records,  312054428 bytes. Allocator  667035168 bytes.
Flushing data... List record(s):  9999999 List size:  312054428 

real    0m35.379s
user    0m34.218s
sys 0m1.072s

请注意，对于312'054'428字节的真实数据，实际上使用了近两倍的空间 - 667'035'168字节。

---

向量实现 - std::vector、std::sort、std::unique：

Processed    9890000 records. In memory    9890000 records,  308578515 bytes. Allocator  343196258 bytes.
Processed    9900000 records. In memory    9900000 records,  308895613 bytes. Allocator  343548385 bytes.
Processed    9910000 records. In memory    9910000 records,  309213506 bytes. Allocator  343901119 bytes.
Processed    9920000 records. In memory    9920000 records,  309531058 bytes. Allocator  344253602 bytes.
Processed    9930000 records. In memory    9930000 records,  309848406 bytes. Allocator  344605762 bytes.
Processed    9940000 records. In memory    9940000 records,  310162322 bytes. Allocator  344954565 bytes.
Processed    9950000 records. In memory    9950000 records,  310477634 bytes. Allocator  345304978 bytes.
Processed    9960000 records. In memory    9960000 records,  310793005 bytes. Allocator  345655307 bytes.
Processed    9970000 records. In memory    9970000 records,  311108063 bytes. Allocator  346005229 bytes.
Processed    9980000 records. In memory    9980000 records,  311422710 bytes. Allocator  346355138 bytes.
Processed    9990000 records. In memory    9990000 records,  311738268 bytes. Allocator  346705788 bytes.
Processed   10000000 records. In memory    9999999 records,  312054428 bytes. Allocator  347057202 bytes.
Flushing data... List record(s):  9999999 List size:  312054428 

real    0m12.759s
user    0m11.929s
sys 0m0.791s

---

测试 80M 对：

2:08 对比 6:17

- Nick