相交和任何或包含和任何.找到至少一个共同元素更有效率？

Question

如果我有两个列表并且我想知道是否至少有一个共同元素,我有两个选项:

lst1.Intersect(lst2).Any();

Lst1.Any(x => lst2.Contains(x));

这两个选项给了我预期的结果,但是我不知道什么是最好的选择.哪个更有效率？为什么？

谢谢.

编辑:当我创建这篇文章时,除了解决方案之外,我正在寻找原因.我知道我可以运行测试,但我不知道结果的原因.一个比另一个快？总是一种解决方案最好吗？

所以出于这个原因,我接受了马修的答案,不仅是为了测试代码,而且还解释了什么时候比其他人好,为什么.我非常感谢尼古拉斯和奥伦的贡献.

谢谢.

Answer 1

奥伦的回答在秒表的使用方式上有误.Any()在测量所用的时间之后,它不会在循环结束时复位.

注意它是如何回到循环的开始,秒表永远不会Reset()使添加的时间intersect 包括所用的时间Any().

以下是更正后的版本.

在任何调试器外部运行的发布版本会在我的PC上显示此结果:

Intersect:    1ms
Any:       6743ms

请注意我是如何为此测试制作两个不重叠的字符串列表.另请注意,这是最糟糕的测试.

如果有许多交叉点(或者在数据开始附近碰巧发生交叉点)那么Oren说它Any()应该更快是完全正确的.

如果真实数据通常包含交叉点,那么使用它可能更好Any().否则,请使用Intersect().它非常依赖数据.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace Demo
{
    class Program
    {
        void run()
        {
            double intersect = 0;
            double any = 0;

            Stopwatch stopWatch = new Stopwatch();

            List<string> L1 = Enumerable.Range(0, 10000).Select(x => x.ToString()).ToList();
            List<string> L2 = Enumerable.Range(10000, 10000).Select(x => x.ToString()).ToList();

            for (int i = 0; i < 10; i++)
            {
                stopWatch.Restart();
                Intersect(L1, L2);
                stopWatch.Stop();
                intersect += stopWatch.ElapsedMilliseconds;

                stopWatch.Restart();
                Any(L1, L2);
                stopWatch.Stop();
                any += stopWatch.ElapsedMilliseconds;
            }

            Console.WriteLine("Intersect: " + intersect + "ms");
            Console.WriteLine("Any: " + any + "ms");
        }

        private static bool Any(List<string> lst1, List<string> lst2)
        {
            return lst1.Any(lst2.Contains);
        }

        private static bool Intersect(List<string> lst1, List<string> lst2)
        {
            return lst1.Intersect(lst2).Any();
        }            

        static void Main()
        {
            new Program().run();
        }
    }
}

为了比较的目的,我编写了自己的测试比较int序列:

intersect took 00:00:00.0065928
any took       00:00:08.6706195

代码:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace Demo
{
    class Program
    {
        void run()
        {
            var lst1 = Enumerable.Range(0, 10000);
            var lst2 = Enumerable.Range(10000, 10000);

            int count = 10;

            DemoUtil.Time(() => lst1.Intersect(lst2).Any(), "intersect", count);
            DemoUtil.Time(() => lst1.Any(lst2.Contains),     "any",      count);
        }

        static void Main()
        {
            new Program().run();
        }
    }

    static class DemoUtil
    {
        public static void Print(this object self)
        {
            Console.WriteLine(self);
        }

        public static void Print(this string self)
        {
            Console.WriteLine(self);
        }

        public static void Print<T>(this IEnumerable<T> self)
        {
            foreach (var item in self)
                Console.WriteLine(item);
        }

        public static void Time(Action action, string title, int count)
        {
            var sw = Stopwatch.StartNew();

            for (int i = 0; i < count; ++i)
                action();

            (title + " took " + sw.Elapsed).Print();
        }
    }
}

如果我还通过将列表更改为此并将其增加到10000 来为重叠范围计时count:

var lst1 = Enumerable.Range(10000, 10000);
var lst2 = Enumerable.Range(10000, 10000);

我得到这些结果:

intersect took 00:00:03.2607476
any took 00:00:00.0019170

在这种情况下Any()显然要快得多.

结论

最糟糕的表现非常糟糕,Any()但可以接受Intersect().最好的表现是非常好的Any()和坏的Intersect().(最好的情况Any()可能是最糟糕的情况Intersect()!)

Any()在最坏的情况下,该方法是O(N ^ 2),在最好的情况下是O(1).该Intersect()方法总是O(N)(因为它使用散列,而不是排序,否则它将是O(N(Log(N))).

您还必须考虑内存使用情况:该Intersect()方法需要获取其中一个输入的副本,而Any()不是.

因此,为了做出最佳决策,您确实需要了解实际数据的特征,并实际执行测试.

如果你真的不想Any()在最坏的情况下变成O(N ^ 2),那么你应该使用Intersect().但是,您最好使用Any().

当然,大部分时间都不重要!

除非您发现这部分代码成为瓶颈,否则这仅仅是学术兴趣.如果没有问题,你不应该浪费时间进行这种分析.:)