2

In Swift 2, given a string s, what's the runtime complexity of these statements:

s.characters.count
s.endIndex
s.utf8.count
s.utf16.count
s.unicodeScalars.count

Also, if I know a string contains alphabets only, what's the most efficient way of getting the n-th character?

KTPatel
  • 1,212
  • 4
  • 19
  • 24
Ethan
  • 18,584
  • 15
  • 51
  • 72

2 Answers2

2

OK, I'm trying to answer my own question. Feel free to correct me if I'm wrong.

s.characters.count  // O(N)
s.endIndex // O(1)
s.utf8.count // O(N)
s.utf16.count // O(N)
s.unicodeScalars.count // O(N)

Apple's documentation on CollectionType.count says "Complexity: O(1) if Index conforms to RandomAccessIndexType; O(N) otherwise." Since none of the Index of CharacterView, UnicodeScalarView, UTF16View or UTF8View conforms to RandomAccessIndexType, accessing their counts are all O(N).

Ethan
  • 18,584
  • 15
  • 51
  • 72
  • Ethan, if you want this answer to be complete, you'll need to include the operations `s.characters`, `s.utf16` and so on. Those complexity values you list are once you *have* the collection type, and don't necessarily include converting a string into that type. – paxdiablo Oct 13 '15 at 06:30
  • You're right but we could assume that those operations won't be worse than O(N). – Ethan Oct 14 '15 at 05:41
  • If you're going to assume that, you may as well assume the answers for your question as well. Either you want a definitive answer or not :-) – paxdiablo Oct 14 '15 at 06:38
  • I would be surprised if it's not the case. They are probably O(1). – Ethan Oct 14 '15 at 06:48
1

If you don't have access to the source code for those expressions (you don't, unless you work for Apple), and the documentation doesn't mention the complexity (it doesn't, I've checked), it might be worth actually benchmarking the operations with strings of size 1, 10, 100, 1000 and so on.

The resulting data, while not definitive, would at least give you an indication of the time complexity for each.

In terms of getting the correct character at a given index of a string, that's already covered here. Whatever method Apple will have chosen for indexing a string is going to be as fast as they can make it (they're not in the business of preferring slow code over fast, all other things being equal).

Community
  • 1
  • 1
paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • I deleted my answer as I felt yours was better. Here's a [link to the documentation for `String`](https://developer.apple.com/library/watchos/documentation/Swift/Reference/Swift_String_Structure/index.html#//apple_ref/swift/struct/s:SS), if you'd like to add it to your answer. – Charles A. Oct 13 '15 at 05:16
  • Thanks for your answer but I don't think you are answering my questions. We don't have access to the source code but we do have access to the documentations. And I'm not asking how to get a character by its index but the most efficient way to do so. – Ethan Oct 13 '15 at 05:45
  • @Ethan, I *am* answering the first question. In the absence of source code and a definitive statement in the doco, the only way you can find out is to test. You have neither the source nor a statement in the doco so that's what you'll have to do. And I'll guarantee that Apple will have made the string indexing as fast as possible so you should just use what they've provided. I'll try to make my intent clearer. – paxdiablo Oct 13 '15 at 05:52
  • Apple doesn't provide source code for now but it does provides docs. See my answer. – Ethan Oct 13 '15 at 06:18