CODEWITHSUNDEEP
c++
rbj
rbj

Reputation: 63

Check for duplicates in large vector of strings

I'm attempting to find duplicate instances of strings where I have a vector of ~2.5 million strings.~

At the moment I use something like:

std::vector<string> concatVec; // Holds all of the concatenated strings containing columns C,D,E,J and U.
std::vector<string> dupecheckVec; // Holds all of the unique instances of concatenated columns
std::vector<unsigned int> linenoVec; // Holds the line numbers of the unique instances only

// Copy first element across, it cannot be a duplicate yet
dupecheckVec.push_back(concatVec[0]);
linenoVec.push_back(0);

// Copy across and do the dupecheck
for (unsigned int i = 1; i < concatVec.size(); i++)
{
    bool exists = false;

    for (unsigned int x = 0; x < dupecheckVec.size(); x++)
    {
        if (concatVec[i] == dupecheckVec[x])
        {
            exists = true;
        }
    }

    if (exists == false)
    {
        dupecheckVec.push_back(concatVec[i]);
        linenoVec.push_back(i);
    }
    else
    {
        exists = false;
    }
}

Which is fine for small files, but obviously ends up taking an extremely long time as filesize grows due to the nested for loop and increasing number of strings contained in dupecheckVec.

What might be a less horrific way to do this in a large file?

Upvotes: 6

Views: 6151

Answers (4)

das_weezul
das_weezul

Reputation: 6142

You could use a hashtable which uses strings as keys and integers as values (the count). Then just iterate over the list of strings and increment the value for each string by 1. Finally iterate over the hashtable and keep those strings with a count of 1

[UPDATE] Another solution:

  • Use a hashtable with string as key and index-position of string in vector/array
  • For each string in the vector:
    • If string is contained in hashtable [optional: remove the entry and] continue
    • Otherwise put index-position of current string into hashtable using the string as key and continue
  • When done iterate over hashtable and use indices to retrieve unique strings

This solution gives you the indices of all strings, filtering out duplicates. If you want only those strings, which have no duplicates, you have to remove the hashtable entry if the string is already used in the hastable.

Upvotes: 4

Mike Seymour
Mike Seymour

Reputation: 254471

If you don't mind reordering the vector, then this should do it in O(n*log(n)) time:

std::sort(vector.begin(), vector.end());
vector.erase(std::unique(vector.begin(), vector.end()), vector.end());

To preserve the order, you could instead use a vector of (line-number, string*) pairs: sort by string, uniquify using a comparator that compares string contents, and finally sort by line number, along the lines of:

struct pair {int line, std::string const * string};

struct OrderByLine {
    bool operator()(pair const & x, pair const & y) {
        return x.line < y.line;
    }
};

struct OrderByString {
    bool operator()(pair const & x, pair const & y) {
        return *x.string < *y.string;
    }
};

struct StringEquals {
    bool operator()(pair const & x, pair const & y) {
        return *x.string == *y.string;
    }
};

std::sort(vector.begin(), vector.end(), OrderByString());
vector.erase(std::unique(vector.begin(), vector.end(), StringEquals()), vector.end());
std::sort(vector.begin(), vector.end(), OrderByLine());

Upvotes: 9

jonsca
jonsca

Reputation: 10381

Use std::unique see this

Upvotes: 0

Puppy
Puppy

Reputation: 146930

You could sort which is O(n logn), and then any equal elements must be consecutive so you can just check against the next element, which is only O(n). Whereas your naive solution is O(n^2).

Upvotes: 5

Related Questions