7
La mise en œuvre est-elle en HashSet.ElementAt O (1) et si non, qu'est-ce que c'est?Est-ce que Enumerable.ElementAt <TSource> O (1) pour HashSet?
A
Répondre
4
Non, c'est O (n). Toutes les méthodes d'extension sur IEnumerable<T> sont, par nécessité O (n) (parce que la seule chose que IEnumerable<T> peut faire est ... énumérer). Bien que, comme indiqué dans les commentaires, ils tentent de lancer à une interface qui peut implémenter l'opération plus rapidement (par exemple, ElementAt va essayer de lancer à IList<T> afin d'implémenter une opération O (1)). Non que cela aide dans le cas de HashSet<T> qui n'implémente pas IList<T> de toute façon.
Pour HashSet<T> le concept de "ElementAt" n'a pas vraiment de sens de toute façon, car il n'y a pas de "ordering" en tant que tel. Vous obtenez simplement un élément aléatoire.
2
Il n'y a pas de méthode ElementAt dans HashSet si vous voulez probablement connaître les performances de la méthode Enumerable.ElementAt lorsqu'il est utilisé sur une instance de HashSet<T>.
La méthode Enumerable.ElementAt a une optimisation pour les types implémentant IList<T>. Dans ce cas, la performance est O (1). Cependant, HashSet n'implémente pas cette interface, donc la performance est O (n).
+0
@Steven, il y a un ElementAt parce que HashSet dérive d'ICollection. –
+0
@Filip: 'HashSet
+0
@Steven, j'utilise .NET 4.0 et ReSharper me suggère d'utiliser 'ICollection
2
Cela dépend du type de liste sous-jacente. Le réflecteur montre que Enumerable<T>.ElementAt(...) essaie d'effectuer un cast vers un IList<T> en premier. Dans ce cas, ce serait O (1).
Un fournisseur de requête peut, par exemple, renvoyer un élément IList<T>. Mais il y a des chances que si vous appliquez l'un des opérateurs Linq, il deviendra un IEnumerable<T>, car ils sont construits simplement en utilisant différents énumérateurs, et il deviendra O (n).
EDIT: J'ai dépassé le HashSet. Un HashSet<T> n'implémente pas IList<T>, donc c'est O (n).
Ensuite, une chose plus intelligente serait de faire un 'ToArray' si vous avez besoin d'utiliser ElementAt sur beaucoup de lignes? Est-il jamais possible d'obtenir la commande "correcte" avec un HasSet? –
Oui, un seul 'ToArray' puis plusieurs" element at "(via l'opérateur' [] ') seraient beaucoup plus rapides. Il n'y a pas d'ordre "correct" avec un HashSet, puisque les éléments ne sont pas ordonnés de manière significative. –
À droite, cependant, quand je fais ceci: {2, 3, 4} et que je lance deux HashSets avec ceux-ci, j'obtiens l'ordre correct en passant par chaque élément. –