Какой самый быстрый способ удалить один элемент из списка <T>без дубликатов, если важен порядок? - PullRequest
Новая
       31

Какой самый быстрый способ удалить один элемент из списка <T>без дубликатов, если важен порядок?

0 голосов
/ 20 апреля 2019

У меня есть список предметов без дубликатов, где порядок имеет значение.

Периодически мне нужно удалять элемент из этого списка.

Практическим примером является элемент управления пользовательского интерфейса с привязкой к списку, например DataGridView, который позволяет удалять.

Пользователь ожидаетДля просмотра элементов в определенном порядке и последующего удаления оставшиеся элементы должны сохранить свой порядок.

Вот пример кода, который, по-видимому, указывает на удаление элементов списка O(n), поскольку

(1) список должен быть повторен, чтобы найти элемент для удаления по соответствующим критериям

(2) метод List.RemoveAt должен перемешать оставшиеся элементы 

public class Item
{
  public string Name {get; set;}
  public string Description {get; set;}
}

public List<Item> Items = new List<Item>();

public void AddItem(string name, string description)
{
  Items.Add(new Item {Name=name, Description=description});
}

public void RemoveItem(string name)
{
  for (int i=0; i<Items.Count; i++)
  {
    if (Items[i].Name == name)
    {
      Items.RemoveAt(i);
      break;
    }
  }
}

Может быть быстреепуть ?

LinkedList<T> не будет работать, потому что его нельзя проиндексировать для прокрутки и нумерации страниц.Также для большого количества элементов LinkedList<T> удаление элементов происходит на самом деле медленнее из-за пропусков в кеше.

Ответы [ 3 ]

4 голосов
/ 20 апреля 2019

RemoveAt занимает O (n) время. Потому что он должен сдвигать элементы влево, начиная с индекса i до n (Items.Count). Аналогично для IndexOf.

Асимптотическая оценка вашего кода: 

public void RemoveItem(string name)
{
  foreach (var item in Items) //n times
  {
    if (item.Name == name)
    {
      Items.RemoveAt(Items.IndexOf(position)); // O(n) + O(n) => O(n)
    }
  }

  // => O(n * n)
}

работает за O (n ^ 2) раз.

Как насчет этого кода? 

for (int i = Items.Count - 1; i >= 0; i--) // n times
{
    if (Items[i].Name == name)
    {
        Items.RemoveAt(i); //O(n)
    }
}

Так что это также работает в O (n ^ 2)

но этот код: 

Items.RemoveAll(i => item.Name == name);

работает за O (n) время. Вы должны увидеть реализацию этого метода для доказательства. RemoveAll выполняет итерацию ОДИН РАЗ через элементы списка, и, если критерии соблюдены, она также начнет смещаться во время итерации. Это смещение на каждом шаге является одним назначением, т. Е. O (1). Поэтому весь метод выполняется за время O (n), что намного быстрее, чем ваша реализация.

UPDATE : Теперь вопрос содержит break; после строки удаления.

В этом коде поиск элементов будет остановлен после обнаружения, и начнется удаление, что будет стоить O (n) + O (n) => O (n).

Так что не будет никакой асимптотической разницы между рассматриваемым кодом и RemoveAll.

Так что это не так быстро и НЕ МОЖЕТ БЫТЬ, но все же RemoveAll более чистый код ИМХО.

3 голосов
/ 20 апреля 2019

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

for (int i = Items.Count - 1; i >= 0; i--)
{
    if (Items[i].Name == name)
    {
        Items.RemoveAt(i);
        break;
    }
}
3 голосов
/ 20 апреля 2019

Вам не нужен ни цикл, ни пользовательский метод. Попробуйте это: 

Items.RemoveAll(i => item.Name == name);

Редактировать
Как заметил @Gian Paolo, для List структуры данных в лучшем случае она имеет сложность O (n). Если вы хотите повысить производительность, вы можете проверить другие структуры данных, включая LinkedList, Dictionary или HashSet.

.
...