算法手记附1 随机化输入与计时器

Changwei | 9/29/2014 10:50:00 AM


1.随机化输入

在快速排序算法的使用中,发现其性能是不稳定的,它的速度取决于输入情况,最好的情况下复杂度为O(NlogN),最坏情况下为O(N^2). 

最简单的优化方法是随机化输入,打乱输入数组顺序,这样可以将不良输入带来低劣性能的可能性降到最低,对于预测算法的运行时间是十分重要的。

考虑到,在c++中std标准库已有random_shuffle函数,其他语言也有类似方法,但c#并没有此标准函数,这样我索性自己实现一个。

设计:

这里按照最简单的O(N)来设计,需要N次交换,实现起来无疑很简单。

实现:

public class RandomShuffle
    {
        private static Random rd;
        private static int N;
        public static IComparable[] shuffle(IComparable[] a)
        {
            rd = new Random();
            N = a.Length;
            for (var i = 0; i < N; i++)
            {
                var newPosition = rd.Next(N);
                var temp = a[i];
                a[i] = a[newPosition];
                a[newPosition] = temp;
            }
            return a;
        }
}

总结:

这里使用迭代写起来会更简洁明了,但是大规模的迭代会导致线程栈StackoverflowException,所以使用循环会更安全。

 

2.计时器

衡量一个算法的性能主要有两个方面:运行时间与内存性能。算法分析中,运行时长是一个很重要的衡量指标,但准确测量给定程序的运行时长时间很困难的事情,不过幸运地是我们只需要近似的结果就可以了。

我们可以使用系统API来实现一个精度尚可的计时器,可以帮助我们验证算法的速度。

设计:

设计一个Stopwatch类,它的elapsedTime()方法能够输出程序执行时间。它的实现基于.NET框架的DateTime类,能返回以毫秒/秒计数的结果。

实现:

 public class Stopwatch
    {
        private static DateTime startTime;
        public Stopwatch(DateTime time)
        {
            startTime = time;
        }
        public void elapsedTime()
        {
            DateTime endTime = DateTime.Now;
            double time = (endTime.Hour - startTime.Hour) * 3600 * 1000 + (endTime.Minute - startTime.Minute) * 60 * 1000
                          + (endTime.Second - startTime.Second) * 1000 + (endTime.Millisecond - startTime.Millisecond);
            if (time > 1000)
            {
                time /= 1000;
                Console.WriteLine("time: " + time + "s");
            }
            else
                Console.WriteLine("time: " + time + "ms");
        }
    }

总结:

这样的计时器虽然精度不高,但是足以用来简单地评估算法的性能了。