Эффективный способ расчета среднего значения по непересекающимся поддиапазонам карты STL

Question

Я конвертирую алгоритм из C # в C ++.Небольшой частью алгоритма является вычисление средних значений для определенных областей в словаре.

Данные в словаре хранятся следующим образом:

Index     Value
1         10
3         28
290       78
1110      90

Мне нужно вычислитьсреднее значение всех значений с индексом меньше определенного числа и всех значений индекса больше определенного числа.В C # я делаю это следующим образом:

if (dictionary.Where(x => x.Key < areaWidth).Count() > 0)
{
    avgValue = (int) dictionary.Where(x => x.Key < areaWidth).Average(
        x => x.Value);
}

for (var i = 0; i < line.Length; i++)
{
    if (i == areaWidth)
    {
        avgValue = -1;
        i = line.Length - areaWidth;
        var rightBorder = i - areaWidth;

        if (dictionary.Where(x => x.Key > (rightBorder)).Count() > 0)
        {
            avgValue = (int) dictionary.Where(
                x => x.Key > (rightBorder)).Average(
                                x => x.Value);
        }
    }

    if (line[i] < avgValue * 0.8)
    {
        reallyImportantValue += (avgValue - line[i]);
    }
}

Я знаю, что это не очень эффективный и довольно дурацкий код, но я знал, что мне все равно придется полностью переписать эту часть алгоритма в C ++,Я решил осуществить это быстро и грязно.

В любом случае, сейчас я переношу это на C ++, и потому что он будет работать на мобильной платформе, производительность очень важна.Имея ограниченные знания C ++ / STL, я, скорее всего, смогу выполнить работу, но результат, вероятно, будет намного хуже, чем код на C #.

Так что если вы знаете хороший и эффективный способ выполнения этой задачи в C ++Пожалуйста, скажите мне.

---

РЕДАКТИРОВАТЬ: Спасибо за все ваши ответы.Как я уже упоминал в своем посте, мои знания STL ограничены, поэтому мне очень трудно выбрать решение, тем более что существует множество разных мнений.Было бы здорово, если бы кто-то мог помочь мне с решением, сравнив решения, размещенные здесь.Чтобы дать вам немного больше справочной информации:

Функция будет вызываться примерно 500 раз с 1000 значениями на карте.Наиболее важным аспектом является стабильность, производительность является вторым по важности.

Answer 1

РЕДАКТИРОВАТЬ: однопроходный накопитель карт - result2 содержит необходимую информацию:

#include <map>
#include <algorithm>
#include <numeric>

typedef map<const unsigned int, unsigned int> Values;

struct averageMap
{
    averageMap() : lowerCount(0), lowerSum(0), upperSum(0) {}
    averageMap operator()(const averageMap& input, 
           const Values::value_type& current)
    {
        if (current.first > boundary)
        {
            upperSum += current.second;
        }
        else
        {
            lowerSum += current.second;
            ++lowerCount;
        }
        return *this;
    }

    static size_t boundary;
    size_t lowerCount;
    unsigned int lowerSum;
    unsigned int upperSum;
};

size_t averageMap::boundary(0);

struct averageRange
{
    averageRange() : count(0), sum(0) {}
    averageRange operator()(const averageRange& input, 
        const Values::value_type& current)
    {
        sum += current.second;
        ++count;

        return *this;
    }

    size_t count;
    unsigned int sum;
};


int main()
{
    Values values;

    values[1] = 10;
    values[3] = 28;
    values[290] = 78;
    values[1110] = 110;

    averageMap::boundary = 100;
    averageMap result = accumulate(values.begin(), values.end(), 
        averageMap(boundary), averageMap(boundary));

averageRange result2 = accumulate(values.lower_bound(2), values.upper_bound(300), 
    averageRange(), averageRange());

    return 0;
};

Старая версия:

Это работает для меня. Использование accumulate в диапазоне, полученном из map::upper_bound, было проблематичным, поскольку многие операции STL требуют, чтобы конечные итераторы были доступны из первого диапазона. Здесь есть немного обмана - при условии, что значения map> = 0.

#include <map>
#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;

typedef map<unsigned int, unsigned int> Values;

