返璞归真:旧的.NET代码的大o表示法问题和提高用于LINQ延迟执行的循环


[原文发表地址] Back to Basics: Big O notation issues with older .NET code and improving for loops with LINQ deferred execution

[原文发表时间] 2011-06-23 07:00       

 

返璞归真:旧的.NET代码的大o表示法问题和提高用于LINQ延迟执行的循环

今天早些时候Brad Wilson和我讨论Jostein Kjønigsen一个关于G+帖子,他说道,“看你能不能在这些代码中发现O(n^2) 错误。 ”

        public IEnumerable<Process> GetProcessesForSession(string processName, int sessionId)

        {

            var processes = Process.GetProcessByName(processName);

            var filtered = from p in processes

                           where p.SessionId == sessionId

                           select p;

            return filtered;

        }

这是一种相当直接的方法来调用.NET BCL (基类库)的方法并通过LINQ过滤结果。当然,当任何方法调用一个方法,你看不到方法内部的执行情况(基本上都是如此),你失去了控制。我们并不知道GetProcessesByName做了什么。

让我们看一下在反射器 .NET Framework方法的源代码。该方法调用Process.GetProcessesByName(string)

        public static Process[] GetProcessesByName(string processName)

        {

            return GetProcessesByName(processName, ".");

        }

看起来这个方法是一个重载方法将"."传递到下一个方法Process.GetProcessesByName(string, string),这里的第二个参数是机器名。

上面的Process.GetProcessesByName(string, string)方法为机器获取所有的进程(在我们的例子中,该机器为本机),然后运转,通过他们在每个方法上做一下比较,以生成结果数组来返回链。

        public static Process[] GetProcessesByName(string processName, string machineName)

        {

            if (processName == null)

            {

                processName = string.Empty;

            }

            Process[] processes = GetProcesses(machineName);

            ArrayList list = new ArrayList();

            for (int i = 0; i < processes.Length; i++)

            {

                if (string.Equals(processName, processes[i].ProcessName, StringComparison.OrdinalIgnoreCase))

                {

                    list.Add(processes[i]);

                }

            }

            Process[] array = new Process[list.Count];

            list.CopyTo(array, 0);

            return array;

        }

如果我们看一下GetProcesses(string)方法内部,会发现这是另一个循环。这更加靠近.NET调用Win32的地方,而且由于这些类是内部类所以我做不了什么来修改这个方法除了完全重写内部实现。然而,我认为我已经展示了我们有了至少两个循环,并且可能有三个甚至四个循环。

        public static Process[] GetProcesses(string machineName)

        {

            bool isRemoteMachine = ProcessManager.IsRemoteMachine(machineName);

            ProcessInfo[] processInfos = ProcessManager.GetProcessInfos(machineName);

            Process[] processArray = new Process[processInfos.Length];

            for (int i = 0; i < processInfos.Length; i++)

            {

                ProcessInfo processInfo = processInfos[i];

                processArray[i] = new Process(machineName, isRemoteMachine, processInfo.processId, processInfo);

            }

            return processArray;

        }

这些代码真是典型的.NET 2002-2003的代码吧(更不用说Java, C++Pascal)。方法返回填充数组,用其他方法更偏重过滤和排序。

当使用该.NET API程序且循环遍历结果几次时,我是通过一个链执行for(), for(), for(),如执行O(4n)循环。

注意:很明显,O(4n)就是O(n)。添加一个数就像我不是O表示法的一部分。我只是想说我们想避免O(cn)的情况,因为c是一个很大的数且足以影响性能。

clip_image001[6]

有时候你会看到嵌套for()循环比如这个,因此这里的O(n^3)使事情更快且混乱。

clip_image002[6]

我认为,LINQ比大家认识到的更加重要。当它第一次出现的时候有些人说:“这就是所有的?

我认为这是一种不幸。LINQ和“延迟执行”的概念如此有力但我认为很多.NET编程人员根本没有花费时间来思考这个概念。

