Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am trying find the number of unique elements in a vector compared against multiple vectors using C++. The vectors are in sorted order and it can be of size 2,000,000.

Suppose I have,

v1: 5, 8, 13, 16, 20
v2: 2, 4, 6, 8
v3: 20
v4: 1, 2, 3, 4, 5, 6, 7
v5: 1, 3, 5, 7, 11, 13, 15

The number of unique elements in v1 is 1 (i.e. number 16).

I tried two approaches.

  1. Added vectors v2,v3,v4 and v5 into a vector of vector. For each element in v1, checked if the element is present in any of the other vectors.

  2. Combined all the vectors v2,v3,v4 and v5 using merge sort into a single vector and compared it against v1 to find the unique elements.

Note: sample_vector = v1 and all_vectors_merged contains v2,v3,v4,v5

//Method 1
unsigned int compute_unique_elements_1(vector<unsigned int> sample_vector,vector<vector<unsigned int> > all_vectors_merged)
{
    unsigned int duplicate = 0;
    for (unsigned int i = 0; i < sample_vector.size(); i++)
    {
        for (unsigned int j = 0; j < all_vectors_merged.size(); j++)
        {
            if (std::find(all_vectors_merged.at(j).begin(), all_vectors_merged.at(j).end(), sample_vector.at(i)) != all_vectors_merged.at(j).end())
            {
                duplicate++;
            }
        }
    }
    return sample_vector.size()-duplicate;
}

// Method 2
unsigned int compute_unique_elements_2(vector<unsigned int> sample_vector, vector<unsigned int> all_vectors_merged)
{
    unsigned int unique = 0;
    unsigned int i = 0, j = 0;
    while (i < sample_vector.size() && j < all_vectors_merged.size())
    {
        if (sample_vector.at(i) > all_vectors_merged.at(j))
        {
            j++;
        }
        else if (sample_vector.at(i) < all_vectors_merged.at(j))
        {
            i++;
            unique ++;
        }
        else
        {
            i++;
            j++;
        }
    }
    if (i < sample_vector.size())
    {
        unique += sample_vector.size() - i;
    }
    return unique;
}

Of these two techniques, I see that Method 2 gives faster results.

1) Method 1: Is there a more efficient way to find the elements than running std::find on all the vectors for all the elements in v1.

2) Method 2: Extra overhead in comparing vectors v2,v3,v4,v5 and sorting them.

How can I do this in a better way?

[edit] Vectors are in sorted order.

share|improve this question
3  
Use the standard std::set_difference –  Loki Astari Sep 3 '12 at 21:18
    
You may gain some speed if you use Binary Search in your method 2.if your numbers are small (as in the example) you could calculate the product of elements of each vector. You could then multiply the 4 products to get 1 number. For each element in the first vector, divide the product by the value of that v1 element. If you get a nonzero remainder, the the number is unique. –  Emmad Kareem Sep 3 '12 at 22:43
    
@EmmadKareem thanks for the suggestion. But my vectors hold string values. So I can't use arithmetic operations. –  SyncMaster Sep 4 '12 at 0:02
add comment

3 Answers

up vote 8 down vote accepted

Use hash tables. Elements are the key, number of occurrences are the values.

share|improve this answer
2  
If the data is starting out in vectors, it's going to take longer to create the hash tables than to do a binsearch on the vector. On the other hand, if the questioner has control over how the vectors are created, and can create hash tables instead at the outset, this will be faster. –  Steven Burnap Sep 4 '12 at 0:11
    
it depends on the size of the vectors. If the vectors are small, no problem. If they have millions of elements, big problem. The hashtable soluition is O(n). –  ddyer Sep 4 '12 at 4:16
add comment

As there are sorted, you can use standard std::set_difference function:

unsigned int compute_uniqute_elements(vector<unsigned int> sample_vector, vector<unsigned int> merged_vectors)
{
    vector<unsigned int> difference;
    vector<unsigned int>::iterator it;
    it = std::set_difference(sample_vector.begin(), sample_vector.end(), it->begin(), it->end(), difference.begin());

    return std::distance(difference.begin(), it);
}
share|improve this answer
add comment

It sounds like your data are strings and you used numeric values to more easily illustrate aspects of the problem like each vector being sorted, but having a lot of vectors to iterate across.

Dynamic programming may provide great opportunities to get big savings in efficiency. Typically, dynamic programming executes part of your algorithm to generate a partial solution that can be reused in later iterations to save time. There is a great version of the travelling salesman problem that does this for huge time savings (at the trade-off of needing huge amounts of memory).

If you know some things about your data, say that it is limited to integer values between 0 and 99, a simple approach would be to make a table of 100 booleans, parse the vectors once to mark the table to show which elements are present, then compare your test vector against the table.

If this were a search algorithm, and the input were a key of multiple strings and the sorted multiple vector data were keywords from documents, you could pick from many methods to collect the unique strings in a representation suitable for binary or other search. Storage needed for this helper data structure will depend on how many unique strings are in the input data set. It might be surprising for even data as varied as English text how few unique strings can be found in two million vectors of even a few hundred words each.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.