Challenge: the fastest way to filter doubled items from a list.

[M Hussain]

I bet it will be faster than everything.

UniqueList.Add((from string itm in UniqueList
from string compareItem in doubledList
where itm == compareItem
select compareItem).ToString());

[Lilith C]

Usually I sort the list then iterate through the list, outputting each change. When a change is found its value is used to compare for the next change detection. This code outputs to a string.

iList.Sort();
txtOutput.Text = "";
foreach (string str in iList)
{
if (str != lastEntry)
{
txtOutput.Text += (str + "\r\n");
lastEntry = str;
}
}

And, yes, I know that StringBuilder might be more appropriate for some lists.

I'm not a programmer but I play one at the office

[Climate Turnip]

Its always dangerous to assume that all performance issues can be assessed using big O notation as an evaluation method, particularly when not comparing apples with apples in terms of implementation specifics. Hashing resolves down to numeric comparison as opposed to String evaluation but involves a hashing function overhead, these are important factors, there are also allocation issues particular to any implementation. Trivialising performance evaluation in this way where growth rate is a factor is always a dangerous proposition.

[Brian L Parker]

public List<String> RemoveDoubles(List<string> doublelist) { return doublelist.Distinct().ToList(); }

[KP Lee]

You've been given several options to use pre-existing code. Makes it easier, doesn't necessarily make it faster. I can certainly see how to make your code slightly faster:

        foreach (string item in doubledList)
       {
            bool x = true;
            foreach (string compare in UniqueList)
            {
                if (item == compare)
                {
                    x = false;
                    break;
                }
            }
            if (x) UniqueList.Add(item);
        }

There is one less if statement needed. The break command knows it is breaking the inner foreach, not the if statement it is in. If you have 100 items with one duplicate, the first outer loop saves nothing, after that, you've removed an if check for every inner loop executed. If the first and last are duplicates you've saved 4800+ if checks. (First outer loop never executes an inner loop, every loop after that executes the inner 1 less than the outer ones taken except the last loop that takes just one inner loop. My math may be wrong, but I'm sure that saves over 4800 if tests. 98/2=49 The last full inner loop will be for 98 times, the prior loop would be 97 and the first inner loop is 1 added together is 98, then 96+2 is 98, etc for 49 times 98 inner loops were taken. 49*98=4802 plus 1 for the 100th outer loop.) Maybe a sorted unique list could be faster? I'll think about that. Is a sorted list OK?

[Harley L Pebley]

Here are the results of a performance test of all the ways mentioned (at the time of this writing) in this thread: skylark-software.com[^]

[TG_Cid]

Good job, i dont know why anyone would downvote your post, but i think is nice to see the comparative. And surprisingly(at least to me) the most simply answers were the best.(i thought the sorted list would be the best)

[Harley L Pebley]

Thanks. The down vote is strange to me too. Perhaps it's because I didn't post it as a CodeProject article. :confused: As I mentioned, I expected Distinct() to be about same as the sorted list and was surprised it was so much faster; apparently it's using a HashSet (or equivalent) internally. But I was really surprised at the difference in speed between the sorted list and the hash set. I thought they'd be closer to each other. I'm guessing it's probably a difference related to inserts.

[Zhang Lu1011]

this problem is complex!

[Jason McBurney]

Agreed, the example given will run in N^2 time, and your solution will run in N time.

You can only be young once. But you can always be immature. - Dave Barry

[Bernhard Hiller]

Do not forget that HashSet must somehow check the constraint that there must not be duplicates. Also the time needed for that operation must be taken into account. And it will increase with the size of the Hashset.

[Lutoslaw]

Harley L. Pebley wrote:

it's using a HashSet (or equivalent) internally

It uses it's own Set type which basically is a minimal implementation of a HashSet. So, I am suprised that Distinct is slower than a HashSet, because it uses a dedicated implementation instead of a general solution.

Greetings - Jacek

[I explore code]

so i know this thread is centuries old, but i decided to comment anyway. I haven't looked at what others have posted yet so heres my unadulterated take:

for (int i = 0; i < doubled.Count; i++)
{
if (!uniques.Contains(doubled[i]))
{
uniques.Add(doubled[i]);
}
}

just one loop, although i know contains() is basically an O(n) method but the time difference doesnt seem much between your code and mine. But mine is less number of lines ;)

[VallarasuS]

call this guy from Fsharp.Core!! >> http://msdn.microsoft.com/en-us/library/ee353861.aspx[^]

Regards Vallarasu S | FSharpMe.blogspot.com

[Kostya Kovalskyy]

You can put the strings that repeat often in the beginning of your unique string, so it will not have to iterate that many times through the loop. So it will be ordered by the amount it repeats instead of the order of original string. For example, for string string: one three two two three three unique string will be unique: three two one instead of unique: one three two because there is most threes in the string. But this will not always optimize, because there may be no most occurring string if they are completely at randomized. So for example, it would not work for random computer generated strings, but work for predictable user info. Edit: you can also order them by there length, for example if you have strings: reallyLongStringWhichIsReallyLong anotherString reallyLongStringWhichIsReallyLong shortString shortString ... Even through shortString and reallyLongString occur the same amount of times, it takes longer for computer to check if reallyLongString is in the front, so it would be more efficient to move this in the back of unique string. Also, how long will it take your function in C# to check this strings: "stuff", "str", "str", "morestuff", "str", "not unique", "evenMoreStuff", "stuff", "unique", "morestuff", "not unique"? In C++, it takes 0.124 seconds when I print results to the screen and 0.074 when I do not. in C++ with gcc:

//0.124 and 0.074
#include
#include
using namespace std;

vector getUnique(vector listStr) {
vector::iterator listIt;

vector uniqueStr;
vector::iterator uniqueIt;

for (listIt = listStr.begin(); listIt < listStr.end(); listIt++) {
bool exists = false;
for (uniqueIt = uniqueStr.begin(); uniqueIt < uniqueStr.end(); uniqueIt++) {
if (*listIt == *uniqueIt) {
exists = true;
break;
}
}
if (!exists) uniqueStr.push_back(*listIt);
}
cout << "list: ";
for (listIt = listStr.begin(); listIt < listStr.end(); listIt++) cout << " " << *listIt;
cout << "\n\nunique list: ";
for (uniqueIt = uniqueStr.begin(); uniqueIt < uniqueStr.end(); uniqueIt++) cout << " " << *uniqueIt;
return uniqueStr;
}

int main() {
vector str = {"stuff", "str", "str", "morestuff", "str", "not unique", "evenMoreStuff", "stuff", "unique", "morestuff", "not unique"};

getUnique(str);
return 0;
}

[dojohansen]

That doesn't mean it's always faster - it just means it is asymptotically faster. It always annoyed me that my algorithms class never dealt with this issue, being exclusively interested in the theoretical framework where "best" only meant "best for infinite-size problem" and not at all interested in real-world performance, where infinite input isn't even possible. :)