2

我有一个 C++ 函数，该函数需要将一系列连续整数插入到一个集合中，并且对于该集合的每个新元素在出列末尾以与迭代相同的顺序插入。下面是一个大约为 O(log(n) * n) 的解决方案，因为重复插入每个都是 O(log(n))。我想得到一个 O(n) 解决方案。我想使用带有提示迭代位置的 set::insert() ，但是如果我这样做，我看不到如何在恒定时间内确定该项目是否已经在集合中。

#include <deque>
#include <set>

void
insertUnique(const int beginOffset,
             const int endOffset,
             std::set<int> &sent,
             std::deque<int> &recent)
{
  for (int offset = beginOffset; offset < endOffset; ++offset) {
    const bool inserted = sent.insert(offset).second;

    if (inserted) {
      recent.push_back(offset);
    }
  }
}

有没有办法将其重构为 O(n) 并完成相同的工作，同时保持函数的参数不变？有没有办法使用迭代器提示插入并且还知道该项目是否被插入？

4

1 回答 1

1

如果sent仅用于确定整数是否已排队，那么我建议使用 astd::unordered_set因为所有插入和搜索都有平均恒定时间。

然而，除非你的系列变得庞大，否则它不太可能产生太大的影响。

事实上，如果记录的不同整数的数量小于~1000，那么使用向量甚至可以获得更好的实际性能，特别是如果你保持它的排序 - 因为std::find()使用的是 O(logN) 时间但没有指针的二进制搜索取消引用并具有良好的内存局部性。

编辑：

只是为了好玩，我进行了几次尝试，但问题是sent它set<>没有比 O(logN) 更快的插入方法。

这个将集合复制到 unordered_set （平均恒定时间操作），但最终插入是 logN :-(

void
insertUnique_average_constant(const int beginOffset,
                              const int endOffset,
                              std::set<int> &sent,
                              std::deque<int> &recent)
{
    std::unordered_set<int> temp_sent(begin(sent), end(sent));

    for (int offset = beginOffset; offset < endOffset; ++offset) {
        const bool inserted = temp_sent.insert(offset).second;

        if (inserted) {
            recent.push_back(offset);
        }
    }

    sent.insert(begin(temp_sent), end(temp_sent));
}

如果你能忍受的话，这个可能会有一些承诺。它试图使用 set_difference (O2n) 来减少必须发送然后缓存的项目集的大小，因此理论上它会随着sent集合的扩展而提高效率。

// a minimal iterator that simply serves the next int in sequence
struct next_index_iterator
{
    using value_type = int;

    next_index_iterator(int value)
    : _value(value)
    {}

    bool operator==(const next_index_iterator& that) const {
        return this->_value == that._value;
    }

    next_index_iterator& operator++() {
        ++_value;
        return *this;
    }

    next_index_iterator operator++(int) {
        return next_index_iterator(_value + 1);
    }

    const int& operator*() const {
        return _value;
    }

private:
    int _value;
};

// necessary for set_difference to compile    
namespace std {
    template<>
    struct iterator_traits<next_index_iterator>
    {
        using value_type = next_index_iterator::value_type;
    };
}


void
insertUnique_sort_of_2N(const int beginOffset,
                              const int endOffset,
                              std::set<int> &sent,
                              std::deque<int> &recent)
{
    std::vector<int> to_send;
    to_send.reserve(endOffset - beginOffset); 

    // set_difference is O(2N)
    std::set_difference(std::begin(sent), std::end(sent),
                        next_index_iterator(beginOffset),
                        next_index_iterator(endOffset),
                        std::back_inserter(to_send));

    // at this point to_send contains only the offsets we have not sent
    for (const auto offset : to_send) {
        recent.push_back(offset);
    }

    // but we still have to insert these into `sent` at the end    
    sent.insert(std::begin(to_send), std::end(to_send));
}
于 2014-12-14T16:42:44.797 回答