Suppose we have a dataframe with ~10M rows with ~9M duplicate records. What is the most time efficient way of selecting the unique records from this dataframe?
Some sort of sampling algorithm?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Cross-posted: cs.stackexchange.com/q/152230/755, cstheory.stackexchange.com/q/51572/5038. Please do not post the same question on multiple sites. I see that you got some suggestions on CS Theory. When you get suggestions, please mention that in the question and explain whether it meets your needs or not and why or why not. If you post on the wrong site, I would recommend you delete the copy on the wrong site before posting on a new one. $\endgroup$– D.W. ♦Jun 10 at 18:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
A reasonable approach would be to build a hashtable that stores all unique records. Scan through the records one at a time, adding each to the hashtable if it is not already present; if it already is in the hashtable, do nothing, and if it is not already in the hashtable, add it to the hashtable and output it.
Another approach would be to sort the records (which will make all duplicates adjacent), then remove duplicates, then return to the original order if needed. This has the benefit that it can scale to even larger databases: if the entire dataset cannot be stored in memory, it is possible to use an external sort and still be efficient. In contrast, a hash table will work great if everything fits in memory, but will be very slow if the database does not fit in memory.
