C#3新手:这应该用linq完成吗？

Question

我有两个单词列表.我想计算两个列表中存在的大于3个字符的单词.使用C#你会如何解决它？

Answer 1

我会用

var count = Enumerable.Intersect(listA, listB).Count(word => word.Length > 3);

假设listA和listB类型IEnumerable<String>.

Answer 2

假设列表1的长度为N,列表2的长度为M:

我会先过滤,因为这是一个廉价的操作O(N + M)然后做交叉,一个相对昂贵的操作基于当前的实现.Intersect调用的成本很复杂,并且基本上由散列函数的行为驱动:

• 如果散列函数较差,则性能可降级为O(N*M)(因为一个列表中的每个字符串都会针对另一个列中的每个流进行检查).
• 如果性能良好,那么成本就像哈希中的查找一样,因此这是O(1),因此M的成本检查哈希和M的成本来构造哈希,所以O(N + M)in时间,但在太空中额外花费O(N).
  • 背衬装置的构造将成为性能方面的杀手.
  • 如果您知道这两个列表已经排序,那么您可以编写自己的Intersects检查,其中包含恒定的空间开销和O(N + M)最差情况下的运行时间,更不用说优秀的内存位置.

这让你:

int count = Enumerable.Intersect(
    list1.Where(word => word.Length > 3),
    list2.Where(word => word.Length > 3)).Count();

顺便提一下,Enumerable.Intersect方法的性能行为可能会根据参数的顺序发生很大变化.

在大多数情况下,使第一个参数中较小的一个产生更快,更高效的内存代码,第一个参数用于构造支持临时(基于散列)的Set.这当然是编码为(隐藏的)实现细节,因此只有在性能分析后显示为问题并且如果是这样突出显示为微优化时才应考虑.

list2上的第二个过滤器从根本上说是不正确的(因为Intersects无论如何都会删除这些条目)

如果很可能以下更快

int count = Enumerable.Intersect(
    list1.Where(word => word.Length > 3),
    list2).Count();

然而,与计算它们的哈希码相比,长度过滤对于长串非常便宜.只有通过适合您使用的输入进行基准测试才能找到更好的产品.