Linq ToList / ToArray / ToDictionary производительность

18

Ну, я встречаю много ситуаций, когда недостаточно IEnumerable. Однако я не уверен в производительности вышеупомянутых вызовов методов.

Я действительно хочу спросить:

Является ли производительность ToList / ToArray:

  1. операция O (n), которая копирует IEnumerable в новый массив / List?
  2. Если я вызвал метод расширения linq в списке, он имеет производительность O (1), если я вызываю ToList, но O (n), если вызывается ToArray (и наоборот, если мой исходный список был массивом)?

  3. Происходит какая-то магия, а производительность - O (1)?

Вероятно, для словаря есть O (n), правильно?

    
задан Jonny 23.02.2013 в 16:11
источник

1 ответ

43
  

Является ли производительность ToList / ToArray функцией O (n), которая копирует IEnumerable в новый массив / List?

Да. ToList немного более эффективно, так как не нужно сначала обрезать внутренний буфер до нужной длины.

  

Если я вызвал метод расширения linq в списке, он имеет производительность O (1), если я вызываю ToList, но O (n), если вызывается ToArray (и наоборот, если мой исходный список был массивом)?

Нет. Для обоих вызовов всегда создается коллекция new ; это мелкая копия оригинальной коллекции. Более эффективно вызывать ToList или ToArray для любого ICollection<T> , чем для простого IEnumerable<T> , который не реализует ICollection<T> , хотя, как и в случае с коллекцией, с которой, как известно, начинается. (Это обнаружено во время выполнения, хотя вам не нужно беспокоиться о типе времени компиляции.)

  

Вероятно, для словаря есть O (n), правильно?

Предполагая, что хэш чувствителен, это O (N), да. В основном он создает новый словарь точно так, как вы, вероятно, ожидаете.

Возможно, вы захотите прочитать соответствующие записи в моей блоге блога Edulinq:

ответ дан Jon Skeet 23.02.2013 в 16:19
источник
  • Я бы также добавил эту ссылку к вашему ответу: msmvps.com/blogs/jon_skeet/archive/2011/01/01/... –  MarcinJuraszek 23.02.2013 в 16:20
  • @JonSkeet: ничего себе, я не заметил, что это ваш блог-сообщение там :) Должен сказать, очень хороший! –  MarcinJuraszek 23.02.2013 в 16:23
  • @MarcinJuraszek Да, проверьте полную серию Edulinq и электронную книгу. Невероятный материал и действительно помогает понять Linq, сборник итераций и просто некоторые изящество в целом; действительно расширило мое мышление. Говоря об электронной книге, какие-либо планы Джона на повторном обновлении / редактировании опубликованной версии PDF? Я бы полностью купил полностью полированную и печатную версию. :) –  Chris Sinclair 23.02.2013 в 16:29
  • @ChrisSinclair: есть издатель, который на самом деле имеет права на него, но я до сих пор не знаю, планируют ли они их использовать ... –  Jon Skeet 23.02.2013 в 17:39
  • @JonSkeet * пересекает пальцы * Спасибо за обновление! –  Chris Sinclair 23.02.2013 в 18:08
Показать остальные комментарии