How to keep only the last duplicate when iterating through rows

Question

Following code iterates through many data-rows, calcs some score per row and then sorts the rows according to that score:

unsigned count = 0;
score_pair* scores = new score_pair[num_rows];
while ((row = data.next_row())) {
    float score = calc_score(data.next_feature())
    scores[count].score = score;
    scores[count].doc_id = row->docid;
    count++;
}

assert(count <= num_rows);
qsort(scores, count, sizeof(score_pair), score_cmp);

Unfortunately, there are many duplicate rows with the same docid but different score. Now i like to keep the last score for any docid only. The docids are unsigned int, but usually big (=> no lookup-array) - using a HashMap to lookup the last count for a docid would probably be too slow (many millions of rows, should only take seconds not minutes...).

Ok, i modified my code to use a std:map:

map<int, int> docid_lookup;
unsigned count = 0; 
score_pair* scores = new score_pair[num_rows];
while ((row = data.next_row())) {
    float score = calc_score(data.next_feature())

    map<int, int>::iterator iter;
    iter = docid_lookup.find(row->docid);
    if (iter != docid_lookup.end()) {
        scores[iter->second].score = score;
        scores[iter->second].doc_id = row->docid;
    } else {
        scores[count].score = score;
        scores[count].doc_id = row->docid;
        docid_lookup[row->docid] = count;
        count++;
    }
}

It works and the performance hit is not as bad as i expected - now it runs a minute instead of 16 seconds, so it's about a factor of 3. Memory usage has also gone up from about 1Gb to 4Gb.

Answer 1

I'd go for a std::map of docids. If you could create an appropriate hashing function, a hash-map would be preferable. But I guess it's too difficult. And no - the std::map ist not too slow. Access is O(log n), which is nearly as good as O(1). O(1) is array access time (and Hashmap btw).

Btw, if std::map is too slow, qsort O(n log n) is too slow as well. And, using a std::map and iterating over it's contents, you can perhaps save your qsort.

---

Some additions for the comment (by onebyone):

• I did not go for the implementation details, since there wasn't enough information on that.
• qsort may behave bad with sorted data (depending on the implementation). Std::map may not. This is a real advantage, especially if you read the values from a database that might output them ordered by key.
• There was no word on the memory allocation strategy. Changing to a memory allocator with fast allocation of small objects may improve the performance.
• Still - the fastest would be a hash map with an appropriate hash function. Since there's not enough information about the distribution of the keys, presenting one in this answer is not possible.

Short - if you ask general questions, you get general answers. This means - at least for me, looking at the time complexity in the O-Notation. Still you were right, depending on different factors, the std::map may be too slow while qsort is still fast enough - it may also be the other way round in the worst case of qsort, where it has n^2 complexity.

Answer 2

The first thing I'd try would be a map or unordered_map: I'd be surprised if performance is a factor of 60 slower than what you did without any unique-ification. If the performance there isn't acceptable, another option is something like this:

// get the computed data into a vector
std::vector<score_pair>::size_type count = 0;
std::vector<score_pair> scores;
scores.reserve(num_rows);
while ((row = data.next_row())) {
    float score = calc_score(data.next_feature())
    scores.push_back(score_pair(score, row->docid));
}

assert(scores.size() <= num_rows);

// remove duplicate doc_ids
std::reverse(scores.begin(), scores.end());
std::stable_sort(scores.begin(), scores.end(), docid_cmp);
scores.erase(
    std::unique(scores.begin(), scores.end(), docid_eq),
    scores.end()
);

// order by score
std::sort(scores.begin(), scores.end(), score_cmp);

Note that the use of reverse and stable_sort is because you want the last score for each doc_id, but std::unique keeps the first. If you wanted the first score you could just use stable_sort, and if you didn't care what score, you could just use sort.

The best way of handling this is probably to pass reverse iterators into std::unique, rather than a separate reverse operation. But I'm not confident I can write that correctly without testing, and errors might be really confusing, so you get the unoptimised code...

Edit: just for comparison with your code, here's how I'd use the map:

std::map<int, float> scoremap;
while ((row = data.next_row())) {
    scoremap[row->docid] = calc_score(data.next_feature());
}
std::vector<score_pair> scores(scoremap.begin(), scoremap.end());
std::sort(scores.begin(), scores.end(), score_cmp);

Note that score_pair would need a constructor taking a std::pair<int,float>, which makes it non-POD. If that's not acceptable, use std::transform, with a function to do the conversion.

Finally, if there is much duplication (say, on average 2 or more entries per doc_id), and if calc_score is non-trivial, then I would be looking to see whether it's possible to iterate the rows of data in reverse order. If it is, then it will speed up the map/unordered_map approach, because when you get a hit for the doc_id you don't need to calculate the score for that row, just drop it and move on.

Answer 3

Why not sort by doc id first, calculate scores, then for any subset of duplicates use the max score?

On re-reading the question; I'd suggest a modification to how scores are read in. Keep in mind C++ isn't my native language, so this won't quite be compilable.

unsigned count = 0;
pair<int, score_pair>* scores = new pair<int, score_pair>[num_rows];
while ((row = data.next_row())) {
 float score = calc_score(data.next_feature())
 scores[count].second.score = score;
 scores[count].second.doc_id = row->docid;
 scores[count].first = count;
 count++;
}

assert(count <= num_rows);
qsort(scores, count, sizeof(score_pair), pair_docid_cmp);

//getting number of unique scores
int scoreCount = 0;
for(int i=1; i<num_rows; i++) 
    if(scores[i-1].second.docId != scores[i].second.docId) scoreCount++; 
score_pair* actualScores=new score_pair[scoreCount];

int at=-1;
int lastId = -1;
for(int i=0; i<num_rows; i++)
{ 
    //if in first entry of new doc id; has the last read time by pair_docid_cmp
    if(lastId!=scores[i].second.docId) 
        actualScores[++at]=scores[i].second;
}
qsort(actualScores, count, sizeof(score_pair), score_cmp);

Where pair_docid_cmp would compare first on docid; grouping same docs together, then second by reverse order read; such that the last item read is the first in the sublist of items with the same docid. Should only be ~5/2x memory usage, and ~double the execution speed.

Answer 4

Unless I've misunderstood the question, the solution can be simplified considerably. At least as I understand it, you have a few million docid's (which are of type unsigned int) and for each unique docid, you want to store one 'score' (which is a float). If the same docid occurs more than once in the input, you want to keep the score from the last one. If that's correct, the code can be reduced to this:

std::map<unsigned, float> scores;

while ((row = data.next_row())) 
    scores[row->docid] = calc_score(data.next_feature());

This will probably be somewhat slower than your original version since it allocates a lot of individual blocks rather than one big block of memory. Given your statement that there are a lot of duplicates in the docid's, I'd expect this to save quite a bit of memory, since it only stores data for each unique docid rather than for every row in the original data.

If you wanted to optimize this, you could almost certainly do so -- since it uses a lot of small blocks, a custom allocator designed for that purpose would probably help quite a bit. One possibility would be to take a look at the small-block allocator in Andrei Alexandrescu's Loki library. He's done more work on the problem since, but the one in Loki is probably sufficient for the task at hand -- it'll almost certainly save a fair amount of memory and run faster as well.

Answer 5

If your C++ implementation has it, and most do, try hash_map instead of std::map (it's sometimes available under std::hash_map).

If the lookups themselves are your computational bottleneck, this could be a significant speedup over std::map's binary tree.