Комбинации N Boost interval_set

Question

У меня есть служба, которая имеет перебои в работе в 4 разных местах. Я моделирую каждое отключение местоположения в Boost ICL interval_set. Я хочу знать, когда по крайней мере N местоположений имеют активное отключение.

Поэтому, следуя этому ответу, я реализовал комбинированный алгоритм, чтобы я мог создавать комбинации между элементами с помощью пересечений interval_set.

Когда этот процесс закончен, у меня должно быть определенное количество interval_set, каждое из которых одновременно определяет отключения для N местоположений, и последним шагом будет присоединение к ним, чтобы получить желаемую полную картину.

Проблема в том, что я сейчас отлаживаю код, и когда приходит время печати каждого пересечения, выводимый текст сходит с ума (даже когда я использую gdb для отладки шаг за шагом), и я не вижу их, в результате много использования процессора.

Я предполагаю, что каким-то образом я посылаю на вывод больший объем памяти, чем должен, но я не вижу, в чем проблема.

Это SSCCE:

#include <boost/icl/interval_set.hpp>
#include <algorithm>
#include <iostream>
#include <vector>


int main() {
    // Initializing data for test
    std::vector<boost::icl::interval_set<unsigned int> > outagesPerLocation;
    for(unsigned int j=0; j<4; j++){
        boost::icl::interval_set<unsigned int> outages;
        for(unsigned int i=0; i<5; i++){
            outages += boost::icl::discrete_interval<unsigned int>::closed(
                (i*10), ((i*10) + 5 - j));
        }
        std::cout << "[Location " << (j+1) << "] " << outages << std::endl;
        outagesPerLocation.push_back(outages);
    }

    // So now we have a vector of interval_sets, one per location. We will combine
    // them so we get an interval_set defined for those periods where at least
    // 2 locations have an outage (N)
    unsigned int simultaneusOutagesRequired = 2;  // (N)

    // Create a bool vector in order to filter permutations, and only get
    // the sorted permutations (which equals the combinations)
    std::vector<bool> auxVector(outagesPerLocation.size());
    std::fill(auxVector.begin() + simultaneusOutagesRequired, auxVector.end(), true);

    // Create a vector where combinations will be stored
    std::vector<boost::icl::interval_set<unsigned int> > combinations;

    // Get all the combinations of N elements
    unsigned int numCombinations = 0;
    do{
        bool firstElementSet = false;
        for(unsigned int i=0; i<auxVector.size(); i++){
            if(!auxVector[i]){
                if(!firstElementSet){
                    // First location, insert to combinations vector
                    combinations.push_back(outagesPerLocation[i]);
                    firstElementSet = true;
                }
                else{
                    // Intersect with the other locations
                    combinations[numCombinations] -= outagesPerLocation[i];
                }
            }
        }
        numCombinations++;
        std::cout << "[-INTERSEC-] " << combinations[numCombinations] << std::endl;  // The problem appears here
    }
    while(std::next_permutation(auxVector.begin(), auxVector.end()));

    // Get the union of the intersections and see the results
    boost::icl::interval_set<unsigned int> finalOutages;
    for(std::vector<boost::icl::interval_set<unsigned int> >::iterator
        it = combinations.begin(); it != combinations.end(); it++){
        finalOutages += *it;
    }

    std::cout << finalOutages << std::endl;
    return 0;
}

Любая помощь?

Answer 1

Как я и предполагал, здесь есть подход "высокого уровня".

Контейнеры Boost ICL - это больше, чем просто контейнеры "прославленных пар интервалов начальной / конечной точек". Они предназначены для реализации именно этого бизнеса по объединению, поиску в общем оптимизированном виде.

Так что тебе не нужно.

Если вы позволите библиотеке делать то, что она должна делать:

using TimePoint = unsigned;
using DownTimes = boost::icl::interval_set<TimePoint>;
using Interval  = DownTimes::interval_type;
using Records   = std::vector<DownTimes>;

Использование функциональных доменных typedefs предлагает подход более высокого уровня. Теперь давайте зададим гипотетический "деловой вопрос":

Что мы на самом деле хотим сделать с нашими записями простоев по месту службы?

Ну, по сути, мы хотим

1. подсчитать их для всех заметных временных интервалов и
2. отфильтруйте те, где подсчеты не менее 2
3. наконец, мы хотели бы показать "объединенные" временные интервалы, которые остались.

Хорошо, инженер: внедри это!

---

