我有两个类型为T的泛型列表。这两个列表都包含相同的类型,我想根据列表2中列表1中不存在的项目,根据每个项目的ID,创建第三个列表(或列表2的过滤版本)。
每个列表都包含一个"Package"对象,该对象具有一个ID属性。
现在我用For Each循环来模拟代码,我知道这很可怕(Big O是恒定时间),所以我想要一个更有效的方法。
根据项目需求,这段代码是用VB编写的,但我更喜欢C#,所以任何一个代码示例都适合我。
Private Sub RemoveStockPackagesFromSelection()
Dim p As Package
Dim packageList As List(Of Package) = New List(Of Package)
Dim stockPackageList As List(Of Package) = New List(Of Package)
Dim result As List(Of Package) = New List(Of Package)
' Fill list with User's Packages
For i As Integer = 0 To ListBox2.Items.Count - 1
p = New Package
p.Id = CInt(ListBox2.Items(i).Value)
p.Name = ListBox2.Items(i).Text
packageList.Add(p)
Next
' Fill list with Stock Packages to compare:
Dim ds As DataSet = DAL.GetStandardPackages()
For Each dr As DataRow In ds.Tables(0).Rows
p = New Package
p.Id = CInt(dr.Item("id"))
stockPackageList.Add(p)
Next
' Do Compare and Filter
For Each p1 As Package In packageList
For Each p2 As Package In stockPackageList
If Not p1.Id = p2.Id Then
result.Add(p2)
End If
Next
Next
' Here is our new trimmed list:
Response.Write(result.Count)
End Sub
什么是一个好的和干净的LINQ或Lamda的方式来做这个过滤?我的方法中的大O是什么,所提出的方法中会有什么大O(只是为了满足我的好奇心)。
感谢
LINQ除方法
正如Maxim和svick所建议的,这将是最干净的方法,但需要一个重写的Equals方法,该方法在ID上等于,或者您必须提供一个比较器(请参阅svick的答案)。
var result = stockPackageList.Except(packageList).ToList();
资源在msdn中可以找到许多LINQ samlehttp://msdn.microsoft.com/en-us/vcsharp/aa336746
我将把答案的开头部分留作参考:
蛮力方式:
var result = stockPackageList
.Where(x => packageList.All(package => x.Id != package.Id))
.ToList();
应该做到这一点。您只需要将lambda语法转换为vb.net。
此查询将筛选stockPackageList
中ID不存在于packageList
的所有项目中的所有项目。
您可以反转查询:
var result = stockPackageList
.Where(x => packageList.Any(package => x.Id == package.Id) == false)
.ToList();
如果packageList
中的任何项具有匹配的id,则Any
查询将返回true。此查询运行速度应该稍快,因为它不必像All
那样遍历整个集合。
使用等式:
如果您的包对象实现IEquatable<Package>
,您可以将代码缩短为
var result = stockPackageList
.Where(x => packageList.Contains(x) == false)
.ToList();
使用哈希集:
如果你想使用哈希集,你可以做
var hash = new HashSet<string>(packageList.Select(x=>x.Id));
var result = stockPackageList.Where(x => hash.Contains(x.Id) == false).ToList();
正如faester和Ivan Danilov所指出的,当列表变大时,这节省了计算时间。
不能真正阅读VB代码,但如果你想在l2中获得不在l1中的项目-
她是一个样本C#代码
public class SomeObject
{
public string ID { get; set; }
}
public class SomeObjectComparer : IEqualityComparer<SomeObject>
{
public bool Equals(SomeObject x, SomeObject y)
{
return x.ID == y.ID;
}
public int GetHashCode(SomeObject obj)
{
return obj.ID.GetHashCode();
}
}
class Program
{
static void Main(string[] args)
{
List<SomeObject> l1, l2;
// lists init ...
IEqualityComparer<SomeObject> comparer = new SomeObjectComparer();
List<SomeObject> l3 = l2.Except(l1, comparer).ToList();
}
}
您的方法的渐近运行时间为O(m*n),其中m和n是集合的大小。
你应该为O(m lg n)而奋斗。当然,您需要搜索这两个集合,但您可以在O(n)中构建其中一个集合的哈希集,并平均在O(1)中执行查询,因此您应该将一个列表复制到一个哈希集,然后遍历第二个列表,查找前者中的值。
static void Sort()
{
List<Package> a = new List<Package>();
List<Package> b = new List<Package>();
Func<Package, int> idExtractor = x => x.ID;
var hash = new HashSet<Package>(a, new IDComparer<Package, int>(idExtractor));
a.AddRange(b.Where(x => !hash.Contains(x)));
}
class IDComparer<ObjectType, KeyType>
: IEqualityComparer<ObjectType>
where KeyType : IComparable
{
private Func<ObjectType, KeyType> idExtractor;
public IDComparer(Func<ObjectType, KeyType> idExtractor)
{
this.idExtractor = idExtractor;
}
public bool Equals(ObjectType x, ObjectType y)
{
return idExtractor(x).Equals(idExtractor(y));
}
public int GetHashCode(ObjectType obj)
{
return idExtractor(obj).GetHashCode();
}
}
您可以使用Except()
:
result = stockpackageList.Except(PackageList).ToList();
这假设Package
已过载Equals()
来比较Id
s。如果没有,则必须使用IEqualityComparer
,例如以下答案中的那个:
result = stockpackageList.Except(PackageList,
new KeyEqualityComparer<Package, int>(p => p.Id))
.ToList();
至于时间复杂性,您的解决方案无法正常工作,因此它的复杂性无关紧要。Except()
的复杂度是O(N+M),因为它首先从第一个集合(O(N))中创建一个哈希集,然后尝试从第二个集合(0(M))中删除每个项目,然后返回结果。
var dic = new Dictionary<string, Package>(p1.Count); // capacity here is important
foreach (var p in p1)
dic.Add(p.Id, p);
var result = p2.Where(p => !dic.ContainsKey(p.Id)).ToList();
填充字典是几乎O(n)乘以p1。计数。并且每次搜索都是O(1)。所以我们有一些接近线性复杂性的东西。