C# Union vs Contains 用于连续数据列表
C# Union vs Contains for lists of continuous data
我很难找到一个问题的答案,我有一些特定于我正在处理的代码,而且我似乎无法找到一些关于 Union 在 C# 中的核心机制如何工作的文档。所以问题是这样的。
我有一组与此示例类似的数据:
object[] someMainTypeArray = new object [n];
List<object> objList2 = new List<object>();
foreach ( object obj in someMainTypeArray ) {
List<object> objList1 = new List<object>() { "1","2","3" };
//each obj has a property that will generate a list of data
//objList1 is the result of the data specific to obj
//some of this data could be duplicates
//Which is better, this:
foreach ( object test in objList1 ) {
if ( !objList2.Contains( test ) ) {
objList2.Add( test );
}
}
//or this:
objList2 = objList2.Union( objList1 ).ToList();
//Also, assume this has to happen anywhere from 0 to 60 times per second
}
让Union包办效率更高吗?还是使用 Contains 比较每个元素更好?
如果两者均否,使用尽可能少的处理时间填充唯一列表的最佳方法是什么?
效率是关键。另外,这不是家庭作业,也不是任何与工作有关的东西,只是与学习有关。
列表在运行时是连续的,最终会被清除并重新填充。列表中的更改用于根据与此示例完全相似的最终结果列表是否用于得出最终列表,如果该列表为空,则为失败条件,如果该列表不为空,这是一个成功条件。
这是所创建列表之一的相关代码片段:
Player.ClearMoves();
List<Pair<BoardLocation, BoardLocation>> attacking = new List<Pair<BoardLocation, BoardLocation>>();
foreach ( ChessPiece p in Board[this.Player.Opponent] ) {
if ( p.TheoryMove( this.Location ) ) {
foreach ( Pair<BoardLocation , BoardLocation> l in Utility.GetLocations( p.Location , this.Location ) ) {
if ( !attacking.Contains( l ) ) {
attacking.Add( l );
}
}
}
}
if ( attacking.Count < 1 ) {
return false;
}
您可以在 reference source 中找到 Enumerable.Union
实现。
这是它的工作原理:
public static IEnumerable<TSource> Union<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second) {
if (first == null) throw Error.ArgumentNull("first");
if (second == null) throw Error.ArgumentNull("second");
return UnionIterator<TSource>(first, second, null);
}
static IEnumerable<TSource> UnionIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
Set<TSource> set = new Set<TSource>(comparer);
foreach (TSource element in first)
if (set.Add(element)) yield return element;
foreach (TSource element in second)
if (set.Add(element)) yield return element;
}
如您所见,Union
将遍历来自这些来源的可枚举对象和 yield 对象。与所有 Linq 方法一样,它不会创建列表,而是用作生成器函数。该列表只会在您调用 .ToList()
.
时创建
为了避免重复,它将使用 Set
并在产生它之前尝试添加一个元素。如果添加到集合中成功,那么该元素还没有在那里,所以它可以被 yield。
请注意,集合对于查找元素是否存在于其中非常有效。它们以摊销常数时间提供项目查找。所以这绝对比你的 objList2.Contains
更有效,后者需要一遍又一遍地遍历列表以确定每个元素是否存在于其中。
另请注意,构建 Union
是为了维护输入枚举的顺序。如果你不需要那个,那么你可以完全跳过这个并首先使用 Set
。如果您计划始终将新项目添加到同一目标集,这将特别有用,因为它会重用结构:
HashSet<object> set = new HashSet<object>();
foreach (…)
{
List<object> objList1 = …
// expand the set with the items from `objList1`
set.UnionWith(objList1);
}
如果您首先避免创建 objList1
并直接将您的项目添加到集合中,那就更好了——如果这对您的用例来说是可能的。
如果您查看 reference source for the LINQ extensions(搜索 UnionIterator
),您将看到 Union
通过使用 Set<T>
来跟踪哪些项目已被枚举超过。遗憾的是,Set<T>
是库的内部 class,因此您不能直接使用它。但是有一个名为 HashSet<T>
的类似集合您可能会用到。
您的实施中的主要低效问题之一可能是您在外循环的每次迭代中为 objList2
创建了一个新列表。这将每次触发迭代和内存分配。由于您是通过嵌套循环构建列表,因此我建议您执行以下操作之一:
- 将所有内容添加到
List<T>
并在完成后使用 .Distinct
过滤掉重复项。此方法也使用 Set<T>
内部 class,但与将多个调用链接到 Union
不同,它只会使用单个 Set
来构建唯一列表。
- 使用
HashSet<T>
构建一个始终包含唯一项目列表的集合。
我很难找到一个问题的答案,我有一些特定于我正在处理的代码,而且我似乎无法找到一些关于 Union 在 C# 中的核心机制如何工作的文档。所以问题是这样的。
我有一组与此示例类似的数据:
object[] someMainTypeArray = new object [n];
List<object> objList2 = new List<object>();
foreach ( object obj in someMainTypeArray ) {
List<object> objList1 = new List<object>() { "1","2","3" };
//each obj has a property that will generate a list of data
//objList1 is the result of the data specific to obj
//some of this data could be duplicates
//Which is better, this:
foreach ( object test in objList1 ) {
if ( !objList2.Contains( test ) ) {
objList2.Add( test );
}
}
//or this:
objList2 = objList2.Union( objList1 ).ToList();
//Also, assume this has to happen anywhere from 0 to 60 times per second
}
让Union包办效率更高吗?还是使用 Contains 比较每个元素更好?
如果两者均否,使用尽可能少的处理时间填充唯一列表的最佳方法是什么?
效率是关键。另外,这不是家庭作业,也不是任何与工作有关的东西,只是与学习有关。
列表在运行时是连续的,最终会被清除并重新填充。列表中的更改用于根据与此示例完全相似的最终结果列表是否用于得出最终列表,如果该列表为空,则为失败条件,如果该列表不为空,这是一个成功条件。
这是所创建列表之一的相关代码片段:
Player.ClearMoves();
List<Pair<BoardLocation, BoardLocation>> attacking = new List<Pair<BoardLocation, BoardLocation>>();
foreach ( ChessPiece p in Board[this.Player.Opponent] ) {
if ( p.TheoryMove( this.Location ) ) {
foreach ( Pair<BoardLocation , BoardLocation> l in Utility.GetLocations( p.Location , this.Location ) ) {
if ( !attacking.Contains( l ) ) {
attacking.Add( l );
}
}
}
}
if ( attacking.Count < 1 ) {
return false;
}
您可以在 reference source 中找到 Enumerable.Union
实现。
这是它的工作原理:
public static IEnumerable<TSource> Union<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second) {
if (first == null) throw Error.ArgumentNull("first");
if (second == null) throw Error.ArgumentNull("second");
return UnionIterator<TSource>(first, second, null);
}
static IEnumerable<TSource> UnionIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
Set<TSource> set = new Set<TSource>(comparer);
foreach (TSource element in first)
if (set.Add(element)) yield return element;
foreach (TSource element in second)
if (set.Add(element)) yield return element;
}
如您所见,Union
将遍历来自这些来源的可枚举对象和 yield 对象。与所有 Linq 方法一样,它不会创建列表,而是用作生成器函数。该列表只会在您调用 .ToList()
.
为了避免重复,它将使用 Set
并在产生它之前尝试添加一个元素。如果添加到集合中成功,那么该元素还没有在那里,所以它可以被 yield。
请注意,集合对于查找元素是否存在于其中非常有效。它们以摊销常数时间提供项目查找。所以这绝对比你的 objList2.Contains
更有效,后者需要一遍又一遍地遍历列表以确定每个元素是否存在于其中。
另请注意,构建 Union
是为了维护输入枚举的顺序。如果你不需要那个,那么你可以完全跳过这个并首先使用 Set
。如果您计划始终将新项目添加到同一目标集,这将特别有用,因为它会重用结构:
HashSet<object> set = new HashSet<object>();
foreach (…)
{
List<object> objList1 = …
// expand the set with the items from `objList1`
set.UnionWith(objList1);
}
如果您首先避免创建 objList1
并直接将您的项目添加到集合中,那就更好了——如果这对您的用例来说是可能的。
如果您查看 reference source for the LINQ extensions(搜索 UnionIterator
),您将看到 Union
通过使用 Set<T>
来跟踪哪些项目已被枚举超过。遗憾的是,Set<T>
是库的内部 class,因此您不能直接使用它。但是有一个名为 HashSet<T>
的类似集合您可能会用到。
您的实施中的主要低效问题之一可能是您在外循环的每次迭代中为 objList2
创建了一个新列表。这将每次触发迭代和内存分配。由于您是通过嵌套循环构建列表,因此我建议您执行以下操作之一:
- 将所有内容添加到
List<T>
并在完成后使用.Distinct
过滤掉重复项。此方法也使用Set<T>
内部 class,但与将多个调用链接到Union
不同,它只会使用单个Set
来构建唯一列表。 - 使用
HashSet<T>
构建一个始终包含唯一项目列表的集合。