有没有一种高效的算法可以合并数字范围？

Question

我需要遍历一系列区间中的每个数字，确保每个数字仅被遍历一次。这些区间可能会重叠并包含相同的数字。

区间中的数字为：

using Number = uint32_t;

范围是这种形式

struct Range {
  Number first;
  Number last;
  Number interval;
};

仅澄清Range的表示。

Range range = {
  2,  //first
  14, //last
  3   //interval
};

//is equivalent to...

std::vector<Number> list = {2, 5, 8, 11, 14};

我有几个Range，需要高效地按任意顺序迭代所有数字。 如何高效地迭代一组范围？ 此外，如果间隔始终为1，是否存在更有效的算法？

- Indiana Kernick

---

std::merge() 对你不起作用吗？ - πάντα ῥεῖ

你是在建议我用Range中的数字填充一个std::vector<Number>，然后将这些向量进行std::merge吗？ - Indiana Kernick

最后一个例子我不太清楚， std::min(a.first, a.first) 你的意思是什么？对于整个问题，你想得到什么？还有 interval 是什么？ - apple apple

如果我理解正确的话，例如数字1可能会出现在多个范围或列表中，但您只想对其进行一次迭代？ - Pandatyr

由于您可以拥有任意间隔，我认为没有比在所有范围内列出所有数字并将它们合并更好的方法了（因为您需要遍历所有数字）。这也可以在原地完成。 - Sopel

Answer 1

对于每个范围，记住“当前”值（以步长从第一个到最后一个）。将其与范围一起放入优先队列中，在当前值之后排序。

取出顶部，如果其当前值与上一个不同，则使用它。然后，如果有下一个步骤，请插入它。

假设步长为正数。

template<typename Iterator, typename Operation>
void iterate_ranges (Iterator from, Iterator to, Operation op) {
  using R = typename std::iterator_traits<Iterator>::value_type;
  using N = typename std::decay<decltype(std::declval<R>().first)>::type;
  using P = std::pair<N, R>;
  auto compare = [](P const & left, P const & right) {
    return left.first > right.first;};

  std::priority_queue<P, std::vector<P>, decltype(compare)> queue(compare);

  auto push = [& queue] (P p) {
    if (p.first < p.second.last) queue.push(p); };
  auto next = [](P const & p) -> P {
    assert(p.second.step > 0);
    return {p.first + p.second.step, p.second}; };
  auto init = [&push] (R const & r) {
    push({r.first, r}); };

  std::for_each(from, to, init);

  if (queue.empty()) return;

  N last = queue.top().first;
  push(next(queue.top()));
  queue.pop();
  op(last);

  while (! queue.empty()) {
    P current = queue.top();
    queue.pop();
    if (current.first != last) {
      op(current.first);
      last = current.first;
    }
    push(next(current));
  }
}

内存需求：与范围数量成线性关系。时间需求：在每个范围内所有步骤计数之和。

小例子：

struct Range {
  int first;
  int last;
  int step; // a better name ...
};


int main() {
  Range ranges [] = {
    {1, 10, 2},
    {2, 50, 5}};

  auto print = [](auto n) { std::cout << n << std::endl; };

  iterate_ranges(std::begin(ranges), std::end(ranges), print);
}

为了获取向量中的所有数字，请使用带有对向量的引用的lambda表达式，并将每个数字推回去。

如果间隔始终为1，是否有更有效的算法？

你可以将其作为特殊情况添加，但我认为这不是必要的。如果你只有大约50个范围，则上述推送不会太昂贵。尽管如此，还是要进行优化：首先进行性能分析！

- Daniel Jour

---

使用优先队列的非常简洁的解决方案。假设范围包括最后一个元素，则测试应该是 p.first <= p.second.last，并且还需要进行另外一些小的调整以避免理论上可能出现的在最后一个值溢出后的包装情况。 - Mic

Answer 2

如果序列非常长，您可能希望按顺序获取每个结果，而不存储列表，并在执行过程中丢弃重复项。

#include <vector>

// algorithm to interpolate integer ranges/arithmetic_sequences
template<typename ASqs, typename Action>
void arithmetic_sequence_union(ASqs arithmetic_sequences, Action action)
{
    using ASq = ASqs::value_type;
    using T = ASq::value_type;
    std::vector<ASq> remaining_asqs(begin(arithmetic_sequences), end(arithmetic_sequences));
    while (remaining_asqs.size()) {
        // get next value
        T current_value = **std::min_element(begin(remaining_asqs), end(remaining_asqs),
            [](auto seq1, auto seq2) { return *seq1 < *seq2; }
        );
        // walk past this value and any duplicates, dropping any completed arithmetic_sequence iterators
        for (size_t seq_index = 0; seq_index < remaining_asqs.size(); )
        {
            ASq &asq = remaining_asqs[seq_index];
            if (current_value == *asq // do we have the next value in this sequence?
                && !++asq) { // consume it; was it the last value in this sequence?
                remaining_asqs.erase(begin(remaining_asqs) + seq_index);//drop the empty sequence
            }
            else {
                ++seq_index;
            }
        }
        action(current_value);
    }
}

这需要在“生成器”类型对象中呈现范围。可能看起来非常像已检查迭代器的实现，但迭代器不公开知道它们处于序列末尾的概念，因此我们可能需要自己编写简单的生成器。

template <typename ValueType, typename DifferenceType>
class arithmetic_sequence {
public:
    using value_type = ValueType;
    using difference_type = DifferenceType;
    arithmetic_sequence(value_type start, difference_type stride, value_type size) : 
        start_(start), stride_(stride), size_(size) {}
    arithmetic_sequence() = default;
    operator bool() { return size_ > 0; }
    value_type operator*() const { return start_; }
    arithmetic_sequence &operator++() { --size_; start_ += stride_; return *this;}
private:
    value_type start_;
    difference_type stride_;
    value_type size_;
};

测试示例：

#include "sequence_union.h"
#include "arithmetic_sequence.h"
#include <cstddef>
#include <array>
#include <algorithm>
#include <iostream>

using Number = uint32_t;

struct Range {
    Number first;
    Number last;
    Number interval;
};

using Range_seq = arithmetic_sequence<Number, Number>;


Range_seq range2seq(Range range)
{
    return Range_seq(range.first, range.interval, (range.last - range.first) / range.interval + 1 );
}

int main() {
    std::array<Range, 2> ranges = { { { 2,14,3 },{ 2,18,2 } } };
    std::array<Range_seq, 2> arithmetic_sequences;
    std::transform(begin(ranges), end(ranges), begin(arithmetic_sequences), range2seq);

    std::vector<size_t> results;
    arithmetic_sequence_union(
        arithmetic_sequences,
        [&results](auto item) {std::cout << item << "; "; }
    );

    return  0;
}

// output: 2; 4; 5; 6; 8; 10; 11; 12; 14; 16; 18;

- Mic