1.4.37 #

/// <summary>
/// 固定大小的整型数据栈。
/// </summary>
internal class FixedCapacityStackOfInts : IEnumerable<int>
{
    private readonly int[] _a;
    private int _n;

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

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

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

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

    /// <summary>
    /// 从栈中弹出一个元素，返回被弹出的元素。
    /// </summary>
    /// <returns></returns>
    public int Pop()
    {
        _n--;
        return _a[_n];
    }

    /// <summary>
    /// 返回栈顶元素（但不弹出它）。
    /// </summary>
    /// <returns></returns>
    public int Peek()
    {
        return _a[_n - 1];
    }

    public IEnumerator<int> GetEnumerator()
    {
        return new ReverseEnmerator(_a);
    }

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

    private class ReverseEnmerator : IEnumerator<int>
    {
        private int _current;
        private int[] _a;

        public ReverseEnmerator(int[] a)
        {
            _current = a.Length;
            _a = a;
        }

        int IEnumerator<int>.Current => _a[_current];

        object IEnumerator.Current => _a[_current];

        void IDisposable.Dispose()
        {
            _current = -1;
            _a = null;
        }

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

        void IEnumerator.Reset()
        {
            _current = _a.Length;
        }
    }
}

internal class FixedCapacityStack<TItem> : IEnumerable<TItem>
{
    private readonly TItem[] _a;
    private int _n;

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

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

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

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

    /// <summary>
    /// 从栈中弹出一个元素，返回被弹出的元素。
    /// </summary>
    /// <returns></returns>
    public TItem Pop()
    {
        _n--;
        return _a[_n];
    }

    /// <summary>
    /// 返回栈顶元素（但不弹出它）。
    /// </summary>
    /// <returns></returns>
    public TItem Peek()
    {
        return _a[_n - 1];
    }

    public IEnumerator<TItem> GetEnumerator()
    {
        return new ReverseEnmerator(_a);
    }

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

    private class ReverseEnmerator : IEnumerator<TItem>
    {
        private int _current;
        private TItem[] _a;

        public ReverseEnmerator(TItem[] a)
        {
            _current = a.Length;
            _a = a;
        }

        TItem IEnumerator<TItem>.Current => _a[_current];

        object IEnumerator.Current => _a[_current];

        void IDisposable.Dispose()
        {
            _current = -1;
            _a = null;
        }

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

        void IEnumerator.Reset()
        {
            _current = _a.Length;
        }
    }
}

public static class DoubleTest
{
    private static readonly int MaximumInteger = 1000000;

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

Console.WriteLine("测试量\t非泛型耗时（毫秒）\t泛型耗时（毫秒）\t差值");
for (var n = 250; true; n += n)
{
    var time = DoubleTest.TimeTrial(n);
    var timeGeneric = DoubleTest.TimeTrialGeneric(n);
    Console.WriteLine($"{n}\t{time}\t{timeGeneric}\t{Math.Abs(time - timeGeneric)}");
}