3

这个名字说明了一切，但为了详细说明，我有一个带有时间戳的向量列表。它们大多是排序的，但会有一些乱序值。我想以有序的方式输出它们，但是向量将以流的形式出现，我不想扩大缓冲区，因为我想及时输出我的结果。

所以我想保留一个包含 N 个向量的“前瞻”列表。当我读入新向量时，我想将其插入列表中，然后从列表顶部弹出最旧的向量以输出，以便列表保持恒定的 N 个向量长。

当我插入列表时，我希望对向量进行排序并添加到列表中的正确位置，因为我认为这是最有效的方法。

我需要良好的效率，但不想浪费太长时间的实施和测试。因此，我对简单的解决方案（例如重用现有的 C++ 结构，如果它们存在）以及如果它们可以显着提高速度，则更难实现的解决方案感兴趣。我宁愿坚持使用标准 C++，但如果有一个 boost 或类似的库可以完全满足我的需要，我很想听听它以防万一。

谢谢你。

编辑：我感谢所有建议。但是，我忽略了时间戳不是唯一的。时间戳只有第二个精度，所以实际上很可能我得到了多个具有相同时间戳的向量。在这种情况下，我宁愿保留他们的订单，尽管这不是必需的。

4

4 回答 4

3

看看std::multiset课堂。

您应该检查其插入方法：

#include <set>
#include <functional>

const size_t max_item_number = 100;

struct your_type
{
  std::string str;
  time_t datetime;
};

class your_less : std::binary_function<your_type,your_type,bool>
{
public:
  bool operator()( const your_type &left, const your_type &right ) const
  {
    return ( left.datetime < right.datetime );
  }
};


std::multiset<your_type,your_less> store;
std::multiset<your_type,your_less>::iterator helper = store.begin();

helper = store.insert( helper, new_value );
helper = store.insert( helper, new_value );

// fixed size: remove the oldest value
// you could use it e.g. in loop
if ( store.size() == max_item_number )
{
  store.erase( store.begin() );
  helper = store.begin();
}

这样，如果流是有序的，则插入时间可以是恒定的。

于 2012-07-02T18:34:09.030 回答
1

简单的选项：priority_queue O(lg n) 插入和提取 min 并且比 set/multiset 快很多（对于整数来说大约是 3 倍）并且内存占用更小

如果输入几乎已排序，则可以使用插入排序的一些变体。你只需保持排序的双端队列并在后面的某个地方插入东西并从前面弹出分钟。

于 2012-07-02T19:26:40.293 回答
0

看看std::set课堂。

于 2012-07-02T18:28:32.497 回答
0

如果你要在一个大缓冲区和一个大排序中完成它，那么 Timsort 会很棒。它能够利用部分排序。但你说你不需要那个。

如果您需要在没有循环内排序的情况下保持可管理性，那么最好使用诸如treap 或红黑树之类的东西。

Treaps 平均速度很快（我最近在 Python 中对许多不同条件下的树数据结构进行了性能比较，发现平均而言，traps 总是最快或第二快 - 根据工作负载，另外两个有时比 treaps 快一点，但并非始终如此）

据报道，红黑树的操作时间标准差较低（与平均而言，它们与trap相比有点慢，但如果这是一个实时或交互式应用程序，红黑树可能更好，因为它的操作时间可变性低）。

于 2012-07-02T21:09:36.850 回答