Сравнивая DoublyLinkedList исполнения с другими ОУЗ (.Нетто) классов


Я реализовал универсальный двунаправленный список класса, который поддерживает интерфейс IEnumerable,IEnumerator перечислитель интерфейсы.

DoublyLinkedList полностью совместим с классами стандарт ОУЗ.

Цели:

  • класс может использоваться как стандартная замена для стека, Очереди и список.
  • сам класс является неизменяемым, поэтому вы можете не менять, содержащий значение элемента.
  • методы класса вызывает исключение, которое отвечает за общие соображения.
  • класс метода блокировки оператора использовался для запирания текущий активный элемент.
  • класс, пуш, поп, украдкой операций нарушает текущее состояние перечисленных объектов.

Как мы можем сравнить производительность для этого класса по сравнению с классов BCL и другие реализации?

Вы будете предоставлять в C# код, чтобы сравнить с ОУЗ классов, как стек, Йцукен, Список?

Модульные тесты (покрытие кода - 100%):

[TestClass]
public class DoublyLinkedListUnitTest
{
    [TestMethod]
    public void TestValueMethod()
    {
        DoublyLinkedList<int> dll = new DoublyLinkedList<int>();

        int i1 = 1;
        int i2 = 2;
        int i3 = 3;

        Assert.AreEqual(((IDoublyLinkedList<int>)dll).Index, -1);
        try
        {
            dll.Peek();
        }
        catch (Exception ex)
        {
            Assert.AreEqual(typeof(InvalidOperationException), ex.GetType());
        }

        using (IEnumerator<int> dllEnumerator = dll.GetEnumerator())
        {
            Assert.AreEqual(dll.MoveLast(), false);
            Assert.AreEqual(dll.MovePrevious(), false);
            Assert.AreEqual(dllEnumerator.MoveNext(), false);
            Assert.AreEqual(dllEnumerator.Current, default(int));
            Assert.AreEqual(dll.Count, 0);
            Assert.AreEqual(dll.CurrentIndex, -1);

            try
            {
                dll.Pop();
            }
            catch (Exception ex)
            {
                Assert.AreEqual(typeof(InvalidOperationException), ex.GetType());
            }

            dll.Add(i1);
            dll.MovePrevious();
            try
            {
                dll.Remove();
            }
            catch (Exception ex)
            {
                Assert.AreEqual(typeof(InvalidOperationException), ex.GetType());
            }
            dll.MoveLast();
            Assert.AreEqual(dllEnumerator.MoveNext(), true);
            Assert.AreEqual(dllEnumerator.Current, i1);
            Assert.AreEqual(dll.Count, 1);
            Assert.AreEqual(dll.CurrentIndex, 0);

            dll.Add(i2);
            Assert.AreEqual(dllEnumerator.MoveNext(), true);
            Assert.AreEqual(dllEnumerator.Current, i2);
            Assert.AreEqual(dll.Count, 2);
            Assert.AreEqual(dll.CurrentIndex, 1);

            dll.MoveFirst();
            try
            {
                dll.Remove();
            }
            catch (Exception ex)
            {
                Assert.AreEqual(typeof(InvalidOperationException), ex.GetType());
            }
            try
            {
                dll.Add(i1);
            }
            catch (Exception ex)
            {
                Assert.AreEqual(typeof(InvalidOperationException), ex.GetType());
            }
            dll.MoveLast();

            dll.Add(i3);
            Assert.AreEqual(dllEnumerator.MoveNext(), true);
            Assert.AreEqual(dllEnumerator.Current, i3);
            Assert.AreEqual(dll.Count, 3);
            Assert.AreEqual(dll.CurrentIndex, 2);
        }

        IEnumerator o = ((IEnumerable)dll).GetEnumerator();
        o.MoveNext();
        Assert.AreEqual(o.Current, i1);

        List<int> list = new List<int>();
        dll.CopyTo(list);
        Assert.AreEqual(dll.ToList().Except(list).Count(), 0);
        Assert.AreEqual(list.Except(dll).Count(), 0);

        Assert.AreEqual(list.Count, 3);
        Assert.AreEqual(list[0], i1);
        Assert.AreEqual(list[1], i2);
        Assert.AreEqual(list[2], i3);

        using (IEnumerator<int> dllEnumerator = dll.GetEnumerator())
        {
            if (dll.Count > 0)
            {
                dll.Remove();
            }

            Assert.AreEqual(dllEnumerator.MoveNext(), true);
            Assert.AreEqual(dllEnumerator.Current, i1);

            if (dll.Count > 0)
            {
                dll.Remove();
            }
            Assert.AreEqual(dllEnumerator.MoveNext(), false);

            if (dll.Count > 0)
            {
                dll.Remove();
            }
        }

        try
        {
            dll.Remove();
        }
        catch (Exception ex)
        {
            Assert.AreEqual(typeof(InvalidOperationException), ex.GetType());
        }

        dll.AddRange(list);
        try
        {
            dll.AddRange(null);
        }
        catch (Exception ex)
        {
            Assert.AreEqual(typeof(ArgumentNullException), ex.GetType());
        }
        try
        {
            dll.MoveFirst();
            dll.AddRange(list);
        }
        catch (Exception ex)
        {
            Assert.AreEqual(typeof(InvalidOperationException), ex.GetType());
        }

        Assert.AreEqual(dll.Contains(i1), true);
        Assert.AreEqual(dll.Contains(i2), true);
        Assert.AreEqual(dll.Contains(i3), true);
        Assert.AreEqual(dll.Contains(default(int)), false);

        using (IEnumerator<int> dllEnumerator = dll.GetEnumerator())
        {
            Assert.AreEqual(dllEnumerator.MoveNext(), true);
            Assert.AreEqual(dllEnumerator.Current, i1);

            Assert.AreEqual(dllEnumerator.MoveNext(), true);
            Assert.AreEqual(dllEnumerator.Current, i2);

            Assert.AreEqual(dllEnumerator.MoveNext(), true);
            Assert.AreEqual(dllEnumerator.Current, i3);
        }

        Stack<int> stack = new Stack<int>();
        stack.Push(i3);
        stack.Push(i2);
        stack.Push(i1);
        foreach (object value in dll)
        {
            Assert.AreEqual(stack.Pop(), value);
        }

        try
        {
            int value = default(int);
            while ((value = dll.Pop()) != default(int))
            {
                stack.Push(value);
            }
        }
        catch (Exception ex)
        {
            Assert.AreEqual(typeof(InvalidOperationException), ex.GetType());
        }

        dll.Push(i1);
        dll.Push(i2);
        dll.Push(i3);
        dll.Clear();
        Assert.AreEqual(dll.MoveFirst(), false);

        stack.Clear();
        stack.Push(i3);
        stack.Push(i2);
        stack.Push(i1);
        foreach (int value in stack)
        {
            dll.Push(value);
            Assert.AreEqual(dll.Peek(), value);
        }

        IDoublyLinkedList<int> dllInterface = dll;
        dllInterface.Reset();

        Assert.AreEqual(dllInterface.MovePrevious(), false);
        Assert.AreEqual(dllInterface.Current, default(int));
        Assert.AreEqual(dllInterface.CurrentIndex, -1);

        Assert.AreEqual(dllInterface.MoveNext(), true);
        Assert.AreEqual(dllInterface.Current, i1);
        Assert.AreEqual(dllInterface.CurrentIndex, 0);

        Assert.AreEqual(dllInterface.MoveNext(), true);
        Assert.AreEqual(dllInterface.Current, i2);
        Assert.AreEqual(dllInterface.CurrentIndex, 1);

        Assert.AreEqual(dllInterface.MoveNext(), true);
        Assert.AreEqual(dllInterface.Current, i3);
        Assert.AreEqual(dllInterface.CurrentIndex, 2);

        Assert.AreEqual(dllInterface.MoveFirst(), true);
        Assert.AreEqual(dllInterface.Current, i1);
        Assert.AreEqual(dllInterface.CurrentIndex, 0);

        Assert.AreEqual(dllInterface.MoveLast(), true);
        Assert.AreEqual(dllInterface.Current, i3);
        Assert.AreEqual(dllInterface.CurrentIndex, 2);

        Assert.AreEqual(dllInterface.MovePrevious(), true);
        Assert.AreEqual(dllInterface.Current, i2);
        Assert.AreEqual(dllInterface.CurrentIndex, 1);

        Assert.AreEqual(dllInterface.MovePrevious(), true);
        Assert.AreEqual(dllInterface.Current, i1);
        Assert.AreEqual(dllInterface.CurrentIndex, 0);

        Assert.AreEqual(dllInterface.MovePrevious(), true);
        Assert.AreEqual(dllInterface.Current, default(int));
        Assert.AreEqual(dllInterface.CurrentIndex, -1);
    }

