Remove duplicate from large lists efficiently?

Question

I have a list which contains ids and values and I need to remove ids duplication. I am looking for an efficiently way preferable in LINQ, instead of my loop and if condition. Thank you for any help and advise.

var list = new List<Tuple<int, double>>();

Current values:
1, 3.6
1, 3.8
2, 5.6
3, 8.1

Wished values:
1, 3.6
2, 5.6
3, 8.1


for (int i = 0; i < list.Count - 1; i++)
{
    if (list[i].Item1 == list[i + 1].Item1)
        list.RemoveAt(i+ 1);
}

http://stackoverflow.com/questions/20883890/linq-query-to-get-the-distinct-values-in-a-list and http://stackoverflow.com/questions/19406242/select-distinct-using-linq and http://stackoverflow.com/questions/998066/linq-distinct-values — Abhitalks, Nov 20 '14 at 07:12
I have to comment on this.. (probably will become my pet peeve on LINQ related questions like these on SO). Why do you think that LINQ version is more efficient compared to the simple for loop implementation? As far as **execution efficiency** is concerned, the accepted answer, which uses `.GroupBy`, `.Select` and `.ToDictionary` is far from being efficient. :( So what efficiency do you seek here? I do not understand. Please clarify.. I am very curious. — Vikas Gupta, Nov 20 '14 at 08:52
@VikasGupta some people use LINQ because want shorter better readable and maintainable code. I hope this satisfy your curiosity. However, I think would be batter if you could help instead of been curious. — Doro, Nov 20 '14 at 09:14
`IEqualityComparer` interface defines methods to support the comparison of objects for equality. [link](http://msdn.microsoft.com/en-us/library/ms132151(v=vs.110).aspx) — enapi, Nov 20 '14 at 12:34

RajeshKdev · Answer 1 · 2014-11-20T07:37:59.123

3

If Id and Values are same as the other one. It will remove that item from list.

distinctList = list.Distinct().ToList();

If you are okay with converting the Tuple to Dictionary:

Try This: If Only Id's are duplicate removes that item from list. It will not consider the value duplication.

var distinctDictionary = list.GroupBy(id => id.Item1)
                         .Select(group => group.First())
                         .ToDictionary(id => id.Item1, val => val.Item2);

Look at the Screen shots:

Solution 1:

Solution One

Solution 2:

Solution Two

edited Nov 20 '14 at 07:37

answered Nov 20 '14 at 07:11

RajeshKdev

6,365
6
58
80

It compares only the Ids or the entire row? – Doro Nov 20 '14 at 07:12
Only the Ids, without considering the values. – Doro Nov 20 '14 at 07:26
For Ex: If `Id and Values are same` as the other one. It will remove that item from list. – RajeshKdev Nov 20 '14 at 07:33
Where as Second Solution will work only based on the `Id` duplication. – RajeshKdev Nov 20 '14 at 07:36
Ok, but just the Ids are the same, values are different. See my example. Anyway, in my read application I only need Ids, what if I use your second example (distinctDictionary) and then convert distinctDictionary into list taking just the Ids? – Doro Nov 20 '14 at 07:36
Check out my screen shots. Rather explaining somthing just visualize it. :) – RajeshKdev Nov 20 '14 at 07:39
In my example I have 1 3.6 and 1 3.8. I only need one of them. – Doro Nov 20 '14 at 07:39
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/65264/discussion-between-doro-and-rjk). – Doro Nov 20 '14 at 08:06
I am at work and some security policy does not allow me to access the chart. – Doro Nov 20 '14 at 08:12
Anyway, in your code I am see that you have 1 3.6 and again 1 3.6 while I have 1 3.6 and 1 3.8. – Doro Nov 20 '14 at 08:14

score 2 · Answer 2 · answered Nov 20 '14 at 07:13

2

Why are you a List with tuples? With the requested functionality I would use a Dictionary so you won't have duplicates.

answered Nov 20 '14 at 07:13

RvdK

19,580
4
64
107

It is just an example. In my case I have Dates a function has interpolate them. – Doro Nov 20 '14 at 07:15
@doro - From what you provided, it seems like you have one "identifying" piece of data and then "something else", too. In the code you showed, the "identifying" piece of data is the `Item1` of the tuple and "something else" is `Item2`. In this case it's `int` and `double`, but it could also be `long` and `DateTime`, or `Guid` and `SomeHugeClass`. Now you have a list of those pairs and you want to "remove duplicates" from it. Basically you only want *one* "something else" for each "identifying" thing. This is `key -> value` and this is, what `Dictionaries` are made for. – Corak Nov 20 '14 at 07:42
I just explained why I am using List. But, the point is how to remove ids duplication. I also included a loop and if which does the work but I am searching a better way. – Doro Nov 20 '14 at 07:46

score 2 · Accepted Answer · answered Nov 20 '14 at 09:51

2

Given your opinion that LINQ is generally more readable / maintainable and is generally equitable to efficiency, I present the following solution, which uses LINQ, and (IMHO compared to others presented so far) is more efficient in execution as well -

list = list.Where((entry, i) => i == 0 || entry.Item1 != list[i - 1].Item1).ToList();

answered Nov 20 '14 at 09:51

Vikas Gupta

4,455
1
20
40

This is in addition to my original question, there is any way that list = ... containd just ids (only item1)? – Doro Nov 20 '14 at 10:07
1

`var list2 = list.Select(item => item.Item1).Distinct().ToList();` – Corak Nov 20 '14 at 10:11
@Vikas - Your solution is great, but if you only ever check the previous element, you might need to sort the list first (if the list is not already sorted). `list = list.OrderBy(item => item.Item1).ToList();` – Corak Nov 20 '14 at 10:22
@Corak Agreed.. but I think the example stated in the question (along with current implementation with for loop) clearly suggests that following assumptions can be made for this specific scenario - 1. It is a list (specifically, supports indexing, otherwise indexer cannot be used). 2. List is already sorted. 3. Object type in the list doesn't already implement appropriate Comparer / Equatable, there are many :(, interface to support the scenario. – Vikas Gupta Nov 20 '14 at 10:27

score 0 · Answer 4 · answered Nov 20 '14 at 07:20

0

DistinctByKey = list.Select(x => x.Keys).Distinct();

DistinctByValue= DistinctByKey.Select(x => x.Values).Distinct();

answered Nov 20 '14 at 07:20

Abbas Galiyakotwala

2,949
4
19
34

Remove duplicate from large lists efficiently?

4 Answers4