Nano Hash - криптовалюты, майнинг, программирование

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

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

Например, (еще не накоплено)

vector<int> vec1 = {10, 30, 20, 40 };
vector<int> vec2 = {5, 10, 5, 8 };

наивный способ получить результат - сначала собрать их в новые векторы:

vector<int> accumulated_vec1 = {10, 10+30, 10+30+20, 10+30+20+40};
vector<int> accumulated_vec2 = {5, 5+10, 5+10+5, 5+10+5+8};

i.e:

accumulated_vec1 = {10,40,60,100};
accumulated_vec2 = {5,15,20,28};

Тогда результатом будет максимальное число между abs(accumulated_vec1[i]-accumulated_vec2[i]) и 0 ‹= i ‹= 3.

так что result = 72 (когда я == 3)

более быстрый способ может заключаться в представлении векторов 1 числом (даже 0,10302040)... но я не могу найти это полезным: \ Думаю, что у меня есть миллионы пар 2 векторов vec1 и vec2, и я пытаюсь избежать вычислений накопленные векторы для каждой пары.. извините, если не ясно, но если я найду решение, я отвечу на этот надоедливый вопрос.

c++ vector stl
26.05.2016

  • Это кажется очень простым... (вы можете вычислить накопление на лету, без необходимости сохранять его в другом векторе). Какие у вас проблемы? 26.05.2016
  • извините, забыл сказать, что накопленные векторы мне нужны для других вычислений в других функциях. Я просто пытаюсь думать о том, чтобы хранить их в других структурах, а не в векторе.. может быть, по-другому, например, в гекса\числе (каким-то образом).. Просто подумайте, что у меня есть миллионы пар, подобных этим. 26.05.2016
  • Ваш код уже довольно быстр, но убедитесь, что вы вызываете .reserve() для ваших накопленных векторов, чтобы избежать перераспределения, пока вы вставляете в него вещи (я предполагаю, что вы заполняете его внутри цикла в своем реальном коде). Если у вас есть много элементов, как вы только что сказали, это будет хорошей оптимизацией вашего кода. 26.05.2016
  • Я понятия не имею, что ваш вопрос на самом деле. Это как получить текущие частичные суммы в vectors? Или что? 26.05.2016
  • @ErezShmiel Я не очень понимаю твой вопрос. В вопросе вы говорите как если бы они были накоплены, предполагая, что вы ищете альтернативу, чтобы избежать накопления и копирования в другие векторы, затем в своем комментарии вы говорите, что вам нужны два накопленные векторы для других вещей. Если вам нужно, чтобы эти векторы присутствовали для других вычислений, нет никакого способа избежать вычисления этих векторов, верно? Если вам нужны эти данные, вы не можете пропустить этот шаг. Я запутался, что именно вам нужно. 26.05.2016
  • так что, возможно, есть другой способ представления накопленных векторов ... не с использованием векторов, а что-то более быстрое. думаю, что я мог бы представить вектор из 4 целых чисел как десятичное число, то есть 0,10304025 .. тогда я бы использовал миллионы десятичных чисел вместо миллионов векторов из 4 целых чисел. 26.05.2016

Ответы:


1

Самый быстрый способ...

int maxDiff(const vector<int> &v1, const vector<int> &v2) {
    int maxDiff(0), diff(0);

    for (auto it1 = v1.begin(), it2 = v2.begin(); it1 != v1.end() && it2 != v2.end(); ++it1, ++it2) {
        diff += *it1-*it2;
        maxDiff = max(abs(diff), maxDiff);
    }

    return maxDiff;
}

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

Демо

26.05.2016

2

Взгляните на код ниже. Это делает то, что вы просите?

vector<int> accumulated_vec;
accumulated_vec.resize(vec1.size());
accumulated_vec[0] = vec1[0] - vec2[0];

for(int i = 1; i < accumulated_vec.size(); i++)
{
    accumulated_vec[i] = accumulated_vec[i-1] + (vec1[i] - vec2[i]);
    cout << accumulated_vec[i] << endl;
}
26.05.2016

3

Вот моя версия для вашей проблемы

int getAccumulatedForIndex(int index, vector<int> &vec) {
    if (index == 0) {
        return vec.at(index);
    }
    return vec.at(index) + getAccumulatedForIndex(index - 1, vec);
}

и тогда

int getAccumulatedMax(vector<int> vec1, vector<int> vec2) {
    if (vec1.size() != vec2.size()) { // don't much each other
        return -1;
    }

    int max = -1;
    for (int i = 0; i < vec1.size(); ++i) {
        int currentMax = abs(getAccumulatedForIndex(i, vec1) - getAccumulatedForIndex(i, vec2));
        if (currentMax > max) {
            max = currentMax;
        }
    }

    return max;
}

надеюсь, это то, что ты хочешь

26.05.2016
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..