int main()
{
    Values values;

    values[1] = 10;
    values[3] = 28;
    values[290] = 78;
    values[1110] = 110;

    size_t boundary(100);
    Values::iterator iter = values.upper_bound(boundary);

    vector<int> lowerRange(values.size(), -1);

    transform(values.begin(), iter, lowerRange.begin(), 
        [](std::pair<unsigned int, unsigned int> p) 
                -> int { return p.second; });

    vector<int>::iterator invalid(find(lowerRange.begin(), 
        lowerRange.end(), -1));
    size_t lowerCount(distance(lowerRange.begin(), invalid));
    lowerRange.resize(lowerCount);

    vector<int> upperRange(values.size() - lowerCount);
    transform(iter, values.end(), upperRange.begin(), 
        [](std::pair<unsigned int, unsigned int> p) 
                -> int { return p.second; });

    size_t lowerAverage = accumulate(lowerRange.begin(), 
        lowerRange.end(), 0) / lowerRange.size();
    size_t upperAverage = accumulate(upperRange.begin(), 
        upperRange.end(), 0) / upperRange.size();

    return 0;
};

Answer 2

Вы можете использовать std::accumulate для вычисления суммы значений, а затем разделить на количество элементов. Вот несколько примеров того, как вычислить среднее и другую статистику с использованием STL.

Answer 3

• Вы находите свой диапазон с помощью std :: lower_bound и std :: upper_bound, разница в том, что lower_bound включает в себя ваше значение, поэтому вы получите первый итератор> = ваше значение, тогда как upper_bound даст вам первый итератор> твоя ценность Если ваше значение отсутствует на карте, они вернут тот же итератор.

• Вы можете использовать накопление, но вы не можете просто добавить пары std :: вместе, поэтому вам понадобится пользовательский функтор здесь, или использовать boost :: transform_iterator, или просто зациклить, как только вы найдете свои границы. Циклы не так злы, как это делают некоторые люди (а накапливать - один из самых ужасных алгоритмов).

Answer 4

Хорошо, вот мой план для тех, кто любит использовать накопление, чтобы сделать его немного менее болезненным.Давайте создадим класс с именем StatsCollector.Мне все равно, что там на самом деле, за исключением того, что мы предположим, что это класс, который вы будете использовать в разных местах вашего кода, который собирает наборы чисел и предоставит вам информацию.Давайте свободно определим это.Я предполагаю, что он принимает удвоенные значения в качестве значений, но вы можете шаблонировать его для value_type.

class StatsCollector
{
public:
   StatsCollector();

   void add(double val);

 // some stats you might want
   size_t count() const;
   double mean() const;
   double variance() const;
   double skewness() const;
   double kurtosis() const;
};

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

Теперь я напишу пользовательский функтор (вы могли бы использовать функцию) для нашего конкретногопетля.Я возьму указатель на один из вышеперечисленных.(Проблема со ссылкой заключается в том, что std :: аккумулировать присваивает ему, поэтому он будет копировать объект, который не является тем, что мы хотим. Это будет само-назначение, но самоопределение нашего указателя в значительной степени нет-op)

struct AddPairToStats
{
  template< typename T >
  StatsCollector * operator()( StatsCollector * stats, const T& value_type ) const
  { 
     stats->add( value_type.second );
     return stats;
  }
};

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

Теперь, предполагая, что у нас есть диапазон итераторов на нашей карте, мы можем использовать накопление следующим образом:

StatsCollector stats;
std::accumuluate( iterStart, iterEnd, &stats, AddPairToStats() );

И статистика будет готова для анализа.Обратите внимание, что вы можете настроить статистику для последующего использования в ее конструкторе, так что вы можете, например, установить флаги, чтобы не вычислять кубы / 4-ые степени, если вы не хотите, чтобы они вычисляли асимметрию и эксцесс (и даже не вычислять квадраты, если вы этого не сделаете).забота о дисперсии).

Answer 5

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

Очень простой код, который должен быть понятен на первый взгляд и который не создает временных контейнеров,Я лично предпочел бы такой подход по этим причинам.На самом деле это именно тот код, который я написал бы, если бы делал это сам, используя эту структуру данных.

int key = <whatever>;

std::map<int, int>::const_iterator it = map.begin(), end = map.end();

size_t num1 = 0;
long total1 = 0;

while (it != end && it->first < key) {
    total1 += it->second;
    ++num1;
    ++it;
}

size_t num2 = map.size() - num1;
long total2 = 0;

