将ICollection成员与其自身进行比较
本文关键字:比较 ICollection 成员 | 更新日期: 2023-09-27 18:20:24
有什么最便宜的方法可以将ICollection与自身进行比较吗。
这是我的代码:
public IEnumerable<Pet> speciesChecker()
{
foreach (Pet pet in _pets)
{
bool wantedSpecies = true;
foreach (Pet pet2 in _pets)
{
if (pet2 != pet && pet.Species == pet2.Species)
{
wantedSpecies = false;
break;
}
}
if (wantedSpecies) yield return pet;
}
}
我的代码的时间复杂度是多少,我只知道它小于O(N^2),如果我从foreach内部循环中删除"break",时间复杂度将为O(N^2)。如果我错了,请纠正我。
以下是我对它的看法:
var q = list.GroupBy (l => l.Species)
.Where (l => l.ElementAtOrDefault(1) == null)
.Select (l => l.Key)
GroupBy
将在内部使用HashSet,因此O(N)ElementAtOrDefault(1)
只需要将枚举器移动一步,因此不会为O(n)
I认为这段代码也做同样的事情。在这种情况下,这是一个O(N)算法。诀窍是将宠物存储在按物种编制索引的词典中。
public IEnumerable<Pet> speciesChecker()
{
var species = new Dictionary<Species, List<Pet>>();
foreach (Pet pet in _pets)
{
// create the list if it doesn't exist
if (!species.ContainsKey(pet.Species))
species[pet.Species] = new List<Pet>();
species[pet.Species].Add(pet);
}
// foreach species, if there is only one pet of that species, then return it
foreach (var speciesPets in species.Values)
{
if (speciesPets.Count() == 1)
yield return speciesPets.First();
}
yield break;
}
您还可以使用以下内容,也应该是O(N):
public IEnumerable<Pet> speciesChecker ()
{
_pets.GroupBy (p => p.Species)
.Select (g => new List<Pet> (g))
.Where (l => l.Count == 1)
.SelectMany (l => l);
}
额外的Select (g => new List<Pet> (g))
可能是多余的,但我相信这将有助于避免第二次迭代整个分组逻辑,我相信这会导致O(N^2)。
编辑:Magnus对在O(n)中操作的List构造函数破坏目的的好评论。。。
怎么样:
public IEnumerable<Pet> speciesChecker ()
{
var groups = _pets.GroupBy (p => p.Species);
foreach (var grp in _pets.GroupBy (p => p.Species))
using (var e = grp.GetEnumerator ()) {
if (!e.MoveNext ())
continue;
var first = e.Current;
if (e.MoveNext ())
continue;
yield return first;
}
}
我认为这是尽可能优化的,并且将在O(n)中工作。我们也避免使用IEnumerable<T>.Any ()
或IEnumerable<T>.Count ()
扩展方法。
想法?
设n
为_pets collection
的长度
需要中断的步骤数:
1+2+3+...+n = n*(n+1)/2 =n^2/2 + n/2 = O(n^2) (for each pet in _pets);
有两个简单的规则如何从维基计算O:
如果f(x)是几个项的和保持了增长率,而忽略了所有其他因素。
如果f(x)是几个因子的乘积,则不依赖于x的乘积)。
无中断所需步骤数:
n+n+n+...+n = n^2 = O(n^2)