Характеристики производительности ImmutableList<T>
Это где-то задокументированы характеристики производительности ImmutableList<T>? Меня интересует асимптотическая сложность (big-O). Ссылка MSDN не раскрывает много.
я знаю Add а также this[] оба O(log n) из этой статьи, но я хочу знать также о Remove а также Insert,
Я также хотел бы видеть, если это возможно, сложности всех типов во вновь введенном System.Collections.Immutable Пространство имен.
1 ответ
Ну, исходя из некоторого изучения кода, я бы ожидал RemoveAt (Remove должен найти предмет первым) и Insert быть почти таким же, как Add, Основной принцип тот же. Больше всего меня бы волновал шаблон использования памяти и тому подобное - если вы используете несколько ImmutableListБудучи рядом друг с другом и делая много добавлений и удалений, я ожидаю, что вы можете быстро столкнуться с проблемами локальности данных, которые приведут к снижению вашей производительности. AddRange в основном это ярлык, он на самом деле вызывает только кучу Node.Addв любом случае, экономя некоторые накладные расходы, но не очень. Там также много рекурсии.
ImmutableArray не будет вызывать это, потому что он всегда создает новый массив и копирует старый массив. Таким образом, это приведет к большому количеству копирования и распределения / выделения памяти, но также будет более стабильным с точки зрения производительности - время доступа не меняется в зависимости от использования, и даже нет никаких ярлыков при изменении массива, у вас всегда есть скопировать все предметы. Это также означает, что добавление нескольких элементов просто должно быть сделано с AddRange - разница в производительности будет огромной. Add внутренне реализовано с использованием Insertтак что сейчас то же самое. Другими словами, все операции изменения - o/O(n), в то время как read - o/O(1).
В общем, ImmutableList больше обеспокоен частыми изменениями и жертвует производительностью чтения, в то время как ImmutableArray в основном полезно для большого количества чтений и относительно небольшого количества изменений.