Как рекурсивно объединять очереди в C ++? Предположим, они уже отсортированы - PullRequest
Новая
       11

Как рекурсивно объединять очереди в C ++? Предположим, они уже отсортированы

0 голосов
/ 09 мая 2020

Просто пытаюсь понять это концептуально

Ответы [ 2 ]

0 голосов
/ 09 мая 2020

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

Первый вызов recMultiMerge имеет 6 очередей. left будет первыми тремя ({3, 6, 9, 9, 100}, {1, 5, 9, 9, 12}, {5}), а right будет последними тремя ({}, {-5, -5}, {3402}).

Затем вы выполните рекурсивный вызов с помощью left. В этом вызове all.size() будет 3. left будет иметь одну очередь ({3, 6, 9, 9, 100}), а right также будет иметь только одну очередь ({1, 5, 9, 9, 12}). (Я предполагаю, что второй параметр Vector.subList - это счетчик.) Это остановится на втором, если потому что left.size() == 1. Результатом будет эта первая очередь.

Теперь мы вернулись к первому рекурсивному вызову (потеряв 2-ю и 3-ю очереди), и мы снова запускаем рекурсивный вызов с помощью right (который имеет 3 очереди в этом). Это будет продолжаться так же, как и последний вызов, возвращая первую очередь (которая в данном случае пуста) и теряет две другие.

Затем вы объединяете эти две очереди ({3, 6, 9, 9, 100} и {}), в результате чего в вашем ответе: {3, 6, 9, 9, 100}.

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

0 голосов
/ 09 мая 2020

Я бы начал с двоичного сворачивания. 

template<class X, class Op>
X binary_fold( span<X> elems, Op op );

или std::vector<X>, но я предпочитаю span для этого.

Он разбивает elems на две части, затем либо рекурсирует, либо вызывает op на нем.

Затем вы можете протестировать binary_fold с отладочным кодом, который просто каким-то образом распечатывает части слева / справа, и вы можете увидеть, как рекурсия разыгрывается .

Получив это, вы снова подключаете свою программу merge, и она должна работать.

Живой пример .

Полный код : 

template<class X>
struct span {
    X* b = 0;
    X* e = 0;
    X* begin() const { return b; }
    X* end() const { return e; }

    std::size_t size() const { return end()-begin(); }
    X& front() const { return *begin(); }
    X& back() const { return *(end()-1); }
    X* data() const { return begin(); }
    bool empty() const { return size()==0; }


    span( X* s, X* f ):b(s),e(f) {}
    span() = default;
    span( X* s, std::size_t l ):span(s, s+l) {}

    span( std::vector<X>& v ):span( v.data(), v.size() ) {}

    template<std::size_t N>
    span( X(&arr)[N] ):span(arr, N) {}
    template<std::size_t N>
    span( std::array<X, N>& arr ):span(arr.data(), N) {}

    span except_front( std::size_t n = 1 ) const {
        n = (std::min)(n, size());
        return {begin()+n, end()};
    }
    span only_front( std::size_t n = 1 ) const {
        n = (std::min)(n, size());
        return {begin(), begin()+n};
    }
    span except_back( std::size_t n = 1 ) const {
        n = (std::min)(n, size());
        return {begin(), end()-n};
    }
    span only_back( std::size_t n = 1 ) const {
        n = (std::min)(n, size());
        return {end()-n, end()};
    }
};


template<class X, class Op>
X binary_fold( span<X> elems, Op op ) {
    if (elems.empty()) return {};
    if (elems.size() == 1) return elems.front();

    auto lhs = binary_fold( elems.only_front( elems.size()/2 ), op );
    auto rhs = binary_fold( elems.except_front( elems.size()/2 ), op );
    return op(std::move(lhs), std::move(rhs));
}
...