maximizing efficiency

[chhe]

I've written a program that compares two vectors A and B to see at which locations A equals B. The problem is that the program is prohibitively time consuming when the vectors A and B become very long. Does anyone know of a more efficient and less time consuming way of doing this? Below is a simplified version of the program to show what I mean. The only way I can think to do it is to compare every element of vector A to every element of vector B.

#include <iostream>
#include <vector>

using namespace std;

 int main()
 {
int i,j;
vector<int> A;
A.push_back(2);
A.push_back(234);
A.push_back(45);
A.push_back(7);
A.push_back(8);
A.push_back(200);
vector<int> B;
B.push_back(8);
B.push_back(2);
B.push_back(45);
B.push_back(200);
B.push_back(7);
B.push_back(234);
vector<int> Location;

 for(size_t i=0;i<A.size();i++)
 {
     for(size_t j=0;j<B.size();j++)
     {
      if(A[i]==B[j])
      {
          Location.push_back(j);
          j=B.size()+1;
      }
     }
 }
 return 0;
 }

[Yay295]

#include <vector>

int main ( )
{
    std::vector<int> A;
    A.push_back(2);
    A.push_back(234);
    A.push_back(45);
    A.push_back(7);
    A.push_back(8);
    A.push_back(200);

    std::vector<int> B;
    B.push_back(8);
    B.push_back(2);
    B.push_back(45);
    B.push_back(200);
    B.push_back(7);
    B.push_back(234);
    
    const size_t aSize = A.size ( ), bSize = B.size ( );

    std::vector<int> Location ( aSize, -1 );


    for ( size_t i = 0 ; i < aSize; ++i )
    {
        for( size_t j = 0; j < bSize; ++j )
        {
            if( A[i] == B[j] )
            {
                Location[i] = j;

                break;
            }
        }
    }
}

In your for loops, the size function is called every time it loops. By saving the size as a const before the loop, it doesn't have to do this.

For reasons, ++X is technically faster than X++. Will it actually make a difference? I don't know.

Every time you call push_back, it has to resize the vector. You already know the size at the beginning though, so just set it once.

I can see how "j=B.size()+1" would work, but the keyword you want is "break".

[Hippogriff]

^ All true

However seeing as you are looping over the same vector several times you will probably want to sort it once first then just use some sort of binary search (linear time vs log time).

Are you sure you need the exact position stored every time there is a match? That gets rid of some faster solutions like unordered_set and the standard binary_search wont help.

I would probably do something like this.

#include <vector>
#include <algorithm>

using std::vector;

int main()
{
	vector<int> A;
	vector<int> B;

	//Insert Data

	sort(B.begin(), B.end());  // Sort vector 

	for (auto Element : A)   // C++11, Use regular for loop otherwise 
	{
		// Returns iterator to first number that is greater or equal to.  Would normally use binary_search but you want index
		auto it = lower_bound(B.begin(), B.end(), Element);

		if (it != B.end())  // make sure it found something
		{
			if (*it == Element)  // if exactly equal 
			{
				int Position = distance(B.begin(), it);  // get index from iterator
				// Store position 
			}
		}
	}
}

Functions used from:
http://www.cplusplus.com/reference/algorithm/
http://www.cplusplus.com/reference/algorithm/sort/

[JLBorges]

O(N) time, O(N) space

#include <iostream>
#include <vector>
#include <unordered_map>

int main()
{
    const std::vector<int> a { 2, 234, 45, 99, 7, 8, 200 } ; // 99 is not present in b

    const std::vector<int> b { 8, 2, 45, 200, 7, 234 } ; //
    std::unordered_map< int, std::size_t > pos_map ; // map values in b to their positions
    for( std::size_t i = 0 ; i < b.size() ; ++i ) pos_map.emplace( b[i], i ) ; // O(N) time, O(N) space

    constexpr std::size_t npos = -1U ; // npos => invalid position
    std::vector<std::size_t> Location( a.size(), npos ) ;  // npos => value is not present in b

    for( std::size_t i = 0 ; i < a.size() ; ++i  ) // O(N)
    {
        const auto iter = pos_map.find( a[i] ) ; // look up its position in b - O(1)
        if( iter != pos_map.end() ) Location[i] = iter->second ; // if the value is in b
    }

    for( std::size_t pos : Location )
    {
        if( pos != npos ) std::cout << pos << ' ' ;
        else std::cout << "npos " ;
    }
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/13a2e902cd9ecf1f

[chhe]

I don't intend to muddy the waters, but what if the vectors A and B were of type string instead of int? Such that A and B stored various words. Would the suggestions for code listed above still work?

Are you sure you need the exact position stored every time there is a match?
Essentially I need to know the value of B at that location everytime there is a match. Knowing the position is equivalent for my purposes.

[Yay295]

JLBorges' and my code would work with strings, but James2250's code uses lower_bound and I'm not sure if that function works with strings or not.

[dhayden]

Don't use vectors. Copy the elements of a into a set. Then for each element in b, see if it's in a.