Эффективный способ получить среднее (среднее) значение std:: set?

Ответ 1

В зависимости от того, как часто вы вставляете/удаляете элементы или просматриваете среднюю/медианную, возможно более эффективное решение, чем очевидное, - поддерживать постоянный итератор в среднем элементе и обновлять его всякий раз, когда вы вставляете/удаляете элементы из задавать. Есть куча краевых случаев, которые потребуют обработки (нечетное число против четного количества элементов, удаление среднего элемента, пустой набор и т.д.), Но основная идея заключалась бы в том, что когда вы вставляете элемент, который меньше, чем текущий средний элемент, ваш средний итератор может нуждаться в декрементах, тогда как если вы вставляете большую, вам нужно увеличивать. Это наоборот для удаления.

При времени поиска это, конечно, O (1), но также имеет существенно O (1) стоимость при каждой вставке/делеции, то есть O (N) после N вставок, которая должна быть амортизирована на достаточном количество поисковых запросов, чтобы сделать его более эффективным, чем принудительное принуждение.

Ответ 2

Это будет O (размер), чтобы получить середину двоичного дерева поиска. Вы можете получить его с помощью std::advance() следующим образом:

std::set<int>::iterator it = s.begin();
std::advance(it, s.size() / 2);

Ответ 3

Имейте в виду, что std::set НЕ хранит повторяющиеся значения. Если вы вставите следующие значения {1, 2, 3, 3, 3, 3, 3, 3, 3}, медиана, которую вы получите, будет 2.

std::set<int>::iterator it = s.begin();
std::advance(it, s.size() / 2);
int median = *it;

Если вы хотите включить дубликаты при рассмотрении медианы, вы можете использовать std::multiset (медиана {1, 2, 3, 3, 3, 3, 3, 3, 3} будет равна 3):

std::multiset<int>::iterator it = s.begin();
std::advance(it, s.size() / 2);
int median = *it;

Если единственная причина, по которой вы хотите отсортировать данные, это получить медиану, std::sort на мой взгляд, вам лучше использовать простой старый std::vector + std::sort.

С большим тестовым образцом и несколькими итерациями я выполнил тест за 5 секунд с помощью std::vector и std::sort и с 13 по 15 с использованием std::set или std::multiset. Ваш пробег может варьироваться в зависимости от размера и количества повторяющихся значений.

Ответ 4

Это предложение является чистой магией и потерпит неудачу, если будут какие-то дубликаты

В зависимости от того, как часто вы вставляете/удаляете элементы по сравнению с поиском среднего/медианы, возможно, более эффективным решением, чем очевидное, является сохранение постоянного итератора для среднего элемента и его обновление всякий раз, когда вы вставляете/удаляете элементы из набора. Существует множество крайних случаев, которые необходимо обработать (нечетное или четное количество элементов, удаление среднего элемента, пустой набор и т.д.), Но основная идея заключается в том, что при вставке элемента, который меньше текущего среднего элемента ваш средний итератор может нуждаться в уменьшении, тогда как если вы вставляете больший итератор, вам нужно увеличивать его. Это наоборот для переездов.

Предложения

1. Первое предложение заключается в использовании std :: multiset вместо std :: set, чтобы он мог хорошо работать, когда элементы могут быть продублированы.
2. Я предлагаю использовать 2 мультимножества, чтобы отслеживать меньшее зелье и большее зелье и балансировать между ними

Алгоритм

1. сохранить наборы сбалансированными, чтобы size_of_small == size_of_big или size_of_small + 1 == size_of_big

void balance(multiset<int> &small, multiset<int> &big)
{
    while (true)
    {
        int ssmall = small.size();
        int sbig = big.size();

        if (ssmall == sbig || ssmall + 1 == sbig) break; // OK

        if (ssmall < sbig)
        {
            // big to small
            auto v = big.begin();
            small.emplace(*v);
            big.erase(v);
        }
        else 
        {
            // small to big
            auto v = small.end();
            --v;
            big.emplace(*v);
            small.erase(v);
        }
    }
}

2. если наборы сбалансированы, средний элемент всегда является первым элементом в большом наборе

auto medium = big.begin();
cout << *medium << endl;

3. будьте осторожны при добавлении нового элемента

auto v = big.begin();
if (v != big.end() && new_item > *v)
    big.emplace(new_item );
else
    small.emplace(new_item );

balance(small, big);

сложность объяснила

• это O (1), чтобы найти среднее значение
• добавить новый предмет занимает O (n)
• вы все еще можете искать предмет в O (log n), но вам нужно искать 2 комплекта

Ответ 5

Если ваши данные являются статическими, то вы можете его заранее определить и не вставлять новые элементы - проще использовать вектор, сортировать его и получать доступ к медианному только по индексу в O (1)

vector<int> data;
// fill data
std::sort(data.begin(), data.end());
auto median = data[data.size() / 2];