    [TestMethod]
    public void TestReferenceMethod()
    {
        DoublyLinkedList<object> dll = new DoublyLinkedList<object>();

        object o1 = new object();
        object o2 = new object();
        object o3 = new object();

        Assert.AreEqual(((IDoublyLinkedList<object>)dll).Index, -1);
        try
        {
            dll.Peek();
        }
        catch (Exception ex)
        {
            Assert.AreEqual(typeof(InvalidOperationException), ex.GetType());
        }

        using (IEnumerator<object> dllEnumerator = dll.GetEnumerator())
        {
            Assert.AreEqual(dll.MoveLast(), false);
            Assert.AreEqual(dll.MovePrevious(), false);
            Assert.AreEqual(dllEnumerator.MoveNext(), false);
            Assert.AreEqual(dllEnumerator.Current, default(object));
            Assert.AreEqual(dll.Count, 0);
            Assert.AreEqual(dll.CurrentIndex, -1);

            try
            {
                dll.Pop();
            }
            catch (Exception ex)
            {
                Assert.AreEqual(typeof(InvalidOperationException), ex.GetType());
            }

            dll.Add(o1);
            dll.MovePrevious();
            try
            {
                dll.Remove();
            }
            catch (Exception ex)
            {
                Assert.AreEqual(typeof(InvalidOperationException), ex.GetType());
            }
            dll.MoveLast();
            Assert.AreEqual(dllEnumerator.MoveNext(), true);
            Assert.AreEqual(dllEnumerator.Current, o1);
            Assert.AreEqual(dll.Count, 1);
            Assert.AreEqual(dll.CurrentIndex, 0);

            dll.Add(o2);
            Assert.AreEqual(dllEnumerator.MoveNext(), true);
            Assert.AreEqual(dllEnumerator.Current, o2);
            Assert.AreEqual(dll.Count, 2);
            Assert.AreEqual(dll.CurrentIndex, 1);

            dll.MoveFirst();
            try
            {
                dll.Add(o1);
            }
            catch (Exception ex)
            {
                Assert.AreEqual(typeof(InvalidOperationException), ex.GetType());
            }
            dll.MoveLast();

            dll.Add(o3);
            Assert.AreEqual(dllEnumerator.MoveNext(), true);
            Assert.AreEqual(dllEnumerator.Current, o3);
            Assert.AreEqual(dll.Count, 3);
            Assert.AreEqual(dll.CurrentIndex, 2);
        }

        IEnumerator o = ((IEnumerable)dll).GetEnumerator();
        o.MoveNext();
        Assert.AreEqual(o.Current, o1);

        List<object> list = new List<object>();
        dll.CopyTo(list);
        Assert.AreEqual(dll.ToList().Except(list).Count(), 0);
        Assert.AreEqual(list.Except(dll).Count(), 0);

        Assert.AreEqual(list.Count, 3);
        Assert.AreEqual(list[0], o1);
        Assert.AreEqual(list[1], o2);
        Assert.AreEqual(list[2], o3);

        using (IEnumerator<object> dllEnumerator = dll.GetEnumerator())
        {
            if (dll.Count > 0)
            {
                dll.Remove();
            }

            Assert.AreEqual(dllEnumerator.MoveNext(), true);
            Assert.AreEqual(dllEnumerator.Current, o1);

            if (dll.Count > 0)
            {
                dll.Remove();
            }
            Assert.AreEqual(dllEnumerator.MoveNext(), false);

            if (dll.Count > 0)
            {
                dll.Remove();
            }
        }

        try
        {
            dll.Remove();
        }
        catch (Exception ex)
        {
            Assert.AreEqual(typeof(InvalidOperationException), ex.GetType());
        }

        dll.AddRange(list);
        try
        {
            dll.AddRange(null);
        }
        catch (Exception ex)
        {
            Assert.AreEqual(typeof(ArgumentNullException), ex.GetType());
        }
        try
        {
            dll.MoveFirst();
            dll.AddRange(list);
        }
        catch (Exception ex)
        {
            Assert.AreEqual(typeof(InvalidOperationException), ex.GetType());
        }

        Assert.AreEqual(dll.Contains(o1), true);
        Assert.AreEqual(dll.Contains(o2), true);
        Assert.AreEqual(dll.Contains(o3), true);
        Assert.AreEqual(dll.Contains(default(object)), false);

        using (IEnumerator<object> dllEnumerator = dll.GetEnumerator())
        {
            Assert.AreEqual(dllEnumerator.MoveNext(), true);
            Assert.AreEqual(dllEnumerator.Current, o1);

            Assert.AreEqual(dllEnumerator.MoveNext(), true);
            Assert.AreEqual(dllEnumerator.Current, o2);

            Assert.AreEqual(dllEnumerator.MoveNext(), true);
            Assert.AreEqual(dllEnumerator.Current, o3);
        }

        Stack<object> stack = new Stack<object>();
        stack.Push(o3);
        stack.Push(o2);
        stack.Push(o1);
        foreach (object value in dll)
        {
            Assert.AreEqual(stack.Pop(), value);
        }

        try
        {
            object value = default(object);
            while ((value = dll.Pop()) != default(object))
            {
                stack.Push(value);
            }
        }
        catch (Exception ex)
        {
            Assert.AreEqual(typeof(InvalidOperationException), ex.GetType());
        }

        dll.Push(o1);
        dll.Push(o2);
        dll.Push(o3);
        dll.Clear();
        Assert.AreEqual(dll.MoveFirst(), false);

        stack.Clear();
        stack.Push(o3);
        stack.Push(o2);
        stack.Push(o1);
        foreach (object value in stack)
        {
            dll.Push(value);
            Assert.AreEqual(dll.Peek(), value);
        }

        IDoublyLinkedList<object> dllInterface = dll;
        dllInterface.Reset();

        Assert.AreEqual(dllInterface.MovePrevious(), false);
        Assert.AreEqual(dllInterface.Current, default(object));
        Assert.AreEqual(dllInterface.CurrentIndex, -1);

        Assert.AreEqual(dllInterface.MoveNext(), true);
        Assert.AreEqual(dllInterface.Current, o1);
        Assert.AreEqual(dllInterface.CurrentIndex, 0);

        Assert.AreEqual(dllInterface.MoveNext(), true);
        Assert.AreEqual(dllInterface.Current, o2);
        Assert.AreEqual(dllInterface.CurrentIndex, 1);

        Assert.AreEqual(dllInterface.MoveNext(), true);
        Assert.AreEqual(dllInterface.Current, o3);
        Assert.AreEqual(dllInterface.CurrentIndex, 2);

        Assert.AreEqual(dllInterface.MoveFirst(), true);
        Assert.AreEqual(dllInterface.Current, o1);
        Assert.AreEqual(dllInterface.CurrentIndex, 0);

        Assert.AreEqual(dllInterface.MoveLast(), true);
        Assert.AreEqual(dllInterface.Current, o3);
        Assert.AreEqual(dllInterface.CurrentIndex, 2);

        Assert.AreEqual(dllInterface.MovePrevious(), true);
        Assert.AreEqual(dllInterface.Current, o2);
        Assert.AreEqual(dllInterface.CurrentIndex, 1);

        Assert.AreEqual(dllInterface.MovePrevious(), true);
        Assert.AreEqual(dllInterface.Current, o1);
        Assert.AreEqual(dllInterface.CurrentIndex, 0);

        Assert.AreEqual(dllInterface.MovePrevious(), true);
        Assert.AreEqual(dllInterface.Current, default(object));
        Assert.AreEqual(dllInterface.CurrentIndex, -1);            
    }
}