这里是一个通过vs列表并列运转的简单的例子 对比使用yield的情况。该数组版本是在开始做所有的工作,但yield版本可以计算。想象一个GetFibonacci()方法。一个yield版本能够“刚好赶上”计算值然后生成他们,但一个数组版本必须预先估算和预先分配。

        public void Consumer()

        {

            foreach (int i in IntegersList())

            {

                Console.WriteLine(i.ToString());

            }

            foreach (int i in IntegersYield())

            {

                Console.WriteLine(i.ToString());

            }

        }

        public IEnumerable<int> IntegersYield()

        {

            yield return 1;

            yield return 2;

            yield return 4;

            yield return 8;

            yield return 16;

            yield return 16777216;

        }

        public IEnumerable<int> IntegersList()

        {

            return new int[] { 1, 2, 4, 8, 16, 16777216 };

        }

回到GetProcess的例子。这里列出了两个问题。

首先,底层执行时 GetProcessesInfos最终获得调用一个 bummer,但是正是因为那种方式说明 P/Invoke怎样运行且底层 Win32 AP I 怎样返回我们需要的数据。如果底层API更精细必然更好。但比起更大的有(或许在这里,没有)一个 LINQ友好的 API的元问题,这个对我的吸引力不大。

第二个且更有趣的问题(在我看来)就是2002-era .NET基类库不是真正为 LINQ-友好安装的想法。没有哪个 APIs返回 LINQ-友好 填充或 IEnumerable<anything>,因此,当你修改 全部的过滤数组时你最终以 O(cn)问题结尾,因为反对完美的延迟 LINQ链。

当你发现返回数组的数组的数组并循环,过滤和排序,你会意识到发生了什么然后考虑你可能在做无效循环,那么到使用  LINQ和延迟执行的时候了。

clip_image003[6]

这里是简单的转换试图改变在典型"Array/List"样式中的第一次实施:

            ArrayList list = new ArrayList();

            for (int i = 0; i < processes.Length; i++)

            {

                if (string.Equals(processName, processes[i].ProcessName, StringComparison.OrdinalIgnoreCase))

                {

                    list.Add(processes[i]);

                }

            }

            Process[] array = new Process[list.Count];

            list.CopyTo(array, 0);

            return array;

对这种更 LINQ的方式。注意从一个LINQ查询延迟执行中返回是可链化的。我们想集合一个链式排序并过滤操作和执行他们一次而不是通过 for()循环遍历许多链表很多次。

            if (processName == null) { processName = string.Empty; }

            Process[] processes = Process.GetProcesses(machineName); //stop here…can’t go farther?

            return from p in processes

                   where String.Equals(p.ProcessName, processName, StringComparison.OrdinalIgnoreCase)

                   select p; //the value of the LINQ expression being returned is an IEnumerable<Process> object th

 

这是示例程序中的要执行的所有事情。

        static void Main(string[] args)

        {

            var myList = GetProcessesForSession("chrome.exe", 1);

        }

        public static IEnumerable<Process> GetProcessesForSession(string processName, int sessionID)

        {

            //var processes = Process.GetProcessesByName(processName);

            var processes = HanselGetProcessesByName(processName); //my LINQy implementation

            var filtered = from p in processes

                           where p.SessionId == sessionID

                           select p;

            return filtered;

        }

        private static IEnumerable<Process> HanselGetProcessesByName(string processName)

        {

            return HanselGetProcessesByName(processName, ".");

        }

        private static IEnumerable<Process> HanselGetProcessesByName(string processName, string machineName)

        {

            if (processName == null)

            {

                processName = string.Empty;

            }

            Process[] processes = Process.GetProcesses(machineName); //can’t refactor farther because of internals.

            //"the value of the LINQ expression being returned is an IEnumerable<Process> object that uses "yield return" under the hood" (thanks Mehrdad!)

            return from p in processes where String.Equals(p.ProcessName == processName, StringComparison.OrdinalIgnoreCase) select p;

            /* the stuff above replaces the stuff below */

            //ArrayList list = new ArrayList();

            //for (int i = 0; i < processes.Length; i++)

            //{

            // if (string.Equals(processName, processes[i].ProcessName, StringComparison.OrdinalIgnoreCase))

            // {

            // list.Add(processes[i]);

            // }

            //}

            //Process[] array = new Process[list.Count];

            //list.CopyTo(array, 0);

            //return array;

        }

对我来说这确实是一个很有趣的话题,而且我也对你的观点很有兴趣,亲爱的读者。由于部分.NET Framework正在扩展到包括支持 异步操作,我很疑惑 BCL中是否有其他地方应更新以使 LINQ更友好。或者,可能这完全不是一个问题。

你认为呢?


Comments (0)

Skip to main content