Скорость списков С#

Бывают ли списки С#? Каковы хорошие и плохие стороны использования списков для обработки объектов?

Широкое использование списков сделает программное обеспечение более медленным? Каковы альтернативы спискам в С#?

Сколько объектов "слишком много объектов" для списков?

Ответы

Ответ 1

List<T> используется массив поддержки для хранения элементов:

  • Доступ индексатора (например, выборка/обновление) - это O (1)
  • Удалить из хвоста O (1)
  • Удаление из другого места требует, чтобы существующие элементы были сдвинуты вверх, поэтому O (n) эффективно
  • Добавить в конец - O (1), если это не требует изменения размера, и в этом случае это O (n). (Это удваивает размер буфера, поэтому амортизированная стоимость равна O (1).)
  • Добавить в другое место требует, чтобы существующие элементы были сдвинуты вниз, поэтому O (n) эффективно
  • Поиск элемента - это O (n), если он не отсортирован, и в этом случае двоичный поиск дает O (log n)

В целом хорошо использовать списки достаточно широко. Если вы знаете конечный размер, когда вы начинаете заполнять список, рекомендуется использовать конструктор, который позволяет указать емкость, чтобы избежать изменения размера. Помимо этого: если вы заинтересованы, выйдите из профилировщика...

Ответ 2

По сравнению с чем?

  • Если вы имеете в виду List<T>, то это по существу обертка вокруг массива; настолько быстрый, чтобы читать/писать по индексу, относительно быстро добавлять (поскольку он позволяет дополнительное пространство в конце, при необходимости удваивать размер) и удалять с конца, но более дорогостоящие для выполнения других операций (вставить/удалить, кроме конца )
  • Массив снова быстрый по индексу, но фиксированный размер (без добавления/удаления)
  • Dictionary<,> и т.д. предлагают лучший доступ по ключу.

Список не слишком медленный; особенно если вы знаете, что вам всегда нужно смотреть на все данные или получить доступ к нему по индексу. Но для больших списков может быть лучше (и удобнее) искать через ключ. В .NET существуют различные реализации словарей, каждый из которых имеет разные размеры и производительность.