Самый быстрый способ перебора в векторе C ++

Question

Самый быстрый способ перебора в векторе C ++

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

Моя функция работает нормально, за исключением того, что она не покрывает ограничение по времени, которое составляет 500 мс.
я чувствую, что есть лучший способ перебрать два вектора для циклов, но я чувствую себя очень застрявшим …

bool sumOfTwo(std::vector<int> a, std::vector<int> b, int v) {
if((a.empty()) || b.empty()){
return false;
}
for (std::vector<int>::iterator it1 = a.begin(); it1<=a.end(); ++it1)     {
for (std::vector<int>::iterator it2 = b.begin(); it2<=b.end(); ++it2) {
if ((*it1 + *it2) == v){
return true;
}
}
}
return false;
}

-3

c++iteration time-limiting vector

Решение

Другие решения

Что касается только советов по стилю, измените ваш код на следующий (для эффективности и аккуратности)

bool sumOfTwo(const std::vector<int>& a, const std::vector<int>& b, int v) {
for (auto i1 : a)     {
for (auto i2 : b) {
if ((i1 + i2) == v){
return true;
}
}
}
return false;
}

Рассмотрите возможность использования std::unordered_set и перекрестные ссылки, чтобы найти, возможна ли сумма для максимальной эффективности. Помните, что поиск в std::unordered_set О (1)

5

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

bool sumOfTwo(std::vector<int>& a, std::vector<int>& b, int v) {
if((a.empty()) || b.empty()){
return false;
}
std::unordered_set<int> s;
for (const auto i : a) {
s.insert(v-i);
}
for (const auto i : b) {
auto search = s.find(i);
if (search != s.end()) {
return true;
}
}
return false;
}

2

Источник

Accepted Answer

В настоящее время вы перебираете два вектора, но вы делаете вложенными итерация. Давайте назовем длины векторов m а также n (произвольно). Ваш текущий алгоритм O (n * m), который довольно медленный для больших векторов.

Если m = n = 1000, в худшем случае (никакие два элемента не суммируют v), ты делаешь миллионы операций — вот так!

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

Псевдокод это:

if a.empty or b.empty:
return false

set = emptySet

for e in a:
set.add(v - e)

for e in b:
if e in set:
return true

return false

Поиск в неупорядоченном наборе должен быть O (1), так что теперь это алгоритм O (max (m, n)), где m — это длина a а n это длина b,

Если m = n = 1000, в худшем случае вы выполняете тысячи операций — намного лучше, верно?

Реализация этого в C ++ оставлена читателю. 🙂

Подсказка: передача по ссылке — хорошая идея для векторов.

3