Re: why is this code so slow?
Somebody skrev:
<cpunerd@gmail.com> wrote in message
news:1177990346.022115.312180@n76g2000hsh.googlegroups.com...
On Apr 30, 8:24 pm, "Somebody" <someb...@cox.net> wrote:
<snip>
the string library is probably intrinsic with your compiler, and
strcmp works off the knowledge that one can compare multiple bytes at
a time before the end of the string. it may be faster for you to write
an inlined function that finds the first number in a string, then
strcmp the bytes previous to the numbers, and then do your inlined
compare of the numbers
Hmm...
I did think of doing something like that, but even though the example string
I gave above was "nice"... it isn't always going to be that way. Imagine if
you have something like "DVD-ISO9817-FULLIMAGE-1-07-2005" as an example. I'd
have to compare every string segment of the string seperately and keep track
of where I'm at. I thought it would be more overhead.
What about:
(Written without enough debugging, but I expect it to work. Not benchmarked)
//---------------------------------------------------------------------------
#include <set>
#include <ostream>
#include <algorithm>
#include <iterator>
inline bool isd(char c) {
return (c >= '0') && (c <= '9');
}
int cmplogic(char const * a, char const * b) {
int result = 0;
bool ad,bd,ab,ob,pb = false;
while(*a && *b) {
ad = isd(*a);
bd = isd(*b);
ab = ad && bd;
ob = !ab && (ad || bd);
if(*a < *b) {
if(ab) { if(!result) result = -1; }
else if(pb && ob) return 1;
else if(pb && !ab) return result?result:-1;
else return -1;
} else
if(*a > *b) {
if(ab) { if(!result) result = 1; }
else if(pb && ob) return -1;
else if(pb && !ab) return result?result:1;
else return 1;
} else
if(result) return result;
pb = ab;
++a;
++b;
}
if(!(*a || *b)) {
return result;
}
if(*a) {
if(isd(*a)) return 1;
return result?result:1;
}
if(isd(*b)) return -1;
return result?result:-1;
}
struct diff {
bool operator()(char const * a, char const * b) {
return cmplogic(a,b) == -1;
}
};
int main(int argc, char* argv[])
{
std::set<char const *,diff> s;
s.insert("string11");
s.insert("string1");
s.insert("2u");
s.insert("963y");
s.insert("963h");
s.insert("string481");
s.insert("DVD-ISO9817-FULLIMAGE-1-08-2006");
s.insert("string23u4");
s.insert("string25");
s.insert("string10");
s.insert("41");
s.insert("string110");
s.insert("string23a");
s.insert("string2");
s.insert("string23u21");
s.insert("963");
s.insert("957");
s.insert("DVD-ISO9817-FULLIMAGE-1-07-2006");
s.insert("DVD-ISO9819-FULLIMAGE-2-07-2005");
std::copy(s.begin(),s.end(),
std::ostream_iterator<char const*>(std::cout,"\n"));
return 0;
}
//---------------------------------------------------------------------------
Outputs:
2u
41
957
963
963h
963y
DVD-ISO9817-FULLIMAGE-1-07-2006
DVD-ISO9817-FULLIMAGE-1-08-2006
DVD-ISO9819-FULLIMAGE-2-07-2005
string1
string10
string11
string23
string23a
string23u4
string23u21
string25
string110
string481
--
OU