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.

Answer 1

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);

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