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

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

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

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};

т.е.

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) ... но я не могу найти его полезным: \ Подумайте, что у меня есть миллионы пар двух векторов vec1 и vec2, и я стараюсь избежать вычисления накопленных векторов для каждой пары. Извините, если это неясно, но если я найду решение, я отвечу на этот досадный вопрос.

источник

2016-05-26 Erez Shmiel

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

Извините, забыли сказать, что мне нужны накопленные векторы для других вычислений в других функциях. Я просто пытаюсь задуматься о том, чтобы держать их в других структурах, чем вектор. Может быть, иначе, как hexa \ number (каким-то образом). Просто подумайте, что у меня есть миллионы пар, подобных этим –

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

Посмотрите на код ниже. Делает ли это то, что вы просите?

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; 
}

источник

2016-05-26 12:51:35 Hill

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

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; 
}

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

источник

2016-05-26 12:54:09

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

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; 
}

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

Live Demo

источник

2016-05-26 12:56:59 coyotte508

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

ответ

Смежные вопросы