time limit exceeding

[GameOn]

during 1 of code need to break a string in tokens and i simply use this code

vector<string> name(string s){


char *cstr, *p;
vector<string>v;

cstr = new char [s.size()+1];
strcpy (cstr, s.c_str());



p=strtok (cstr,"/");
while(p!=NULL){
v.push_back(p);
p=strtok(NULL,"/");
}
return v;
}
i got this idea from this site only but this code is exceding time limit.
1 freind of mine gave me his code in which he didn't use strtok function and o my surprise his code is executing within time limit heres his function

vector<string> name(string s1){
string s;
vector<string> v;
for(int i=1;i<s1.size();i++){
if(s1[i]=='/'){ v.push_back(s); s="";}
else s+=s1[i];
}
if(s!="") v.push_back(s);
return v;
}
so it means predefined function strtok is having more time complexity right??
well i know that this is really stupid post but still i want to knowwhat makes my code to take more time?
please help

[Duthomhas]

My results show that the strtok() version works about twice as fast as the character-by-character version.

In any case, what do you mean by 'exceeding the time limit'?


His function misses the first character in the string. It works by looking at each character in turn. If it is not the '/', then the character is copied to the end of a temporary string, else the temporary string is added to the end of the input vector. That excessive use of push_back() is probably killing his time...

Your function is better written -- it uses the standard library the way it is supposed to be used and makes no errors in processing. You did forget to delete[] cstr; before the end of your function though (that's a memory leak).

I would have used a stringstream to parse the line:

#include <sstream>
#include <string>
#include <vector>
using namespace std;

vector <string> name( string s )
  {
  vector <string> result;
  istringstream   iss( s );
  string          token;

  while (getline( iss, token, '/' ))
    result.push_back( token );

  return result;
  }

I really don't like strtok(), but I am really impressed that you took care to use it properly (considering the fact that it modifies the input string). My function runs slower than yours though...


The thing to remember is that the difference in times is really insignificant... I had to do it 10,000 times each to calculate useful results.

Hope this helps.

[GameOn]

thx dude
well actually its a problem of some online judge, i need to split the input string to proceed and it was given that first character must be '/' so his code is doing fine. i think rest part of my code is taking more time than his thats why is exceeding the TL.
anyway i am really amazed how you so precisely comment on the time complexity of both the codes.could you please tell how you manage that.
your code is really impressive and clean, kudos for it.this will be my default code for this kind of problems in future as you said that its insignificantly affecting run time

[Duthomhas]

Google around "profiling". Here's something I snagged for you:
http://www.codeguru.com/forum/showthread.php?t=291294

If you don't have a high-precision timer, you can increase its resolution by repeating the operation N times, then divide by N to get the average execution time.

[GameOn]

dude you are just too good xoxox
heartly thanks for your efforts
:)