1.4.37

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

数据量比较大时才会有比较明显的差距。

代码

FixedCapacityStackOfInts

using System;
using System.Collections;
using System.Collections.Generic;

namespace _1._4._37
{
    /// <summary>
    /// 固定大小的整型数据栈。
    /// </summary>
    class FixedCapacityStackOfInts : IEnumerable<int>
    {
        private int[] a;
        private int N;

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        /// <param name="capacity">栈的大小。</param>
        public FixedCapacityStackOfInts(int capacity)
        {
            this.a = new int[capacity];
            this.N = 0;
        }

        /// <summary>
        /// 检查栈是否为空。
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            return this.N == 0;
        }

        /// <summary>
        /// 检查栈是否已满。
        /// </summary>
        /// <returns></returns>
        public bool IsFull()
        {
            return this.N == this.a.Length;
        }

        /// <summary>
        /// 将一个元素压入栈中。
        /// </summary>
        /// <param name="item">要压入栈中的元素。</param>
        public void Push(int item)
        {
            this.a[this.N] = item;
            this.N++;
        }

        /// <summary>
        /// 从栈中弹出一个元素,返回被弹出的元素。
        /// </summary>
        /// <returns></returns>
        public int Pop()
        {
            this.N--;
            return this.a[this.N];
        }

        /// <summary>
        /// 返回栈顶元素(但不弹出它)。
        /// </summary>
        /// <returns></returns>
        public int Peek()
        {
            return this.a[this.N - 1];
        }

        public IEnumerator<int> GetEnumerator()
        {
            return new ReverseEnmerator(this.a);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        private class ReverseEnmerator : IEnumerator<int>
        {
            private int current;
            private int[] a;

            public ReverseEnmerator(int[] a)
            {
                this.current = a.Length;
                this.a = a;
            }

            int IEnumerator<int>.Current => this.a[this.current];

            object IEnumerator.Current => this.a[this.current];

            void IDisposable.Dispose()
            {
                this.current = -1;
                this.a = null;
            }

            bool IEnumerator.MoveNext()
            {
                if (this.current == 0)
                    return false;
                this.current--;
                return true;
            }

            void IEnumerator.Reset()
            {
                this.current = this.a.Length;
            }
        }
    }
}

FixedCapacityStack\<Item>

using System;
using System.Collections;
using System.Collections.Generic;

namespace _1._4._37
{
    /// <summary>
    /// 固定大小的栈。
    /// </summary>
    class FixedCapacityStack<Item> : IEnumerable<Item>
    {
        private Item[] a;
        private int N;

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        /// <param name="capacity">栈的大小。</param>
        public FixedCapacityStack(int capacity)
        {
            this.a = new Item[capacity];
            this.N = 0;
        }

        /// <summary>
        /// 检查栈是否为空。
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            return this.N == 0;
        }

        /// <summary>
        /// 检查栈是否已满。
        /// </summary>
        /// <returns></returns>
        public bool IsFull()
        {
            return this.N == this.a.Length;
        }

        /// <summary>
        /// 将一个元素压入栈中。
        /// </summary>
        /// <param name="item">要压入栈中的元素。</param>
        public void Push(Item item)
        {
            this.a[this.N] = item;
            this.N++;
        }

        /// <summary>
        /// 从栈中弹出一个元素,返回被弹出的元素。
        /// </summary>
        /// <returns></returns>
        public Item Pop()
        {
            this.N--;
            return this.a[this.N];
        }

        /// <summary>
        /// 返回栈顶元素(但不弹出它)。
        /// </summary>
        /// <returns></returns>
        public Item Peek()
        {
            return this.a[this.N - 1];
        }

        public IEnumerator<Item> GetEnumerator()
        {
            return new ReverseEnmerator(this.a);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        private class ReverseEnmerator : IEnumerator<Item>
        {
            private int current;
            private Item[] a;

            public ReverseEnmerator(Item[] a)
            {
                this.current = a.Length;
                this.a = a;
            }

            Item IEnumerator<Item>.Current => this.a[this.current];

            object IEnumerator.Current => this.a[this.current];

            void IDisposable.Dispose()
            {
                this.current = -1;
                this.a = null;
            }

            bool IEnumerator.MoveNext()
            {
                if (this.current == 0)
                    return false;
                this.current--;
                return true;
            }

            void IEnumerator.Reset()
            {
                this.current = this.a.Length;
            }
        }
    }
}

测试函数:

using System;
using Measurement;

namespace _1._4._37
{
    /// <summary>
    /// FixedCapacityStackOfInts 测试类。
    /// </summary>
    public static class DoubleTest
    {
        private static readonly int MAXIMUM_INTEGER = 1000000;

        /// <summary>
        /// 返回对 n 个随机整数的栈进行 n 次 push 和 n 次 pop 所需的时间。
        /// </summary>
        /// <param name="n">随机数组的长度。</param>
        /// <returns></returns>
        public static double TimeTrial(int n)
        {
            int[] a = new int[n];
            FixedCapacityStackOfInts stack = new FixedCapacityStackOfInts(n);
            Random random = new Random(DateTime.Now.Millisecond);
            for (int i = 0; i < n; ++i)
            {
                a[i] = random.Next(-MAXIMUM_INTEGER, MAXIMUM_INTEGER);
            }
            Stopwatch timer = new Stopwatch();
            for (int i = 0; i < n; ++i)
            {
                stack.Push(a[i]);
            }
            for (int i = 0; i < n; ++i)
            {
                stack.Pop();
            }
            return timer.ElapsedTimeMillionSeconds();
        }

        /// <summary>
        /// 返回对 n 个随机整数的栈进行 n 次 push 和 n 次 pop 所需的时间。
        /// </summary>
        /// <param name="n">随机数组的长度。</param>
        /// <returns></returns>
        public static double TimeTrialGeneric(int n)
        {
            int[] a = new int[n];
            FixedCapacityStack<int> stack = new FixedCapacityStack<int>(n);
            Random random = new Random(DateTime.Now.Millisecond);
            for (int i = 0; i < n; ++i)
            {
                a[i] = random.Next(-MAXIMUM_INTEGER, MAXIMUM_INTEGER);
            }
            Stopwatch timer = new Stopwatch();
            for (int i = 0; i < n; ++i)
            {
                stack.Push(a[i]);
            }
            for (int i = 0; i < n; ++i)
            {
                stack.Pop();
            }
            return timer.ElapsedTimeMillionSeconds();
        }
    }
}

主函数

using System;

namespace _1._4._37
{
    /*
     * 1.4.37
     * 
     * 自动装箱的性能代价。
     * 通过实验在你的计算机上计算使用自动装箱所付出的性能代价。
     * 实现一个 FixedCapacityStackOfInts,
     * 并使用类似 DoublingRatio 的用例比较它和泛型 FixedCapacityStack 在进行大量 push() 和 pop() 时的性能。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("测试量\t非泛型耗时(毫秒)\t泛型耗时(毫秒)\t差值");
            for (int n = 250; true; n += n)
            {
                double time = DoubleTest.TimeTrial(n);
                double timeGeneric = DoubleTest.TimeTrialGeneric(n);
                Console.WriteLine($"{n}\t{time}\t{timeGeneric}\t{Math.Abs(time - timeGeneric)}");
            }
        }
    }
}

另请参阅

Measurement 库

上一题 下一题