while (it != end) {
    total2 += it->second;
    ++it;
}

int avg_less = num1 > 0 ? total1 / num1 : 0;
int avg_greater_equal = num2 > 0 ? total2 / num2 : 0;

Я не вижу смысла находить конечный итератор для первого раздела, используя std::lower_bound до начала.В любом случае, вы будете ходить по карте, так что вы можете проверить, как вы идете.Итерация карты не является бесплатной и потенциально может немного подскочить в памяти - по сравнению с этим, дополнительное сравнение на каждой итерации не должно быть заметным.

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

Answer 6

В случае, если предикат является функцией сравнения карты, с которой вам лучше всего подходят std::map<>::lower_bound() и std::map<>::upper_bound(). Получите итератор, указывающий на соответствующую границу, и используйте его с std::accumulate() из <numeric>. Поскольку вы работаете с ассоциативным контейнером, вам нужно будет адаптироваться, принимая среднее значение, чтобы вы работали со значением second, а не с std::pair<>.

Если ваш предикат может измениться на что-то другое, вы можете использовать std::partition():

// tmp container: should be fast with std::distance()
typedef std::vector<int> seq;

seq tmp(dict.size());
seq::iterator end(std::partition(dict.begin(), dict.end(),
                                 tmp.begin(),
                                 std::bind2nd(std::tmp(), UPPER_BOUND)));

// std::vector works well with std::distance()
seq::difference_type new_count = std::distance(tmp.begin(), end);
double lower_avg = std::accumulate(tmp.begin(), end, 0.0) / new_count;
seq::difference_type new_count = std::distance(end, tmp.end());
double higher_avg = std::accumulate(tmp.begin(), end, 0.0) / new_count;

Здесь вам понадобятся заголовки <vector>, <algorithm>, <numeric>, <iterator> и <functional>.

Answer 7

Пары ключ-значение в std :: map сортируются по ключам - легко суммировать значения, обозначенные ключами, меньшими или большими, чем какое-либо значение, даже с циклом for (если вы не хотите использовать или учитесь использовать STLалгоритмы).Для ключей ниже некоторых value:

std::map<int, int> map;
map[...] = ...;

int count = 0, sum = 0;
for (std::map<int, int>::const_iterator it = map.begin();
     it != map.end() && it->first < value; ++it, ++count)
{
    sum += it->second;
}
// check for count == 0
int avg = sum / count; // do note integer division, change if appropriate

Для среднего значения ключей больше значения используйте map.rbegin() (типа std::map<...>::const_reverse_iterator), map.rend() и >.

edit: алгоритмы STL могут сделать код короче (то есть, где он используется).Например, для вычисления среднего значения ключей ниже value.

int ipsum(int p1, const std::pair<int, int>& p2) {
    return p1 + p2.second;
}

...

std::map<int, int> map;
int sum = std::accumulate(map.begin(), map.lower_bound(value), 0, ipsum);

Answer 8

примерно

• map::upper_bound / lower_bound, чтобы получить итератор для диапазона индекса
• accumulate для расчета суммы по диапазону (легко) и count для получения элементов

---

Это проходит через диапазон дважды (плохо масштабируется). Для оптимизации:

 struct RunningAverage
 {
     double sum;
     int count;
     RunningAverage() { sum = 0; count = 0; }
     RunningAverage & operator+=(double value) 
     { sum += value; ++count; }

     RunningAverage operator+(double value) 
     { RunningAverage result = *this; result += value; return result; }

     double Avg() { return sum / count; } 
 }

Который вы можете передать, чтобы накопить и счет, и сумму за один проход.

---

[редактировать] Согласно комментарию, вот обоснование для оптимизации:

• алгоритм O (N) без ограничения для N
• примитивные операции (обход и сложение узлов)
• возможна схема произвольного доступа

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

«Переменные» в этом обсуждении зависят только от набора данных и конфигурации клиентского компьютера, а не от алгоритма.

Я бы предпочел это решение вместо пользовательского «накопления», потому что его просто расширять или изменять для других операций, в то время как детали «накопления» остаются изолированными. Его также можно использовать с гипотетическим методом accumulate_p, который распараллеливает доступ (вам также понадобится оператор struct + struct, но это просто).

О, а правильность const оставлена ​​читателю в качестве упражнения:)