Исходный код:

public interface IDoublyLinkedList<T> : IEnumerator<T>, IEnumerable<T>, IEnumerator, IEnumerable, IDisposable
{
    void Add(T value);
    void AddRange(IEnumerable<T> values);
    bool Contains(T item);
    void Remove();
    bool MoveFirst();
    bool MovePrevious();
    bool MoveLast();
    void CopyTo(List<T> list);
    List<T> ToList();
    void Clear();
    T Pop();
    T Peek();
    void Push(T value);
    int Count { get; }
    int Index { get; }
    int CurrentIndex { get; }
}

public class DoublyLinkedList<T> : IDoublyLinkedList<T>
{
    private DoublyLinkedList<T> _current;
    private DoublyLinkedList<T> _previous;
    private DoublyLinkedList<T> _first;
    private DoublyLinkedList<T> _last;
    private readonly T _value;
    private readonly int _count;

    public DoublyLinkedList()
    {
        _current = this;
    }
    private DoublyLinkedList(DoublyLinkedList<T> copy)
    {
        _current = copy;
        _previous = copy._previous;
        _first = copy._first;
        _last = copy._last;
        _count = copy._count;
    }
    public int Count
    {
        get
        {
            lock (_current)
            {
                if (_last != null)
                {
                    return _last._count;
                }
                return 0;
            }
        }
    }
    public int Index
    {
        get
        {
            lock (_current)
            {
                return _count - 1;
            }
        }
    }
    public int CurrentIndex
    {
        get
        {
            lock (_current)
            {
                return _current._count - 1;
            }
        }
    }
    private DoublyLinkedList(DoublyLinkedList<T> previous, T value)
    {
        _current = this;
        _previous = previous;
        _value = value;
        _count = previous._count + 1;
    }
    public void Clear()
    {
        _current = this;
        _previous = null;
        _first = null;
        _last = null;
    }
    public bool Contains(T item)
    {
        lock (_current)
        {
            foreach (T value in this)
            {
                if (object.Equals(value, item))
                    return true;
            }
            return false;
        }
    }
    public void CopyTo(List<T> list)
    {
        lock (_current)
        {
            list.AddRange(this);
        }
    }
    public List<T> ToList()
    {
        lock (_current)
        {
            return new List<T>(this);
        }
    }
    public void AddRange(IEnumerable<T> values)
    {
        lock (_current)
        {
            if (values != null)
            {
                if (_current._first == null)
                {
                    foreach (T value in values)
                    {
                        _current._first = new DoublyLinkedList<T>(_current, value);
                        _current = _current._first;
                    }
                    _last = _current;
                    return;
                }
                throw new InvalidOperationException();
            }
            throw new ArgumentNullException();
        }
    }
    public void Add(T value)
    {
        lock (_current)
        {
            if (_current._first == null)
            {
                _current._first = new DoublyLinkedList<T>(_current, value);
                _last = _current = _current._first;
                return;
            }
            throw new InvalidOperationException();
        }
    }
    public void Remove()
    {
        lock (_current)
        {
            if (_current._first == null)
            {
                if (_current._previous != null)
                {
                    _last = _current = _current._previous;
                    _current._first = null;
                    return;
                }
                throw new InvalidOperationException();
            }
            throw new InvalidOperationException();
        }
    }
    public T Pop()
    {
        lock (_current)
        {
            if (_last != null)
            {
                _current = _last;
            }
            if (_current._previous != null)
            {
                T value = _current._value;
                _last = _current = _current._previous;
                _current._first = null;
                return value;
            }
            throw new InvalidOperationException();
        }
    }
    public T Peek()
    {
        lock (_current)
        {
            if (_last != null)
            {
                _current = _last;
            }
            if (_current._previous != null)
            {
                T value = _current._value;
                return value;
            }
            throw new InvalidOperationException();
        }
    }
    public void Push(T value)
    {
        lock (_current)
        {
            if (_last != null)
            {
                _current = _last;
            }
            _current._first = new DoublyLinkedList<T>(_current, value);
            _last = _current = _current._first;
        }
    }
    public bool MoveFirst()
    {
        lock (_current)
        {
            if (_first != null)
            {
                _current = _first;
                return true;
            }
            return false;
        }
    }
    public bool MoveLast()
    {
        lock (_current)
        {
            if (_last != null)
            {
                _current = _last;
                return true;
            }
            return false;
        }
    }
    public bool MovePrevious()
    {
        lock (_current)
        {
            if (_current._previous != null)
            {
                _current = _current._previous;
                return true;
            }
            return false;
        }
    }
    T IEnumerator<T>.Current
    {
        get
        {
            lock (_current)
            {
                return _current._value;
            }
        }
    }
    public IEnumerator<T> GetEnumerator()
    {
        lock (_current)
        {
            return new DoublyLinkedList<T>(this);
        }
    }
    bool IEnumerator.MoveNext()
    {
        lock (_current)
        {
            if (_current._first != null)
            {
                _current = _current._first;
                return true;
            }
            return false;
        }
    }
    object IEnumerator.Current
    {
        get
        {
            lock (_current)
            {
                return _current._value;
            }
        }
    }
    void IEnumerator.Reset()
    {
        lock (_current)
        {
            _current = this;
        }
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        lock (_current)
        {
            return new DoublyLinkedList<T>(this);
        }
    }
    void IDisposable.Dispose()
    {
    }
}


