Я читали blog post на MSDN о итераторах, который говорит о том, о том, как Concat имеет O(m^2) производительности, где m является длиной первого IEnumerable. Один из комментариев, на основе richard_deeming на второй странице, содержит пример кода, который, по его словам, намного быстрее. Я не совсем понимаю, почему это происходит быстрее, и надеялся, что кто-то сможет мне это объяснить.Concat производительность
Спасибо.
Он просто говорит, что вместо того, чтобы использовать Concat создать итератор, который на самом деле эквивалентно созданию итератор:
...(((a+b)+c)+d)...
, которое вызвано:
for (int i = 0; i < length; ++i)
ones = ones.Concat(list);
создать список итераторы вам нужно и вернуть каждый из тех итераторов, которые вы создали ранее.
Таким образом, вы не получите много сложенных итераторов в первом наборе элементов.
Также стоит упомянуть, что иск о O(m^2) не «действительно прав». Это правда в этом конкретном случае, но это похоже на то, что + - это O(m^2), когда вы рассчитываете (((a+b)+c)+d)... кейс. Это конкретный шаблон использования, который делает его O(m^2).
Я не думаю, что в блоге говорится, что Concat is O (m^2), по крайней мере, это не должно быть - в какой-то момент упоминается факт, что Concat O (m + n) и это гораздо более убедительно. Это использование Concat в цикле, как указано на этом посту, это O (m^2), и я не думаю, что это особенно шокирующее открытие, так как вы ожидаете, что многие вызовы будут умножать сложность!
Выполнение Ричардом предполагает отложить операции Конкат до тех пор, пока они не понадобятся, путем хранения списка итераторов, а затем перемещение каждого из них, начиная с первого, затем, когда это исчерпано, переходя к следующему, который имеет прекрасный смысл - однако для «использования света» Concat as-is будет хорошо.