je suis en train de lire un blog post sur msdn à propos itérateurs qui parle de la façon dont Concat a O(m^2) la performance où m est la longueur de la première IEnumerable. L'un des commentaires, par richard_deeming sur la deuxième page, fournit un exemple de code qui, selon lui, est beaucoup plus rapide. Je ne comprends pas vraiment pourquoi c'est plus rapide et j'espérais que quelqu'un pourrait me l'expliquer.performances Concat
Merci.
Il dit simplement qu'au lieu d'utiliser Concat pour créer un itérateur qui est en fait équivalent à la création d'un itérateur sur:
...(((a+b)+c)+d)...
qui est causée par:
for (int i = 0; i < length; ++i)
ones = ones.Concat(list);
créer une liste de itérateurs vous avez besoin de chacun de ces itérateurs que vous avez créés précédemment. De cette façon, vous ne vous retrouverez pas avec beaucoup d'itérateurs empilés dans la première collection d'éléments.
Aussi, il est à noter que la réclamation au sujet de O(m^2) n'est pas "vraiment juste". C'est vrai dans ce cas précis, mais c'est comme dire + est O(m^2) lorsque vous calculez (((a+b)+c)+d)... cas. C'est le modèle d'utilisation spécifique qui le rend O(m^2).
Je ne pense pas que le blog dit que Concat est O (m^2), au moins, il ne devrait pas être - à un moment donné, le fait que Concat est O (m + n) est mentionné - et c'est beaucoup plus crédible. C'est l'utilisation de Concat dans une boucle donnée sur ce post qui est O (m^2) - et je ne pense pas que ce soit une découverte particulièrement choquante car vous vous attendriez à ce que de nombreux appels multiplient la complexité! Le suivi de Richard suggère de différer les opérations de concat jusqu'à ce qu'elles soient nécessaires, en stockant une liste d'itérateurs, puis de passer à travers chacune d'elles en commençant par la première, puis quand elle est épuisée, en passant à la suivante, ce qui est tout à fait logique - cependant, pour une «utilisation légère», Concat tel qu'il est serait parfait.