3
\$\begingroup\$

A classic problem to split a string into its "root and suffix":

There are many ways to implement the same algorithm, so, what is the best? Examples in PHP, but valid for any language.

/**
 * Splits a string by its root and sufix.
 * @param $str string input
 * @param $root string empty when no root, or start string
 * @return array (rootFlag,sufix) 
 */
function  str_splitByRoot($str, $root){
    ...
}

Algorithms str_splitByRoot1(), str_splitByRoot2(), ..., str_splitByRoot5() or other (show more if you know). All do the same thing, are valid solutions.

function  str_splitByRoot1($str, $root){
    if (strpos($str,$root)===0)
        return array($root, substr($str, strlen($root)) );
    else 
        return array( '', $str );
}

function  str_splitByRoot2($str, $root){
    $rootLen = strspn($str ^ $root, "\0");
    return array( substr($root,0,$rootLen), substr($str,$rootLen) );
}

function  str_splitByRoot3($str, $root){
    $s = explode($root,$str);
    return ( count($s)>1  && !array_shift($s) )? 
      array($root,join($root,$s)): 
      array('',$str);
}

function  str_splitByRoot4($str, $root){
    // to generalize need a secure regex, something like
    // $regex = str_replace(array('/','.','-'),array('\\/','\\.','\\-'),$root);
    $suffix = preg_replace("/^$root/",$str,1,$n);
    return $n? 
      array($root,$suffix): 
      array('',$str);
}

function  str_splitByRoot5($str, $root){
    // need also $root translating as algorithm 4.
    if (preg_match("/^$root(.+)$/",$str,$m))
          return array($root,$m[1]);
    else 
          return array('',$str);
}

The first is the traditional way. The last (algorithms 4 and 5) use regular expression, the second trim excess garbage from strings that are null terminated; and the third remember that the algorithm is a kind of split (explode function).

All can be used with

function str_sepByRoot($str,$root){
   return join(' * ',str_splitByRoot($str,$root)); 
}
print "\n".str_sepByRoot("walking","walk");
print "\n".str_sepByRoot("hello","walk");
print "\n".str_sepByRoot("walking-walk-walk","walk");
print "\n".str_sepByRoot("/var/www/myApp","/var/www/");
print "\n".str_sepByRoot("10.1038/ncomms7368","10.1038/ncomms");

returning

   walk * ing
    * hello
   walk * ing-walk-walk
   /var/www/ * myApp
   10.1038/ncomms * 7368
\$\endgroup\$
1
\$\begingroup\$

About "best thing"... The "principle of simplest is best" seems valid. The number of commands, and the computational simplicity of each command.

  • str_splitByRoot1: 2 fast commands (strpos and substr) and 1 condition and strlen
  • str_splitByRoot2: 2 fast commands (substr) and 1 to be checked (strspn+str ^ str)
  • str_splitByRoot2 optimized: 1 fast command (substr), 1 to be checked (strspn) and 1 condition.
  • ...

So, my doubt was about strspn+str ^ str performance... And its time struck me most, was near time for str_splitByRoot1...

  $str_splitByRoot = array(
       function  ($str, $root){  // str_splitByRoot1()
            if (strpos($str,$root)===0)
                return array($root, substr($str, strlen($root)) );
           else 
                   return array( '', $str );
       },

       function  ($str, $root){ //str_splitByRoot2()
           $rootLen = strspn($str ^ $root, "\0");
           return array( substr($root,0,$rootLen), substr($str,$rootLen) );
       },
       function  ($str, $root){ //str_splitByRoot2() optimized
           $rootLen = strspn($str ^ $root, "\0");
           return array( $rootLen?$root:'' , substr($str,$rootLen) );
       },

       function  ($str, $root){  //str_splitByRoot3()
         $s = explode($root,$str);
         return ( count($s)>1  && !array_shift($s) )? 
             array($root,join($root,$s)): 
             array('',$str);
       }   

       function ($str, $root){ // str_splitByRoot5
            $root2 = str_replace(array('/','.','-'),array('\\/','\\.','\\-'),$root);
           if (preg_match("/^$root2(.+)$/",$str,$m))
                 return array($root,$m[1]);
           else 
                 return array('',$str);
       }
  );


  function str_sepByRoot($i,$str,$root){
       global $str_splitByRoot;
       global $debug;
            $func = $str_splitByRoot[$i];
            $s = join(' * ', call_user_func($str_splitByRoot[$i],$str,$root)); // $func($str,$root));
            if ($s &&  $debug)
                 print "\n ___ $s";
  }

  $debug=0;
  for ($i=0; $i<count($str_splitByRoot); $i++) {
       print "\n--- $i ---";
       $time = microtime(true); // time in Microseconds
       for($j=0;($j<333 && !$debug) || ($debug && $j<1); $j++){
            str_sepByRoot($i,"walking","walk");
            str_sepByRoot($i,"hello","walk");
            str_sepByRoot($i,"walking-walk-walk","walk");
            str_sepByRoot($i,"/var/www/myApp","/var/www/");
            str_sepByRoot($i,"DOI:10.1038/ncomms7368","DOI:10.1038/ncomms");     
       }
       echo "\n", (microtime(true) - $time) . ' elapsed';
  }

Result:

--- 0 ---
0.0037140846252441 elapsed
--- 1 ---
0.0045409202575684 elapsed
--- 2 ---
0.0040040016174316 elapsed
--- 3 ---
0.0088369846343994 elapsed
--- 4 ---
0.0075829029083252 elapsed
--- 5 ---
0.0037930011749268 elapsed

Conclusion, using str_splitByRoot1 as reference (100%),

  • str_splitByRoot2 optimized is ~105% , so for practical use it's as good as str_splitByRoot1.

  • str_splitByRoot2 is ~115%, something good when compared with str_splitByRoot3 (~125%).

  • str_splitByRoot5 is 225%... as expected, the worst (even without str_replace regex escapes).


... But, the performance changes (!) when using a big root, an Lorem ipsum of 800 words. The performance profile changed to:

  • str_splitByRoot2 (optimized or not) ~244%... bad!

  • str_splitByRoot3 (with direct split by explode) is ~120%, very good!

  • str_splitByRoot5 (regex) ~390%, the worst of course.

So, the only that shows more "stability" (~120%) about root length was str_splitByRoot5, and str_splitByRoot2 is not a good replacement for str_splitByRoot1 in the context of big roots.

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