1
\$\begingroup\$

I am using this basic extension for a Swift project. It works well, but I want to make sure it is the absolute fastest way to get a substring.

extension String {
    func substring(start: Int, end: Int) -> String {
        if (start == end || self.strlen() == 0) {
            return ""
        }
        let startIndex = self.index(self.startIndex, offsetBy: start)
        let endIndex = self.index(self.startIndex, offsetBy: end)
        return self[startIndex..<endIndex]
    } 

    func strlen() -> Int {
        return self.characters.count
    }
}

You can see I am checking for two situations that don't make since in the if then statement. Those are the only two things I need to check for. For example, I don't need to check for a situation where start is greater than end.

Should this condition be rewritten as a guard statement? Remember I'm not concerned about following best practices or writing pretty code, I just want to have an efficient substring function.

\$\endgroup\$
1
\$\begingroup\$

I see some things that might help:

index(_:, offsetBy:) is O(n) where n is the amount you're offsetting, so you can squeeze a bit out of calculating the endIndex as an offset from the startIndex especially if you're getting substrings from near the end of the string:

let startIndex = self.index(self.startIndex, offsetBy: start)
let endIndex = self.index(startIndex, offsetBy: end-start)

The other option could be to use the UTF16 view of the string instead of the character view.

The UTF16Index has an option to create directly from an Int (rather than) offsetting an index which will be faster (I assume O(1) but I can't find a reference).

let start16 = String.UTF16Index(start)
let end16   = String.UTF16Index(end)
return String(utf16[start16..<end16])!

The consideration around the UTF16 approach depends if you're going to be using text that has multi-width characters and how you're getting the actual start and end values to make the substring. Here's a post that I found useful getting my head around these options: https://oleb.net/blog/2016/08/swift-3-strings/

So it looks like there is an opportunity for a little bit of a performance increase there!

When you check to see if the string is empty you're checking if the character count is zero. self.characters.count == 0 is O(n) where n is the number of characters, you can get some performance increase here by using self.isEmpty which is O(1).

edit: added 4th option that returns String?

Finally, with the UTF16 option there's the need to cast to a String and force unwrap if you want to return the type String. An alternative could be to return nil instead as your early exit:

I ran a quick profile in Xcode comparing those four options:

1. Baseline approach (in question)
2. Alternative (use isEmpty and calculate endIndex from startIndex)
3. UTF16 (use isEmpty and create UTF16 index directly from Int)
4. UTF16 nil (use isEmpty, create UTF16 index from Int and return String?)

Benchmark substring using "hello tests".substring(1,10)

1. Baseline    -> 1.151s  (2% STDEV)
2. Alternative -> 0.633s  (1% STDEV)
3. UTF16       -> 0.408s  (2% STDEV)
4. UTF16 nil   -> 0.404s  (1% STDEV)

Benchmark early exit using "".substring(1,10)

1. Baseline    -> 0.074s  (4% STDEV)
2. Alternative -> 0.024s (12% STDEV)
3. UTF16       -> 0.024s (11% STDEV)
4. UTF16 nil   -> 0.019s (12% STDEV)

Here's a gist of the test I used for full transparency: https://gist.github.com/mathewsanders/c4c43915c5e1c13e8fe3b912bf4c27d1

So absolutely use isIndex instead of counting characters, and maybe consider using the UTF16 view if it's appropriate for the text you'll be making substrings from.

It also looks like returning nil instead of an empty string gives a bit of a boost, but you might loose that small advantage elsewhere in your code depending on how you handle the nil` return.

\$\endgroup\$
  • \$\begingroup\$ This worked tremendously. Option 3 worked for me. I will accept your answer if no one else gives a better one. \$\endgroup\$ – twharmon Jan 3 '17 at 6:23
  • 1
    \$\begingroup\$ UTF-18 was an April Fools' Day RFC joke. \$\endgroup\$ – Martin R Jan 3 '17 at 12:13
  • \$\begingroup\$ @MartinR ◔̯◔ good spot. Answer updated! \$\endgroup\$ – MathewS Jan 3 '17 at 16:03
1
\$\begingroup\$

The padding function yields some interesting results:

extension String 
{
    public func substring2(start: Int, end: Int) -> String 
    { 
      return "".padding(toLength:end-start, withPad:self, startingAt:start)
    }    
}

It is less impacted by the start position. I got results on an 88 character string that were about 4.5 times faster than the OP's function with a 5 character substring starting at 10.

This performance difference increased to 9.9 times faster with a start of 80.

Additional testing showed that, the optimized version (that uses isEmpty() and computes endIndex relative to startIndex) is faster than this padding approach when the end is less than 35. Beyond that, the padding approach is faster and progressively much faster as the end parameter increases.

The padding function seems to somehow get to the first character in O(1) then it gets the substring in O(n) as a function of the length of the substring independently of the position in the main string.

You could probably combine the two approaches and select one based on the value the end parameter.

\$\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.