Since we've got a working implementation, we may now optimise it. Each steps will be shown, to mimic a code review session (albeit a schizophrenic one).
Phase 1 : Limit objects creation.
reverse creates new string. But reversing a view only creates a new (lightweight) view.
Indeed, replacing str.sliding by str.view.sliding halve process time. For 6 keystrokes, it's not too bad.
Phase 2 : Refine the algorithm.
Actually it should be phase 0, but you never know when ideas pop up.
Each palindrome contains matryoshka-nested palindromes.
This means all n sized ones can be detected from n-2 sized, just by checking 2 new chars at boundaries.
We introduce an helper
def collectPalindrome(str: String, from: Int, to: Int): List[String] =
if (str(from) == str(to)) {
str.slice(from, to+1) :: (if (from > 0 && to < str.size - 1) collectPalindrome(str, from-1, to+1) else Nil)
} else Nil
No superfluous object creation is involved. So it's a double win !
Since collected sizes increase by 2, we need 2 passes :
def extractPalindromes (str: String) : List[String] =
{
val evenSized: List[String] = ((for (i <- (0 to str.size - 2)) yield collectPalindrome(str,i,i+1)) flatten).toList
val oddSized: List[String] = ((for (i <- (0 to str.size - 3)) yield collectPalindrome(str,i,i+2)) flatten).toList
evenSized ++ oddSized
}
Result for genlin input :
Reference (Zwirb) : 233 s
Stopping at longest : 232 s (nb : only extract 1 palindrome)
So benchmarking proves my claim wrong.
Idem + .view. : 120 s (nb : only extract 1 palindrome)
New algorithm : 0.006 s
Phase 3 : Refactor.
So we've got a fast, memory friendly and still readable implementation.
But we can always improve.
- give the helper a more descriptive name :
collectIncreasingPalindromes
- move bound checking at top. The helper became robuster and more readable.
- hide this helper
- DRY
- document
- finally I prefer to map. Then map + flatten = flatMap
Result :
def extractPalindromes (str: String): List[String] = {
//@brief Collect nested palindromes increasing by 1 char at each end.
def collectIncreasing(from: Int, until: Int): List[String] =
if ( from < 0 || until > str.size //Out of bounds
|| str(from) != str(until-1) ) Nil
else str.slice(from, until) :: collectIncreasing(from-1, until+1)
//@brief Start to collect from given size, for each position
def collect (n: Int) = (0 to str.size - n) flatMap
(i => collectIncreasing (i, i+n))
(collect (2) ++ collect (3)).toList // Even sized then odd sized palindromes
}
Phase 4 : Parallelize.
Thanks to functional approach, it should be just a matter of switching to parallel collections.
Phase 5 : Challenge a friend
