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

Question

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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