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

[Jorgen Andersson]

A hashset might not be the best choice to find doubled items since:

MSDN wrote:

The HashSet(Of T) class provides high-performance set operations. A set is a collection that contains no duplicate elements, and whose elements are in no particular order.

Light moves faster than sound. That is why some people appear bright, until you hear them speak. List of common misconceptions

[Jorgen Andersson]

UniqueList = doubledList.distinct

Light moves faster than sound. That is why some people appear bright, until you hear them speak. List of common misconceptions

[PIEBALDconsult]

Exactly. Iterate the input List, add new items to the HashSet and the result List.

[PIEBALDconsult]

Luc Pattyn wrote:

You're in the wrong forum.

Correct, this should be a Friday Programming Challenge.

[Luc Pattyn]

if (!hashSet.Contains(candidate)) hashSet.Add(candidate); takes full advantage of hashing and collecting, much faster than other collections' Contains method. [ADDED] And the test is redundant, Add() already does it, so hashSet.Add(candidate); suffices [/ADDED] :)

Luc Pattyn [My Articles] Nil Volentibus Arduum

[Jorgen Andersson]

:doh: :sigh:

Light moves faster than sound. That is why some people appear bright, until you hear them speak. List of common misconceptions

[0bx]

I know... but the question forums are primarily used for showing code that doesn't work, so I just wanted to throw a stone in the pond. BTW: I just realized that I know you personally. We both play in the same chess club. :-D

Giraffes are not real.

[Luc Pattyn]

You could have wrinkled the C# pond; the programming forums are for discussions, not just for "help, my code fails" kind of questions. CU.

Luc Pattyn [My Articles] Nil Volentibus Arduum

[ekolis]

private List LoadUniqueList(List doubledList)
{
return doubledList.Distinct().ToList();
}

LINQ is fun :D And as for using this part of the forum for challenges, I think it's a great idea - hardly anyone ever posts here to begin with, since people don't usually look at their own code and say "Damn, that was clever - I need to share it with someone!"

[Philippe Mori]

Such an algorithm is 0(n²) thus for large collection, it will be very slow. Each time, you double the collection size, it is 4 times slower. Using an HastSet or a SortedSet or a Dictionary would be much faster for large collections. The order would then be about O(n) with hashing or O(n log(n)) with Dictionary (binary search). Another alternative would be to sort the list if the order does not matters. It is then easier to skip skip or remove duplicates.

Philippe Mori

[Stefan_Lang]

I'd concatenate the lists ( O(1); or O(n) if you must copy them ), then sort it ( raising complexity to O(n*log(n) ) and then remove duplicates ( O(n) again ) That means your complexity will be ruled by your sorting algorithm: choose whichever algorithm fits your data best.

[pchinery]

I don't agree that hashing would make it O(n), as it requires to handle hash collisions. This if course is not a real problem for average use cases, but after all that's not what the Landau thing is about, right? ;-) Usually, this would end up taking O(n log(n)) time, even with hashing. The main difference would be the constant that is involved. Of course it is hard to tell, but I would think that the HashSet would provide highly optimized code to do just this and it would be recommended to just use that.

[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.