1

According to Time complexity of Java's substring(), java's substring takes linear time. Is there a faster way (may be in some cases)? I may suggest iterator, but suspect that it also takes O(n). 

val s1: String  = s.iterator.drop(5).mkString

But several operations on an iterator would be faster than same operations on string, right?

Community
  • 1
  • 1
ov7a
  • 1,497
  • 4
  • 15
  • 34

2 Answers2

5

If you need to edit very long string, consider using data structure called Rope.

Scalaz library has Cord class which is implementation of modified version of Rope.

A Cord is a purely functional data structure for efficiently storing and manipulating Strings that are potentially very long. Very similar to Rope[Char], but with better constant factors and a simpler interface since it's specialized for Strings.

ymonad
  • 11,710
  • 1
  • 38
  • 49
1

As Strings are - according to the linked question - always backed by a unique character array, substring can't be faster than O(n). You need to copy the character data.

As for alternatives: there will at least be one operation which is O(n). In your example, that's mkString which collects the characters in the iterator and builds a string from them.

However, I wouldn't worry about that too much. The fact that you're using a high level language means (should mean) that developer time is more valuable than CPU time for your particular task. substring is also the canonical way to ... take a substring, so using it makes your program more readable.

EDIT: I also like this sentence (from this answer) a lot: O(n) is O(1) if n does not grow large. What I take away from this is: you shouldn't write inefficient code, but asymptotical efficiency is not the same as real-world efficiency.

Community
  • 1
  • 1
Silly Freak
  • 4,061
  • 1
  • 36
  • 58
  • Totally agree, but what about large strings (like 1M or larger)? – ov7a Aug 21 '15 at 13:59
  • @ChelovekChelovechnii In that case, String maybe isn't for you. I'd edit the question to clarify that you are not asking about Strings exclusively, but any data structures for large character sequences. – Silly Freak Aug 21 '15 at 15:08