Is the implementation in HashSet.ElementAt O(1) and if not, what is it?
views:
92answers:
3
+3
A:
No, it's O(n). All of the extension methods on IEnumerable<T> are, by necessity O(n) (because the only thing that IEnumerable<T> can do is ... enumerate). Although, as pointed out in the comments, they do attempt to cast to an interface that can implement the operation faster (for example, ElementAt will try to cast to IList<T> in order to implement an O(1) operation). Not that that helps in the case of HashSet<T> which doesn't implement IList<T> anyway.
For HashSet<T> the concept of "ElementAt" doesn't really make sense anyway, because there is no "ordering" as such. You're basically just getting a random element.
Dean Harding
2010-07-19 07:07:53
Then a smarter thing would be to do a `ToArray` if you need to use ElementAt on a lot of rows? Is it never possible to get the "correct" order with a HasSet?
Filip Ekberg
2010-07-19 07:09:01
Yes, a single `ToArray` and then multiple "element at" (via the `[]` operator) would be much faster. There's no such thing as a "correct" order with a HashSet, since elements are not ordered in any meaningful way.
Dean Harding
2010-07-19 07:10:46
Right, however when I do this: { 2, 3, 4 } and initiate two HashSets with those, I do get the correct ordering when stepping through each element.
Filip Ekberg
2010-07-19 07:12:52
@Dean: Don't forget about the performance optimizations inside the `Enumerable` class for array and List<T> types. For these types some operations are in fact O(1).
Steven
2010-07-19 07:12:53
@Steven: Oh, I didn't know that! Interesting...
Dean Harding
2010-07-19 07:16:08
@Filip: The ordering isn't random. The ordering will be exactly the same for those two instances, always. However, there are no guarantees that elements are stored in the same order you supply them. I expect that the results of your experiment are accidentally in that order. Also, the order might change from version to version.
Steven
2010-07-19 07:16:40
@Filip: What you're seeing is a coincidence. Two sets with the *same* contents will have the *same* order, but if you add additional elements to the set, you'll likely find that the ordering changes, since the hashtable buckets will move around as the set grows.
Dean Harding
2010-07-19 07:17:35
@Steven, I see. Are there any other Sets that are Fast and supply `Overlaps`?
Filip Ekberg
2010-07-19 07:18:46
@Dean: Open Reflector and look at the `ElementAt`, `Where` and `Last` for instance. It is nice to see what they do. Of course these optimizations come at a cost for small collections.
Steven
2010-07-19 07:18:47
The first paragraph of this answer is just plain wrong. Lots of the IEnumerable<T> extension methods (including ElementAt) attempt casts to other types (often IList<T>) that allow faster behaviour than O(n) where possible.
Will Dean
2010-07-19 08:07:27
@Will: That is exactly what we're discussing here in the comments ;-)
Steven
2010-07-19 08:49:06
@Filip: What do you mean by 'Overlaps'?
Steven
2010-07-19 08:50:47
@Steven, Just noticed `Intersects` however, I want to know if it Intersects with the Exact same order.
Filip Ekberg
2010-07-19 09:27:05
@Will, answer updated. Not that it helps in this situation anyway...
Dean Harding
2010-07-19 11:31:22
+2
A:
There is no ElementAt method in HashSet so you probably want to know the performance of the Enumerable.ElementAt method when used on an instance of HashSet<T>.
The Enumerable.ElementAt method has an optimization for types implementing IList<T>. In that case the performance is O(1). However, HashSet does not implement this interface, therefore, the performance is O(n).
Steven
2010-07-19 07:10:49
@Steven, there is an ElementAt becuase HashSet derives from ICollection.
Filip Ekberg
2010-07-19 07:11:43
@Filip: `HashSet<T>` does derive from `ICollection<T>`, but `ICollection<T>` does not have an `ElementAt` method. `HashSet<T>` does not (at least in .NET 3.5sp1) contian an `ElementAt` method.
Steven
2010-07-19 09:04:57
@Steven, I am using .NET 4.0 and ReSharper suggests me to use `ICollection<T>` where I want to take a `HashSet<T>`. Anyways, using `ToArray` speeded things up a lot.
Filip Ekberg
2010-07-19 09:28:38
@Filip: I'm not very familiar with .NET 4.0 but I'm absolutely sure that Microsoft didn't add any methods to `ICollection<T>` for that release (because this would be a severe breaking change). Resharper suggests you to use `ICollection` because all method calls you do on it are based on this interface or on extension methods on that interface or base interfaces (`IEnumerable<T>` in your case).
Steven
2010-07-19 09:38:01
@Steven, I can use ElementAt with a HashSet, don't know what else I should say..
Filip Ekberg
2010-07-19 10:59:43
@Filip: Perhaps this discussion isn't very useful to you. You propably don't care where it is defined. You call it, it compiles, it works :-). Just don't formet you are calling an extension method.
Steven
2010-07-19 11:27:16
+2
A:
It depends on the underyling list type. Reflector shows that Enumerable<T>.ElementAt(...) tries to cast to an IList<T> first. In that case it would be O(1).
A query provider for example might return something that is an IList<T>. But chances are that if you apply any of the Linq operators, it will turn into an IEnumerable<T>, because they are built merely using different enumerators, and it will become O(n).
EDIT: I overread the HashSet. A HashSet<T> doesn't implement IList<T>, thus it is O(n).
herzmeister der welten
2010-07-19 07:13:32