5

什么被认为是按顺序推送某物的最佳数据结构（因此在任何位置插入，能够找到正确的位置），按顺序迭代，并从顶部弹出 N 个元素（因此 N 个最小元素，N 通过与阈值）？推送和弹出需要特别快（运行循环的每次迭代），而数据的有序完整迭代以可变速率发生，但频率可能少一个数量级。数据不能被完全迭代清除，它需要保持不变。所有被推送的东西最终都会被弹出，但是由于弹出可以删除多个元素，所以推送可能比弹出更多。任何时候结构中的数据规模可能高达数百或数千个元素。

我目前正在使用std::deque二分搜索按升序插入元素。分析表明它占用了大部分时间，所以必须改变一些东西。 std::priority_queue不允许迭代，我见过的黑客不会按顺序迭代。即使在有限的测试中（没有完整的迭代！），该std::set课程的表现也比我的std::deque方法差。

我搞砸的所有类似乎都没有考虑到这个用例。如果由于某种原因在 STL 或 boost 中找不到数据结构，我不反对创建自己的类。

编辑：

现在有两个主要功能，push和prune。 push使用 65% 的时间，prune使用 32%。使用的大部分时间push是由于插入deque（65% 中的 64%）。只有 1% 来自二分查找来寻找位置。

template<typename T, size_t Axes>
void Splitter<T, Axes>::SortedData::push(const Data& data) //65% of processing
{
 size_t index = find(data.values[(axis * 2) + 1]);

 this->data.insert(this->data.begin() + index, data); //64% of all processing happens here
}

template<typename T, size_t Axes>
void Splitter<T, Axes>::SortedData::prune(T value) //32% of processing
{
 auto top = data.begin(), end = data.end(), it = top;

 for (; it != end; ++it)
 {
  Data& data = *it;

  if (data.values[(axis * 2) + 1] > value) break;
 }

 data.erase(top, it);
}

template<typename T, size_t Axes>
size_t Splitter<T, Axes>::SortedData::find(T value)
{
 size_t start = 0;
 size_t end = this->data.size();

 if (!end) return 0;

 size_t diff;

 while (diff = (end - start) >> 1)
 {
  size_t mid = diff + start;

  if (this->data[mid].values[(axis * 2) + 1] <= value)
  {
   start = mid;
  }
  else
  {
   end = mid;
  }
 }

 return this->data[start].values[(axis * 2) + 1] <= value ? end : start;
}
4

4 回答 4

2

根据您的要求，根据您的需求量身定制的混合数据结构可能会表现最佳。正如其他人所说，连续内存非常重要，但我不建议始终保持数组排序。我建议您使用 3 个缓冲区（1std::array和 2 std::vectors）：

  • 1（常量大小）“插入堆”的缓冲区。需要适合缓存。
  • 2 个（可变大小）缓冲区 (A+B)，用于维护和更新已排序的数组。

当你推送一个元素时，你通过 .将它添加到插入堆中std::push_heap。由于插入堆是固定大小的，它可能会溢出。发生这种情况时，您std::sort将其倒退并将std::merge其与已经排序的序列缓冲区 (A) 一起放入第三个 (B) 中，并根据需要调整它们的大小。这将是新的排序缓冲区，旧的可以被丢弃，即您交换 A 和 B 以进行下一个批量操作。当您需要排序的序列进行迭代时，您也可以这样做。当您删除元素时，您将堆中的顶部元素与排序序列中的最后一个元素进行比较并将其删除（这就是您将其向后排序的原因，以便您可以pop_back代替pop_front）。

作为参考，这个想法松散地基于序列堆。

于 2013-01-28T19:05:14.557 回答
0

你试过弄乱std::vector吗？尽管听起来很奇怪，但它实际上可能非常快，因为它使用连续内存。如果我没记错的话，Bjarne Stroustrup 在 Going Native 2012（http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Keynote-Bjarne-Stroustrup-Cpp11-Style但我不是 100% 肯定它在这个视频中）。

于 2013-01-28T16:21:24.757 回答
0

使用二分查找可以节省时间，但在双端队列的随机位置插入速度很慢。我建议改为使用 std::map 。

于 2013-01-28T16:21:28.967 回答
0

从您的编辑来看，这听起来像是复制的延迟——它是一个复杂的对象吗？您能否在结构中堆分配和存储指针，以便每个条目只创建一次；您需要提供一个带有指针的自定义比较器，因为不会调用对象 operator<()。（自定义比较器可以简单地调用operator<()）

编辑：您自己的数据表明，插入需要时间，而不是“排序”。虽然其中一些插入时间是创建对象的副本，但一些（可能大部分）是创建将保存您的对象的内部结构 - 我认为这不会在列表/映射/设置/队列等之间发生变化。如果您可以预测数据集可能的最终/最大大小，并且可以编写或找到自己的排序算法，并且分配对象的时间正在浪费，那么向量可能是要走的路。

于 2013-01-28T16:34:36.050 回答