Gibt es einen effizienten Algorithmus zum Zusammenführen numerischer Bereiche?

Question

Ich habe eine Reihe von Bereichen und ich muss jede Zahl in einem der Bereiche genau einmal durchlaufen. Die Bereiche können sich überlappen und die gleichen Nummern enthalten.

Die Zahlen liegen im Bereich

using Number = uint32_t; 

Bereiche dieser Form sind

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

einfach die Darstellung Range zu klären.

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

//is equivalent to... 

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

Ich habe ein paar Range s und ich brauche nur einmal alle Zahlen in beliebiger Reihenfolge effizient zu durchlaufen.

Wie kann ich eine Reihe von Bereichen effizient iterieren?

Auch Gibt es einen effizienteren Algorithmus, wenn Intervall immer 1 ist?

Answer 1

Für jeden Bereich, erinnern Sie sich an den "aktuellen" Wert (von der ersten bis zur letzten mit der Schrittgröße). Fügen Sie das zusammen mit dem Bereich in eine Prioritätswarteschlange ein, sortiert nach dem aktuellen Wert.

Nimm die Spitze heraus, wenn ihr aktueller Wert sich von der letzten unterscheidet, dann benutze sie. Fügen Sie dann den nächsten Schritt ein, wenn es einen anderen gibt.

Vorausgesetzt, dass die Schrittweite positiv ist.

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)); 
    } 
} 

Speicherbedarf: in der Anzahl der Bereiche linear. Zeitbedarf: Summe aller Schrittzählungen in jedem Bereich.

Small example:

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); 
} 

Um alle Zahlen in einem Vektor zu erhalten, eine Lambda mit einem Verweis auf einen Vektor verwenden und drücken Sie jeden zurück.

Gibt es einen effizienteren Algorithmus, wenn Intervall immer 1 ist?

Sie könnten das als Sonderfall hinzufügen, aber ich denke nicht, dass es notwendig sein wird. Wenn Sie nur ~ 50 Bereiche haben, dann wird Push nicht so teuer sein. Obwohl, mit aller Optimierung: Profil zuerst!

Answer 2

Wenn die Sequenzen sehr lang sind, möchten Sie vielleicht einfach jedes Ergebnis der Reihe nach aufnehmen, ohne die Liste zu speichern und die Duplikate zu verwerfen.

#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); 
    } 
} 

Dies möchte den Bereich in einem "Generator" -Typ-Objekt dargestellt. Würde wahrscheinlich sehr ähnlich aussehen wie die Implementierung von checked a iterator, aber Iteratoren stellen nicht den Gedanken dar, dass sie wissen, dass sie sich am Ende der Sequenz befinden, so dass wir vielleicht unseren eigenen einfachen Generator rollen müssen.

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_; 
}; 

Testbeispiel:

#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;