1. Хм. Тальманские. Как трудно это может быть?

   To Ключом к элегантным решениям является выбор правильной структуры данных

   using Tally     = unsigned; // or: bit mask representing affected locations?
   using DownMap   = boost::icl::interval_map<TimePoint, Tally>;
   

   Теперь это просто массовая вставка:

   // We will do a tally of affected locations per time slot
   DownMap tallied;
   for (auto& location : records)
       for (auto& incident : location)
           tallied.add({incident, 1u});
   

2. Хорошо, давайте отфильтруем. Нам просто нужен предикат, который работает на нашем DownMap, верно

   // define threshold where at least 2 locations have an outage
   auto exceeds_threshold = [](DownMap::value_type const& slot) {
       return slot.second >= 2;
   };
   

3. Объедините временные интервалы!

   На самом деле. Мы просто создаем еще один набор DownTimes, верно. Просто не в этот раз.

   Выбор структуры данных снова побеждает:

   // just printing the union of any criticals:
   DownTimes merged;
   for (auto&& slot : tallied | filtered(exceeds_threshold) | map_keys)
       merged.insert(slot);
   

Доклад!

std::cout << "Criticals: " << merged << "\n";

Обратите внимание, что нигде мы не приблизились к манипулированию индексами массива, перекрывающимся или непересекающимся интервалам, закрытым или открытым границам. Или [eeeeek!] Перестановки элементов грубой силы.

Мы только что заявили о наших целях, и пусть библиотека сделает всю работу.

Полная демонстрация

Жить на Колиру

#include <boost/icl/interval_set.hpp>
#include <boost/icl/interval_map.hpp>
#include <boost/range.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <algorithm>
#include <iostream>
#include <vector>

using TimePoint = unsigned;
using DownTimes = boost::icl::interval_set<TimePoint>;
using Interval  = DownTimes::interval_type;
using Records   = std::vector<DownTimes>;

using Tally     = unsigned; // or: bit mask representing affected locations?
using DownMap   = boost::icl::interval_map<TimePoint, Tally>;

// Just for fun, removed the explicit loops from the generation too. Obviously,
// this is bit gratuitous :)
static DownTimes generate_downtime(int j) {
    return boost::accumulate(
            boost::irange(0, 5),
            DownTimes{},
            [j](DownTimes accum, int i) { return accum + Interval::closed((i*10), ((i*10) + 5 - j)); }
        );
}

int main() {
    // Initializing data for test
    using namespace boost::adaptors;
    auto const records = boost::copy_range<Records>(boost::irange(0,4) | transformed(generate_downtime));

    for (auto location : records | indexed()) {
        std::cout << "Location " << (location.index()+1) << " " << location.value() << std::endl;
    }

    // We will do a tally of affected locations per time slot
    DownMap tallied;
    for (auto& location : records)
        for (auto& incident : location)
            tallied.add({incident, 1u});

    // We will combine them so we get an interval_set defined for those periods
    // where at least 2 locations have an outage
    auto exceeds_threshold = [](DownMap::value_type const& slot) {
        return slot.second >= 2;
    };

    // just printing the union of any criticals:
    DownTimes merged;
    for (auto&& slot : tallied | filtered(exceeds_threshold) | map_keys)
        merged.insert(slot);

    std::cout << "Criticals: " << merged << "\n";
}

Какие отпечатки

Location 1 {[0,5][10,15][20,25][30,35][40,45]}
Location 2 {[0,4][10,14][20,24][30,34][40,44]}
Location 3 {[0,3][10,13][20,23][30,33][40,43]}
Location 4 {[0,2][10,12][20,22][30,32][40,42]}
Criticals: {[0,4][10,14][20,24][30,34][40,44]}

Answer 2

В конце цикла перестановки вы пишете:

numCombinations++;
std::cout << "[-INTERSEC-] " << combinations[numCombinations] << std::endl;  // The problem appears here

Мой отладчик говорит мне, что на первой итерации numCombinations было 0 до приращения. Но при увеличении это сделало его вне диапазона для combinations контейнер (так как это только один элемент, поэтому с индексом 0).

Вы хотели увеличить его после использования? Была ли какая-то конкретная причина не использовать

std::cout << "[-INTERSEC-] " << combinations.back() << "\n";

или для C++03

std::cout << "[-INTERSEC-] " << combinations[combinations.size()-1] << "\n";

или даже просто:

std::cout << "[-INTERSEC-] " << combinations.at(numCombinations) << "\n";

который бы бросил std::out_of_range?

---

Кстати, я думаю, что Boost ICL предлагает гораздо более эффективные способы получить ответ, который вы ищете. Позвольте мне подумать об этом на мгновение. Выложу еще один ответ, если увижу его.

ОБНОВЛЕНИЕ: опубликовал другой ответ, показывающий кодирование высокого уровня обсадной колонны с Boost ICL