Найти медианную в движущемся окне фиксированного размера вдоль длинной последовательности данных

Ответ 1

O (n * lg m) легко:

Просто сохраните свое окно как два std::set s, один для нижней половины, один для верхней половины. Вставка нового элемента стоит O (lg m), поиск и удаление старого элемента стоит одинаково. Определение медианы с использованием метода, описанного в вашем вопросе, стоит O (1).

Когда вы перемещаете окно над своей последовательностью, на каждой итерации вы удаляете элемент, выпавший из окна (O (lg m)), вставьте новый элемент (O (lg m)) и вычислите медианную (O ( 1)), что приводит к сумме O (n lg m).

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

Ответ 2

Я реализовал почти точно описанный здесь алгоритм: http://ideone.com/8VVEa и описал его здесь: Режимы медианного в реализации C - Turlach

Способ обойти проблему "найти самый старый" - сохранить значения в круговом буфере, поэтому у вас всегда есть указатель на самый старый. То, что вы храните в куче, - это индексы буфера. Таким образом, требуется 2M, а каждое обновление - O (lg M).

Ответ 3

Тот же ответ, что и hc_, но вместо использования запаса BST используйте версию, в которой каждый node имеет количество элементов в этом поддереве. Таким образом, поиск медианы - это O (log (m)).

Ответ 4

Я дал этот ответ для вопроса "прокатки медианного в С"

Я не смог найти современную реализацию структуры данных С++ с порядковой статистикой, поэтому в итоге она реализовала обе идеи в ссылке верхнего кодера (Match Editorial: прокрутите вниз до FloatingMedian).

Два мультисети

Первая идея разделяет данные на две структуры данных (кучи, мультимножества и т.д.) с O (ln N) на вставку/удаление, не позволяет динамически изменять квантиль без больших затрат. То есть мы можем иметь скользящую медианную или прокатывающую 75%, но не обе в то же время.

Дерево сегментов

Вторая идея использует дерево сегментов, которое является O (ln N) для вставки/удаления/запросов, но более гибкое. Лучше всего "N" - это размер вашего диапазона данных. Так что, если у вашей скользящей медианной есть окно из миллиона предметов, но ваши данные варьируются от 1..65536, тогда требуется только 16 операций за одно движение подвижного окна в 1 миллион! (И вам нужны только байты размером 65536 * sizeof (counting_type), например 65536 * 4).

Статистика статистики заказа GNU

Как раз перед тем, как сдаться, я обнаружил, что stdlibС++ содержит деревья статистики заказов!!!

Они имеют две критические операции:

iter = tree.find_by_order(value)
order = tree.order_of_key(value)

См. libstdС++ manual policy_based_data_structures_test (поиск "split and join" ).

Я обернул дерево для использования в заголовке удобства для компиляторов, поддерживающих частичные типы typedefs С++ 0x/С++ 11:

#if !defined(GNU_ORDER_STATISTIC_SET_H)
#define GNU_ORDER_STATISTIC_SET_H
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// A red-black tree table storing ints and their order
// statistics. Note that since the tree uses
// tree_order_statistics_node_update as its update policy, then it
// includes its methods by_order and order_of_key.
template <typename T>
using t_order_statistic_set = __gnu_pbds::tree<
                                  T,
                                  __gnu_pbds::null_type,
                                  std::less<T>,
                                  __gnu_pbds::rb_tree_tag,
                                  // This policy updates nodes'  metadata for order statistics.
                                  __gnu_pbds::tree_order_statistics_node_update>;

#endif //GNU_ORDER_STATISTIC_SET_H

Ответ 5

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

Это реализует следующую структуру данных:

|-------------------------------|
|---------------|---------------|
|-------|-------|-------|-------|
|---|---|---|---|---|---|---|---|
  0   1   2   3   4   5   6   7  

Каждый сегмент хранит количество элементов подсчета в диапазоне, который он охватывает. Я использую 2N сегменты для диапазона значений от 1..N. Они помещаются в один развернутый вектор, а не в формат дерева, показанный фигурально выше.

Итак, если вы вычисляете скользящие медианы по набору целых чисел, которые варьируются от 1..65536, тогда вам нужно только 128kb для их хранения и может вставлять/удалять/запрашивать с помощью O (ln N), где N = размер диапазона, т.е. 2 ** 16 операций.

Это большой выигрыш, если диапазон данных намного меньше, чем ваше окно.

#if !defined(SEGMENT_TREE_H)
#define SEGMENT_TREE_H
#include <cassert>
#include <array>
#include <algorithm>
#include <set>

#ifndef NDEBUG
#include <set>
#endif

template<typename COUNTS, unsigned BITS>
class t_segment_tree
{
    static const unsigned                       cnt_elements    = (1 << BITS);
    static const unsigned                       cnt_storage     = cnt_elements << 1;
    std::array<COUNTS, cnt_elements * 2 - 1>    counts;
    unsigned                                    count;

#ifndef NDEBUG
    std::multiset<unsigned>                     elements;
#endif
    public:

    //____________________________________________________________________________________

    //  constructor

    //____________________________________________________________________________________
    t_segment_tree(): count(0)
    {
        std::fill_n(counts.begin(), counts.size(),  0);
    }
    //~t_segment_tree();

    //____________________________________________________________________________________

    //  size

    //____________________________________________________________________________________
    unsigned size() const  { return count; }

    //____________________________________________________________________________________

    //  constructor

    //____________________________________________________________________________________
    void insert(unsigned x)
    {
#ifndef NDEBUG
        elements.insert(x);
        assert("...............This element is too large for the number of BITs!!..............." && cnt_elements > x);
#endif
        unsigned ii = x + cnt_elements;
        while (ii)
        {
            ++counts[ii - 1];
            ii >>= 1;
        }
        ++count;
    }

    //____________________________________________________________________________________

    //  erase 

    //      assumes erase is in the set
    //____________________________________________________________________________________
    void erase(unsigned x)
    {
#ifndef NDEBUG
        // if the assertion failed here, it means that x was never "insert"-ed in the first place
        assert("...............This element was not 'insert'-ed before it is being 'erase'-ed!!..............." && elements.count(x));
        elements.erase(elements.find(x));
#endif
        unsigned ii = x + cnt_elements;
        while (ii)
        {
            --counts[ii - 1];
            ii >>= 1;
        }
        --count;
    }

    // 
    //____________________________________________________________________________________

    //  kth element

    //____________________________________________________________________________________
    unsigned operator[](unsigned k)
    {
        assert("...............The kth element: k needs to be smaller than the number of elements!!..............." && k < size());
        unsigned ii = 1;
        while (ii < cnt_storage)
        {
            if (counts[ii - 1] <= k)
               k -= counts[ii++ - 1];
            ii <<= 1;
        }
        return (ii >> 1) - cnt_elements;
    }

};
#endif