Searching Multiple Vectors

Question

I have 4 vectors with about 45,000 records each right now. Looking for an efficient method to run through these 4 vectors and output how many times it matches the users input. Data needs to match on the same index of each vector.

Multiple for loops? Vector find?

Thanks!

Answer 1

What I got from description is that, you have 4 vectors and lots of user data, you need to find out how many of times it matches with vectors at same index so here goes the code ( i am writing a c++4.3.2 code)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    vector<typeT>a;  
    vector<typeT>b;
    vector<typeT>c;
    vector<typeT>d;
    vector<typeT>matched;
    /*i am assuming you have initialized a,b,c and d;
    now we are going to do pre-calculation for matching user data and store
    that in vector matched */
    int minsize=min(a.size(),b.size(),c.size(),d.size());
    for(int i=0;i<minsize;i++)
    {
        if(a[i]==b[i]&&b[i]==c[i]&&c[i]==d[i])matched.push_back(a[i]);
    }
    return 0;
}

this was the precalculation part. now next depend on data type you are using, Use binary search with little bit of extra counting or using a better data structure which stores a pair(value,recurrence) and then applying binary search. Time complexity will be O(n+n*log(n)+m*log(n)) where n is minsize in code and m is number of user input

Answer 2

You can create a lookup table for the vector with std::unordered_multimap in O(n). Then you can use unordered_multimap::count() to get the number of times the item appears in the vector and unordered_multimap::equal_range() to get the indices of the items inside your vector.

std::vector<std::string> a = {"ab", "ba", "ca", "ab", "bc", "ba"};
std::vector<std::string> b = {"fg", "fg", "ba", "eg", "gf", "ge"};
std::vector<std::string> c = {"pq", "qa", "ba", "fg", "de", "gf"};

std::unordered_multimap<std::string,int> lookup_table;

for (int i = 0; i < a.size(); i++) {
    lookup_table.insert(std::make_pair(a[i], i));
    lookup_table.insert(std::make_pair(b[i], i));
    lookup_table.insert(std::make_pair(c[i], i));
}

// count
std::string userinput;
std::cin >> userinput;
int count = lookup_table.count(userinput);
std::cout << userinput << " shows up " << count << " times" << std::endl;

// print all the places where the key shows up
auto range = lookup_table.equal_range(userinput);
for (auto it = range.first; it != range.second; it++) {
    int ind = it->second;
    std::cout << " " << it->second << " " 
        << a[ind] << " " 
        << b[ind] << " " 
        << c[ind] << std::endl;
}

This will be the most efficient if you will be searching the lookup table many items. If you only need to search one time, then Dietmar Kühl's approach would be most efficient.

Answer 3

Honestly, I would have a couple of methods to maintain your database(vectors).

Essentially, do a QuickSort to start out with.

Then ever so often consistently run a insertion sort (Faster then QuickSort for partially sorted lists)

Then just run binary search on those vectors.

---

edit:

I think a better way to store this is instead of using multiple vectors per entry. Have one class vector that stores all the values. (your current vectors)

class entry { 

public: 
      variable data1;
      variable data2;
      variable data3;
      variable data4;
}

Make this into a single vector. Then use my method I described above to sort through these vectors.

You will have to sort through by what type of data it is first. Then after call binary search on that data.

Answer 4

If the elements need to match at the same location, it seems that a std::find() or std::find_if() combined with a check for the other vectors at the position is a reasonable approach:

std::vector<A> a(...);
std::vector<B> b(...);
std::vector<C> c(...);
std::vector<D> d(...);

std::size_t match(0);
for (auto it = a.begin(), end = a.end(); it != end; ) {
    it = std::find_if(it, end, conditionA));
    if (it != end) {
        if (conditionB[it - a.begin()]
         && conditionC[it - a.begin()]
         && conditionD[it - a.begin()]) {
            ++match;
        }
        ++it;
    }
}