Всегда отсортированный список

В этом списке каждый вновь вставленный элемент помещается на свое место, используя IComparer<T>. Реализация использует LinkedList<T> для повышения производительности вставки. Существуют ли какие-либо проблемы с этим объектом?

public class SortedCollection<T> : ICollection<T>
{
    private readonly LinkedList<T> _sortedList;
    private readonly IComparer<T> _comparer;

    public SortedCollection(IComparer<T> comparer)
    {
       if (comparer == null) throw new ArgumentNullException("comparer");

       _comparer = comparer;
       _sortedList = new LinkedList<T>();
    }

    public SortedCollection()
       : this(Comparer<T>.Default)
    { }

    public void Add(T item)
    {
       LinkedListNode<T> node = _sortedList.First;
       if (node == null || _comparer.Compare(node.Value, item) > 0)
       {
          _sortedList.AddFirst(item);
       }
       else
       {
          while (node != null && _comparer.Compare(node.Value, item) < 1)
          {
             node = node.Next;
          }

          if (node == null)
          {
             _sortedList.AddLast(item);
          }
          else
          {
             _sortedList.AddBefore(node, item);
          }
       }
    }

    public bool Remove(T item)
    {
       return _sortedList.Remove(item);
    }

    public IEnumerator<T> GetEnumerator()
    {
       return _sortedList.GetEnumerator();
    }

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

    public void Clear()
    {
       _sortedList.Clear();
    }

    public bool Contains(T item)
    {
       return _sortedList.Contains(item);
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
       _sortedList.CopyTo(array, arrayIndex);
    }

    public int Count
    {
       get { return _sortedList.Count; }
    }

    public bool IsReadOnly { get { return false; } }
}
11 голосов | спросил IEatBagels 25 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 25 Sep 2014 22:35:54 +0400 2014, 22:35:54

2 ответа


12

Хотя сама вставка эффективна, поиск правильного индекса не выполняется с этой реализацией. Вы по-прежнему выполняете линейный поиск. Для вставки сортированное дерево более эффективно, и это тоже можно повторить в порядке сортировки. Я не знаю, почему вы выбрали список в первую очередь, но, как правило, причиной этого является доступ к элементам по индексу. Это невозможно эффективно с деревом, но со связанным списком это тоже не так.

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

ответил Simon Fischer 25 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 25 Sep 2014 23:29:14 +0400 2014, 23:29:14
4

Вы можете упростить метод Add, отбросив первый if, то есть:

public void Add(T item)
{
    LinkedListNode<T> node = _sortedList.First;
    while (node != null && _comparer.Compare(node.Value, item) < 1)
    {
        node = node.Next;
    }
    if (node == null)
    {
        _sortedList.AddLast(item);
    }
    else
    {
        _sortedList.AddBefore(node, item);
    }
}
ответил janos 26 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowFri, 26 Sep 2014 00:22:09 +0400 2014, 00:22:09

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132