544
6
задан 19 сентября 2011 в 06:09 Источник Поделиться
Комментарии
1 ответ

Более подробные модульные тесты как на мой комментарий выше.

    [TestClass]
public sealed class DoublyLinkedListUnitTest
{
private IDoublyLinkedList<int> valueDll;

[TestInitialize]
public void TestEmptyValueDllInitialize()
{
this.valueDll = new DoublyLinkedList<int>();
}

[TestMethod]
public void TestEmptyValueDllIndex()
{
Assert.AreEqual(-1, this.valueDll.Index);
}

[TestMethod]
[ExpectedException(typeof(InvalidOperationException))]
public void TestEmptyValueDllPeek()
{
var intValue = this.valueDll.Peek();
}

[TestMethod]
public void TestEmptyValueDllMoveLast()
{
Assert.AreEqual(false, this.valueDll.MoveLast());
}

[TestMethod]
public void TestEmptyValueDllMovePrevious()
{
Assert.AreEqual(false, this.valueDll.MovePrevious());
}

[TestMethod]
public void TestEmptyValueDllEnumeratorMoveNext()
{
using (var dllEnumerator = this.valueDll.GetEnumerator())
{
Assert.AreEqual(false, dllEnumerator.MoveNext());
}
}

[TestMethod]
public void TestEmptyValueDllEnumeratorCurrent()
{
using (var dllEnumerator = this.valueDll.GetEnumerator())
{
Assert.AreEqual(default(int), dllEnumerator.Current);
}
}

[TestMethod]
public void TestEmptyValueDllCount()
{
Assert.AreEqual(0, this.valueDll.Count);
}

[TestMethod]
public void TestEmptyValueDllCurrentIndex()
{
Assert.AreEqual(-1, this.valueDll.CurrentIndex);
}

[TestMethod]
[ExpectedException(typeof(InvalidOperationException))]
public void TestEmptyValueDllPop()
{
var intValue = this.valueDll.Pop();
}

[TestMethod]
public void TestEmptyValueDllAdd()
{
const int I1 = 1;

this.valueDll.Add(I1);
this.TestEmptyValueDllIndex();
Assert.AreEqual(1, this.valueDll.Count);
Assert.AreEqual(0, this.valueDll.CurrentIndex);

var i1 = this.valueDll.Peek(); // Technically not a "unit" test since we are relying on Peek() to work too.

Assert.AreEqual(I1, i1);
}

//// Add more unit tests here.
}
}

3
ответ дан 14 ноября 2011 в 08:11 Источник Поделиться