C# 合并两个已排序的列表（并集？）

Question

C# 合并两个已排序的列表（并集？）

7

我正在寻找加速合并两个 SortedLists 代码的方法。

C# 4.0 泛型 SortedList：http://msdn.microsoft.com/zh-cn/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);
}

我在考虑使用联合操作代替foreach循环可能更快，但我不知道如何在SortedList上实现联合操作。如果有人能帮助我解决这个问题，我将不胜感激。

另外，如果有更好的方法来完成这个任务，我也愿意听取建议。

- Anthony Nichols

1

只是一个想法，但根据这个答案，如果您对输入集进行排序可能会有所帮助。 - nrodic

谢谢，输入的数据来自已排序的列表，因此应该是预排序的 - 不过看起来我可能想要切换到 SortedDictionary。 - Anthony Nichols

你为什么想要加速这段代码？它的性能表现不佳吗？ - Enigmativity

1

不，它可以正常运行——只是似乎应该有更好的方法。这是我的代码的关键部分，我只需要让它尽快运行。 - Anthony Nichols

所以有人一直在编辑我的描述并从标题中删除C#（我认为应该保留），最后一个人还删除了MSDN上的SortedList链接。有人能给我一些见解吗？ - Anthony Nichols

2个回答

2

SortedSet有一个UnionWith方法可以实现您所要求的功能。我创建了自己的SortedSet实现，它的性能非常快速。

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

没关系，我重新阅读了你的问题，你正在使用列表实现；但是，如果你能想出一种创建EqualityComparer而不是使用特定键的方法，可能可以将SortedSet适应于你的目的。

- theMayer

谢谢，但SortedSet和SortedList不是同一回事。它是键/值混淆了我的思维，而SortedSet没有键。 -- 另外，我希望能够获得一些实现的例子。我可以自己搜索。 - Anthony Nichols

实际上，非常抱歉。然而，看了你的示例代码，你是在尝试消除重复项吗？ - theMayer

没有重复的键 - 我不认为SortedList可以有重复的键。重复的值是可以的。 - Anthony Nichols

是的，你说得对，我想我的实现和你的稍有不同。我在我的排序集中使用日期作为键，因此不允许重复，并且可以按日期进行提取。你可以忽略这个答案 :-) - theMayer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- code4life · Accepted Answer

我能想到合并两个SortedList实例的唯一方法是将它们联合起来，然后转换为查找，再从查找集合中获取第一个元素以创建字典。

我需要创建一个字典，因为SortedList仅支持逐个添加。所以唯一的其他选择是将字典注入到SortedList构造函数中。

底线：我认为您当前的代码已经非常不错了。LINQ可以帮助将代码减少到约2行（如果您是受虐狂则只需一行）。

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