首页 文章

C矢量元素擦除与新的矢量创作

提问于
浏览 次
2

我正在处理需要随机选择并有效删除的元素向量，直到满足条件或者直到选择了所有元素 . 但是，它们实际上不会在代码执行的后期阶段被删除，因此我需要维护一个有效的可用元素列表 . 我可以从第二个向量中删除元素，或者每次都可以重新创建它 . 请参阅下面的代码的最小版本，其中显示了每次在while循环中创建向量的示例：

Random mRandom; // Pseudo-random number generator
    std::vector< Element* > mElements;
    for( unsigned index = 0; index < ARBITRARY_VALUE; index++ )
      mElements.push_back( new Element( ) );

    std::vector< bool > removedElements;
    bool condition = true;

    while( condition == true ) {
      std::vector< unsigned > availableIndices;

      for( unsigned index = 0; index < mElements.size( ); index++ ) {
        if( removedElements[ index ] == false )
          availableIndices.push_back( index );
      }

      if( availableIndices.size( ) > 0 ) {
        unsigned maximum = availableIndices.size( ) - 1;
        unsigned randomIndex = mRandom.GetUniformInt( maximum ); // Zero to max
        removedElements[ availableIndices[ randomIndex ] ] = true;
        Element* element = mElements[ availableIndices[ randomIndex ] ];
        condition = element->DoStuff( ); // May change condition and exit while
      } else
        break;
    }

很明显，在向量中间擦除元素需要底层系统迭代剩余的元素并将它们“移动”到新的有效位置 . 显然，如果擦除的元素接近向量的末尾，则意味着更少的迭代 .

我已经阅读了一些关于擦除矢量元素相关费用的帖子，但我没有看到任何直接解决我问题的内容 . 擦除后“移动”元素的过程是否会引入开销，通过创建指向有效元素的新向量，每次迭代所有元素会降低成本？就像我上面的代码示例一样 .

干杯，菲尔

c++ performance vector processing-efficiency cpu-speed

2 回答

  • 1

    我无法评论解决问题的最佳方法，因为我还不确定函数或算法的实际要求是什么（即元素是否应该保留顺序？不可用的元素是否会再次可用？如果有，会订购问题那么？等等）

    但是，关于最后一个问题：

    擦除后“移动”元素的过程是否会引入开销，通过创建指向有效元素的新向量，每次迭代所有元素会降低成本？

    这完全取决于移动元素所涉及的内容 . 如果它是一个指针，如上所述，那么你甚至可以在接近分配新向量中的内存的成本之前移动很多元素 . 而且“很多”我在想数百甚至数千 .

    在上面的代码中，看起来可用性向量是多余的 . 如果它位于 availableIndicies 的向量中，则 Element 指针可用 .

    如果我理解正确的意图，我想我可能会按以下方式重构：

    #include <vector>
#include <random>

struct Element
{
  bool doStuff();
};


struct ElementAvailability
{
  ElementAvailability(std::vector<Element*> const& storage)
  : storage_(storage)
  {}

  void resync()
  {
    // will requre an allocation at most once if storage_ does not grow
    available_ = storage_;
  }

  std::size_t availableCount() const {
    return available_.size();
  }

  Element* removeAvailable(std::size_t index) {
    auto pe = available_[index];
    available_.erase(std::begin(available_) + index);
    return pe;
  }

  void makeUnavailable(std::size_t available_i)
  {
    available_.erase(std::next(std::begin(available_), available_i));
  }

private:
  std::vector<Element*> const& storage_;
  std::vector<Element*> available_;
};

// I have used a std random engine because I don't know your library
auto eng = std::default_random_engine(std::random_device()());

void test(std::vector<Element*>const& elems)
{
  auto available = ElementAvailability(elems);

  bool condition = true;
  auto getCount =[&condition, &available] () -> std::size_t 
  {
    if (condition) {
      available.resync();
      auto count = available.availableCount();
      return count;
    }
    else {
      return 0;
    }
  };

  while (auto count = getCount()) {
    auto range = std::uniform_int_distribution<std::size_t>(0, count - 1);
    auto index = range(eng);
    auto candidate = available.removeAvailable(index);
    condition = candidate->doStuff();
  }
}
    回复于
  • 0

    随机消除你提出的元素的问题似乎只能在 O(n^2) 时间和 O(n) 空间复杂度中解决 . 因为您必须传递所有元素一次并且在每次传递时必须在一系列仍然存在的元素中找到随机索引并维护此序列 . 可能很少有使用不同算法原语的方法 . 下面我介绍我的解决方案，以CPU /内存操作友好的方式执行此目标 .

    void runRandomTasks() {
  Random mRandom; // Pseudo-random number generator
  std::vector<Element*> mElements;
  for (unsigned index = 0; index < ARBITRARY_VALUE; ++index) {
    mElements.push_back(new Element);
  }
  size_t current_size = mElements.size();
  if (!current_size)
    return;
  std::vector<Element*> current_elements(current_size, nullptr);
  for (unsigned index = 0; index < current_size; ++index) {
    current_elements[index] = mElements[index];
  }
  Element** last_ptr = &current_elements[0] + current_size - 1;

  bool condition = true;

  while (condition && current_size) {
    unsigned random_size = mRandom.GetUniformInt(current_size - 1) + 1; // Zero to max
    Element** ptr = last_ptr;
    while (true) {
      random_size -= (bool)(*ptr);
      if (random_size) {
        --ptr;
      } else {
        break;
      }
    }

    condition = (*ptr)->DoStuff(); // May change condition and exit while
    *ptr = nullptr;
    --current_size;
  }
}

    关于向量元素擦除的问题，你可以在我的解决方案中找到一个寻找随机索引的循环，这相当于时间复杂度中向量中的元素擦除，但由于省略了元素移位而具有较小的常量，而是元素值被检查为 0 或不 . 在循环中进行任何内存分配总是很昂贵，所以要避免这种情况 .

    回复于

相关问题