Получение максимального значения в массиве


Есть функция, которая получает максимальное значения каждой period-длина интервала в массиве. Я пытаюсь оптимизировать эту функцию по производительности.

void maximumsT(const std::vector<double> &src, size_t period, std::vector<double> &dst)
{
    dst.resize(src.size());

    for (size_t i = 1; i <= period; ++i) {
        dst[i - 1] = *std::max_element(src.begin(), src.begin() + i);
    }

    for (size_t i = period; i <= src.size(); ++i) {
        dst[i - 1] = *std::max_element(src.begin() + i - period, src.begin() + i);
    }
}

Я задал этот вопрос так
и получил это решение.

Затем я попытался реализовать решение.

#include <vector>
#include <deque>
#include <algorithm>

void maximumsT(const std::vector<double> &src, size_t period, std::vector<double> &dst)
{
    dst.resize(src.size());

    for (size_t i = 1; i <= period; ++i) {
        dst[i - 1] = *std::max_element(src.begin(), src.begin() + i);
    }

    for (size_t i = period; i <= src.size(); ++i) {
        dst[i - 1] = *std::max_element(src.begin() + i - period, src.begin() + i);
    }
}

void maximums(const std::vector<double> &src, size_t period, std::vector<double> &dst)
{
    dst.resize(src.size());
    std::deque<std::pair<size_t, double>> deq;

    for (size_t i = 0; i < src.size(); ++i) {
        if (!deq.empty() && i >= period && deq.front().first <= i - period) {
            deq.pop_front();
        }

        while (!deq.empty() && deq.back().second < src[i]) {
            deq.pop_back();
        }

        deq.push_back(std::make_pair(i, src[i]));
        dst[i] = deq.front().second;
    }
}

bool test()
{
    std::vector<double> v(1 + rand() % 1000);
    for (double &e : v) {
        e = (double)rand() / RAND_MAX;
    }

    size_t period = 1 + (rand() % v.size());
    std::vector<double> vv, vvv;

    maximumsT(v, period, vv);
    maximums (v, period, vvv);

    return vv == vvv;
}

bool test(size_t iterations)
{
    for (size_t i = 0; i < iterations; ++i) {
        if (!test()) {
            return false;
        }
    }

    return true;
}

int main(int argc, char *argv[])
{
    return test(10000);
}

Как я могу улучшить и оптимизировать этот код?



169
3
задан 31 марта 2018 в 11:03 Источник Поделиться
Комментарии
2 ответа

Код в maximums делает то, что он должен делать, исходя из этого такой вопрос. У меня есть несколько замечаний по поводу других краях.

Не используйте один переменные письмо. Используйте имена, которые что-то говорят.
Так нет v, vv, vvv.

Еще одна проблема именования, ваши две функции максимумы делать то же самое, но с другим подходом, вы можете уточнить в названии. Они оба используют Т=период, так что это не отличительный. Может быть, использовать тот факт, что использовать дека или что один простой вариант.

Вы создаете двойной векторов в тесте, а затем передать их maximums например. Нет абсолютно никаких причин для test для их создания. Давайте maximums создать вектор, так как он должен его, а затем вернуть его. Некоторые для maximumsT.

Ваш maximumsT не интуитивно понятный. Нет необходимости делать двойную петлю.
Почему вы изменили своей реализации, как в вашем вопросе так? Там было гораздо лучше.
А именно

for (size_t i = period; i <= v.size(); ++i) {
vv[i - 1] = *std::max_element(v.begin() + i - period, v.begin() + i);
}

Код не будет быстрее или сэкономить пространство, но короче и яснее.

Инициализация случайных векторов для тестирования против, можно сделать в отдельной функцией. Я бы сделала тест и параметризована вектор источника.

Мое предложение:

#include <vector>
#include <deque>
#include <algorithm>

std::vector<double> maximumsT(const std::vector<double> &src, size_t period)
{
std::vector<double> dst(src.size());

for (size_t i = period; i <= v.size(); ++i) {
vv[i - 1] = *std::max_element(v.begin() + i - period, v.begin() + i);
}
return dst;
}

std::vector<double> maximums(const std::vector<double> &src, size_t period)
{
std::vector<double> dst(src.size());
std::deque<std::pair<size_t, double>> deq;

for (size_t i = 0; i < src.size(); ++i) {
if (!deq.empty() && i >= period && deq.front().first <= i - period) {
deq.pop_front();
}

while (!deq.empty() && deq.back().second < src[i]) {
deq.pop_back();
}

deq.push_back(std::make_pair(i, src[i]));
dst[i] = deq.front().second;
}
return dst;
}

std::vector<double> randomVect()
{
std::vector<double> v(1 + rand() % 1000);
for (double &e : v) {
e = (double)rand() / RAND_MAX;
}
return v
}
bool compareMaximums(std::vector<double> v, size_t period)
{
return maximumsT(v, period) == maximums(v, period);
}

bool test(size_t iterations)
{
for (size_t i = 0; i < iterations; ++i) {
std::vector<double> srcVec = randomVect();
size_t period = 1 + (rand() % srcVec.size());
if (!compareMaximums(srcVec, period)) {
return false;
}
}

return true;
}

int main(int argc, char *argv[])
{
return test(10000);
}

4
ответ дан 31 марта 2018 в 01:03 Источник Поделиться

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

Наиболее эффективный алгоритм для этой проблемы был предложен в 1992 и 1993 годах, независимо от Ван Герк, и Гил и Верманом. Этот алгоритм должен именно 3 сравнения в пробе, независимо от размера period.

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

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

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

Я думаю, вы могли бы даже сделать версию, где временные массивы длины 2*period, но это будет сложнее в реализации.


  • Ван Герк, "быстрый алгоритм локального минимума и максимума фильтров на прямоугольных и восьмиугольных ядра", распознавание букв 13(7):517-521, 1992 (Дой)

  • Гил, Верманом, "вычислительная техника 2-х мин, медиана и Макс фильтров", стандарта IEEE сделок на шаблон анализа и искусственного интеллекта 15(5):504-507 , 1993 (Дои)

  • Гил, Киммел, "эффективная дилатация, эрозия, Открытие и закрытие алгоритмы", стандарта IEEE сделок на шаблон анализа и искусственного интеллекта 24(12):1606-1617, 2002 (Дои)

2
ответ дан 1 апреля 2018 в 05:04 Источник Поделиться