C# Merge Two SortedLists (Union?)

Question

I'm looking to speed up a piece of code that merges two SortedLists.

C# 4.0 generic SortedList: http://msdn.microsoft.com/en-us/library/ms132319(v=vs.100).aspx

public Trait getTrait(decimal thisValue)
{       
    if (ParentStructure != null && ParentStructure.RankedTraits.Count > 0)
    {
        SortedList<decimal, Trait> tempTraits = this.RankedTraits;

        // Improve here (union?)
        foreach (KeyValuePair<decimal, Trait> kvp in (ParentStructure.RankedTraits))
        {
            if (!tempTraits.ContainsKey(kvp.Key)) 
            { 
                tempTraits.Add(kvp.Key, kvp.Value); 
            }
        }
        return _getTrait(tempTraits, thisValue);
        }
    }
    return _getTrait(_rankTraits, thisValue);
}

I'm thinking that a union instead of the foreach loop would be faster but I don't know how to implement a union on a SortedList. If someone could help me out with that I would appreciate it.

Also, if there is a better way of doing this overall I'm open to suggestions.

Just an idea, but according to [this answer](http://stackoverflow.com/a/1754080/551322), it might help if you sort input collection. — nrodic, Nov 02 '12 at 01:49
Thanks, the data being input is coming from sorted lists so that should make it presorted -- looking at that though I may want to switch to a SortedDictionary. — Anthony Nichols, Nov 02 '12 at 01:52
Why are you looking to speed up this code? Does it perform poorly? — Enigmativity, Nov 02 '12 at 04:21
No, it runs fine - It just seems like there should be a better way. This is a key part of my code and I just need to have it run as quickly as possible. — Anthony Nichols, Nov 02 '12 at 14:05
So people keep editing my description and removing C# from the title (I think that should stay) and the last person also removed the link to `SortedList` on MSDN. Can anyone give me some insight to why? — Anthony Nichols, Nov 02 '12 at 14:43

score 3 · Accepted Answer · answered Nov 02 '12 at 04:36

3

The only way that I can think of merging two SortedList instances would be to union them, then convert to a lookup, then grab the first element of the lookup collection to make a dictionary.

I would need to make a dictionary because the SortedList only supports one-by-one adds. So the only other option would be to inject a dictionary into the SortedList constructor.

Bottom line: I think your current code is pretty decent as it is. LINQ can help reduce the code to about 2 lines (or one if you're a masochist).

SortedList<decimal, Traits> listA = new SortedList<decimal, Traits>();
SortedList<decimal, Traits> listB = new SortedList<decimal, Traits>();

listA.Add(1m, new Traits { FieldName = "One" });
listA.Add(2m, new Traits { FieldName = "Two" });
listA.Add(3m, new Traits { FieldName = "Three" });

listB.Add(1m, new Traits { FieldName = "One" });
listB.Add(4m, new Traits { FieldName = "Four" });
listB.Add(5m, new Traits { FieldName = "Five" });

var listUnion = listA.Union(listB).ToLookup(k => k.Key, v => v.Value)
                     .ToDictionary(k => k.Key, v => v.First());
var listMerged = new SortedList<decimal, Traits>(listUnion);

answered Nov 02 '12 at 04:36

code4life

15,655
7
50
82

Thanks -- that answers my questions about unions -- however it doesn't make my code faster (probably because of having to convert it back to a SortedList) so I wont me using it. Thanks again! – Anthony Nichols Nov 02 '12 at 14:35
Yeah, I kind of thought so, too. The issue is that the `SortedList.Union` doesn't seem to respect the `IEqualityComparer`. If it did, it **might** be a tiny bit more performant, because the conversion to lookup would impact the later conversion to dictionary. It also kind of sucks that `SortedList` doesn't innately support the addition of a range of `KeyValuePairs` rather than just one at a time. – code4life Nov 02 '12 at 14:38
Yeah, this actually does a lot more looping than the original code, because that's what linq does in the background. – theMayer Nov 02 '12 at 14:38
@code4life "It also kind of sucks that SortedList doesn't innately support the addition of a range of KeyValuePairs rather than just one at a time." -- That's what I was hoping someone could point me towards. But at least I feel a little bit more confidant in my programming skills now. =) – Anthony Nichols Nov 02 '12 at 14:46

theMayer · Answer 2 · 2012-11-02T01:54:33.953

2

SortedSet has a UnionWith method that does what you are asking. I created my own implementation of SortedSet and it performs very quickly.

http://msdn.microsoft.com/en-us/library/dd411939.aspx

Nevermind, I re-read your question and you are using the list implementation; however, if you can figure out a way to create an EqualityComparer instead of using a specific key, it might be possible to adapt a SortedSet to your purpose.

edited Nov 02 '12 at 01:54

answered Nov 02 '12 at 01:40

theMayer

15,456
7
58
90

Thanks, but SortedSet & SortedList are not the same thing. It's the Key/Value that is messing me up and SortedSet doesn't have a key. -- Also I am hoping to get some sort of example on how to implement it. I can do searches on my own. – Anthony Nichols Nov 02 '12 at 01:42
Indeed, my apologies. However, looking at your example code, are you trying to eliminate duplicates? – theMayer Nov 02 '12 at 01:45
No duplicates keys -- I don't believe a SortedList can have duplicate keys anyway. Duplicate Values are fine. – Anthony Nichols Nov 02 '12 at 01:49
Yes, you are correct, I guess my implementation is slightly different than yours. I use a date as the key in my sorted set, so no duplicates allowed and I can pull out by date. You can ignore this answer :-) – theMayer Nov 02 '12 at 01:53

C# Merge Two SortedLists (Union?)

2 Answers2