2
$\begingroup$

While reading the following tutorial on iOS development Working with Foundation (section on Sets near the bottom), I came across the following statement: "Because sets don’t maintain order, they offer faster performance than arrays do when it comes to testing for membership."

The author doesn't mention the underlying data structure and as it stands, I don't see how the second part of this statement can be inferred from the first.

If the NSSet class is implemented using a hash table, I agree that it will have faster lookup performance than an NSArray class but in principle both classes could be implemented using arrays, in which case both would have a lookup performance of O(n).

Am I missing something or is this just an incomplete statement?

$\endgroup$
  • 4
    $\begingroup$ You're right, no such inference can be made. You should read the sentence as: "when we implement sets we can do funky stuff that we can't when implementing arrays, because we need to keep the order of elements in an array intact." For instance, a set could be implemented as some sort of a balanced tree to give you logarithmic membership testing. With arrays it would be linear. But you can't know until you actually look at what they did in NSSet and NSArray. $\endgroup$ – Andrej Bauer Jun 30 '15 at 17:03
  • 3
    $\begingroup$ I believe the point is that, since sets don't have to remember order, they can be implemented using a datastructure that allows fast membership testing. The fact that you could implement sets in a bad way (using arrays) that has bad performance isn't really relevant. $\endgroup$ – David Richerby Jun 30 '15 at 17:05
  • 1
    $\begingroup$ In other words, this is an incomplete statement. Better would be to edit it as "... they might offer faster performance...". $\endgroup$ – Rick Decker Jun 30 '15 at 18:30
  • 1
    $\begingroup$ In sorted arrays, we have logarithmic membership tests. In bitvector representations. too. You need to clarify how you want to use sets, and what operations you want to compare. The typical scenario is that set implementations do some things well and some things badly. $\endgroup$ – Raphael Jun 30 '15 at 21:04
  • $\begingroup$ Welcome to SE Computer Science. This statement is correct, imho, if "faster" is understood non strictly, i.e., as "non slower". Otherwise it is a "non sequitur". $\endgroup$ – babou Jun 30 '15 at 22:05
1
$\begingroup$

I think the key is that NSSets aren't required to "maintain order," meaning that you cannot access elements with an index, nor can you extract elements in any particular order. Because NSSets don't offer those kinds of accesses the implementation is free to use hashing, trees or anything else that gives speedier membership checks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.