string comparison

[yadurajj@yahoo.com]

Hello i am newbie trying to learn C..I need to know about string
comparisons in C, without using a library function,...rec ently I was
asked this in an interview..I can write a small program but I was told
that wouldn't it be wise to first get the length of the strings..if it
doesn't match then they are not the same..I agreed...then he said..but
again that would be an overhead first measuring the length...and then
doing a character by character comparison...I was confused and was
wondering if anybody has an answer to this theory. I am only trying to
undestand...

thanks

[SM Ryan]

Re: string comparison

yadurajj@yahoo. com wrote:
# Hello i am newbie trying to learn C..I need to know about string
# comparisons in C, without using a library function,...rec ently I was
# asked this in an interview..I can write a small program but I was told
# that wouldn't it be wise to first get the length of the strings..if it

The interviewer is either a jackass (not uncommon) or trying to trick
you (also not uncommon). In general the only way to measure strings
in C is to scan them from the first character to the null character.
If you measure the strings first you're going to end up doing the same
scan twice.

In ANSI C, a string comparison function can look something like
int compare(char *a,char *b) {
int cc = 0; while (cc==0 && *a && *b) cc = *a++ - *b++;
if (cc!=0) ;
else if (*a) cc = 1;
else if (*b) cc = -1;
return cc;
}
Sometimes you can compare words in machine dependent fashion and get
a four or eight time speed up.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
You hate people.
But I love gatherings. Isn't it ironic.

[Lew Pitcher]

Re: string comparison

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

yadurajj@yahoo. com wrote:[color=blue]
> Hello i am newbie trying to learn C..I need to know about string
> comparisons in C, without using a library function,...rec ently I was
> asked this in an interview..I can write a small program but I was told
> that wouldn't it be wise to first get the length of the strings..if it
> doesn't match then they are not the same..I agreed...then he said..but
> again that would be an overhead first measuring the length...and then
> doing a character by character comparison...I was confused and was
> wondering if anybody has an answer to this theory. I am only trying to
> undestand...[/color]

Consider this: in C, a string is just an array of char, with zero or more
significant characters, and a '\0' character which terminates the string.

The length of the string is the count of the significant characters, up to
(but not including) the '\0' character.

It is true that, if the length of one string is different from the length of
another string, then the strings are different.

However, all that is really saying is that, in a character-by-character
comparison, where one string has a '\0', the other does not.

So, yes, it would be ideal to determine the lengths of the strings, but you
can only do so through a character-by-character inspection of each string.
If you are already going to examine the strings character-by-character,
comparing each character position to '\0' (to find the end, and thus the
length, of each string), there is no reason why you should not compare each
character of one string to the correspondingly placed character of the other.

Indeed, identical strings will compare identically up to and including the
'\0' character of each string. Different strings will compare identical up to
the first character difference, which may include the '\0' of one string
comparing unequal to the corresponding character of another string.


A visual example might help

String 1 A B C \0
: : : : Identical
String 2 A B C \0

or

String 1 A B C \0
: : : x Different
String 2 A B C D \0

or

String 1 A B Q \0
: : x Different
String 2 A B C \0

or even

String 1 A B Q \0
x Different
String 2 Z Y X \0

- --
Lew Pitcher

Master Codewright & JOAT-in-training | GPG public key available on request
Registered Linux User #112576 (http://counter.li.org/)
Slackware - Because I know what I'm doing.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFCuM2nagV FX4UWr64RApU+AJ 4lI1+ui+FjPPN29 OMYukiDF/QVsQCeIv9k
EhRxPiJaixr9YT9 PivVRUkw=
=EpUj
-----END PGP SIGNATURE-----

[Lew Pitcher]

Re: string comparison

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

SM Ryan wrote:
[snip][color=blue]
> In ANSI C, a string comparison function can look something like
> int compare(char *a,char *b) {
> int cc = 0; while (cc==0 && *a && *b) cc = *a++ - *b++;
> if (cc!=0) ;
> else if (*a) cc = 1;
> else if (*b) cc = -1;
> return cc;
> }[/color]

Or even

int compare_strings (char *a, char *b)
{
while (*a++ == *b++) ;
return (int)(*a-*b);
}

- --
Lew Pitcher

Master Codewright & JOAT-in-training | GPG public key available on request
Registered Linux User #112576 (http://counter.li.org/)
Slackware - Because I know what I'm doing.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFCuNMSagV FX4UWr64RAmRkAK DbXBeL3v3qA5Q0z Wfjee9pgU4LGgCg 4u5y
yykp27lAPLGzgEt oXL7eTYw=
=FAF0
-----END PGP SIGNATURE-----

[kaby@tom.com]

Re: string comparison

I suggest you may use *long* instead of *char* to get full capability
of register.
and keep one eye on snaping 32bit and 8bit.

[Peter Nilsson]

Re: string comparison

Lew Pitcher wrote:[color=blue]
> SM Ryan wrote:
> [snip][color=green]
> > In ANSI C, a string comparison function can look something like
> > int compare(char *a,char *b) {
> > int cc = 0; while (cc==0 && *a && *b) cc = *a++ - *b++;
> > if (cc!=0) ;
> > else if (*a) cc = 1;
> > else if (*b) cc = -1;
> > return cc;
> > }[/color]
>
> Or even
>
> int compare_strings (char *a, char *b)
> {
> while (*a++ == *b++) ;
> return (int)(*a-*b);
> }[/color]

I'd mark both of these as wrong. Neither replicates strcmp(). ;)

--
Peter

[CBFalconer]

Re: string comparison

Lew Pitcher wrote:[color=blue]
>[/color]
.... snip ...[color=blue]
>
> Or even
>
> int compare_strings (char *a, char *b)
> {
> while (*a++ == *b++) ;
> return (int)(*a-*b);
> }[/color]

There is a winged insect crawling over that :-)

--
Some informative links:
news:news.annou nce.newusers

http://www.geocities.com/nnqweb/

http://www.catb.org/~esr/faqs/smart-questions.html

http://www.caliburn.nl/topposting.html

http://www.netmeister.org/news/learn2quote.html

[Morris Dovey]

Re: string comparison

CBFalconer wrote:[color=blue][color=green]
>> Lew Pitcher wrote:[color=darkred]
>>>[/color]
>> ... snip ...[color=darkred]
>>>
>>> Or even
>>>
>>> int compare_strings (char *a, char *b)
>>> {
>>> while (*a++ == *b++) ;
>>> return (int)(*a-*b);
>>> }[/color]
>>
>> There is a winged insect crawling over that :-)[/color][/color]

I don't think that bug has wings... ;-)

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA

http://www.iedu.com/DeSoto

[Lawrence Kirby]

Re: string comparison

On Tue, 21 Jun 2005 19:03:16 -0700, yadurajj wrote:
[color=blue]
> Hello i am newbie trying to learn C..I need to know about string
> comparisons in C, without using a library function,...rec ently I was
> asked this in an interview..I can write a small program but I was told
> that wouldn't it be wise to first get the length of the strings..if it
> doesn't match then they are not the same.[/color]

That's a possible strategy if you are only testing for equality. But if
you also need to determine which of 2 unequal strings is greater then it
doesn't help.
[color=blue]
> .I agreed...then he said..but
> again that would be an overhead first measuring the length...and then
> doing a character by character comparison...I was confused and was
> wondering if anybody has an answer to this theory. I am only trying to
> undestand...[/color]

You have to consider whether the strings are likely to differ near the
start. If you have a 100 character string and they differed in the 2nd
character then determining the length would be a very costly operation
compared to just comparing the character sequences. And strings usually
do differ in the first couple of characters unless there is a strong
relationship between them already.

Lawrence

[Netocrat]

Re: string comparison

On Tue, 21 Jun 2005 22:54:11 -0700, Peter Nilsson wrote:
[color=blue]
> Lew Pitcher wrote:[color=green]
>> SM Ryan wrote:
>> [snip][color=darkred]
>> > In ANSI C, a string comparison function can look something like
>> > int compare(char *a,char *b) {
>> > int cc = 0; while (cc==0 && *a && *b) cc = *a++ - *b++; if (cc!=0) ;
>> > else if (*a) cc = 1;
>> > else if (*b) cc = -1;
>> > return cc;
>> > }
>> > }[/color]
>> Or even
>>
>> int compare_strings (char *a, char *b) {
>> while (*a++ == *b++) ;
>> return (int)(*a-*b);
>> }
>> }[/color]
> I'd mark both of these as wrong. Neither replicates strcmp(). ;)[/color]

The bug in the second is easy to spot, and from what I can tell the first
compare() differs from strcmp() in that strcmp() treats its arguments as
unsigned char *, whereas compare() treats them as they are when passed in:
char *.

Is that what you were referring to? If so, the problem seems to be solved
by changing the first line and adding two:
int compare(char *a,char *b) {
becomes
int compare(char *_a,char *_b) {
unsigned char *a = (unsigned char *)_a;
unsigned char *b = (unsigned char *)_b;

I'm just going by my gcc implementation - I don't know whether the
standard requires strcmp to behave this way...

[Lawrence Kirby]

Re: string comparison

On Tue, 21 Jun 2005 22:04:32 -0700, kaby wrote:
[color=blue]
> I suggest you may use *long* instead of *char* to get full capability
> of register.
> and keep one eye on snaping 32bit and 8bit.[/color]

Unless the OP is already familiar with the technique I think you are
talking about this isn't likely to mean very much. I am familiar with
techniques for handling character data a word at a time, but even then
this doesn't make an awful lot of sense. :-)

I wouldn't worry about this for the purposes of an interview question,
especially when the issue is whether to determine the length of the string
first.

Lawrence

[Lawrence Kirby]

Re: string comparison

On Wed, 22 Jun 2005 20:48:09 +1000, Netocrat wrote:
[color=blue]
> On Tue, 21 Jun 2005 22:54:11 -0700, Peter Nilsson wrote:
>[color=green]
>> Lew Pitcher wrote:[color=darkred]
>>> SM Ryan wrote:
>>> [snip]
>>> > In ANSI C, a string comparison function can look something like
>>> > int compare(char *a,char *b) {
>>> > int cc = 0; while (cc==0 && *a && *b) cc = *a++ - *b++; if (cc!=0) ;
>>> > else if (*a) cc = 1;
>>> > else if (*b) cc = -1;[/color][/color][/color]

These don't take into account the relative values of *a and *b so are
wrong.
[color=blue][color=green][color=darkred]
>>> > return cc;
>>> > }
>>> > }
>>> Or even
>>>
>>> int compare_strings (char *a, char *b) {
>>> while (*a++ == *b++) ;
>>> return (int)(*a-*b);
>>> }
>>> }[/color]
>> I'd mark both of these as wrong. Neither replicates strcmp(). ;)[/color]
>
> The bug in the second is easy to spot,[/color]

Which of the bugs in the second are you referring to? :-)

It will walk off the end of identical strings.

There are 2 instances of an off-by-one index error in the return
statement.

C doesn't guarantee that char has a smaller range than int so *a-*b could
overflow. You can usually get away with this in practice but at least a
comment is in order.

Since char values can be negative it has a curious property that a
longer string can compare less than a shorter string that is a prefix of
it (assuming a trivial fix for bug 2).
[color=blue]
> and from what I can tell the first
> compare() differs from strcmp() in that strcmp() treats its arguments as
> unsigned char *, whereas compare() treats them as they are when passed in:
> char *.[/color]

True. And using unsigned char eliminates the "curious property".
[color=blue]
>Is that what you were referring to? If so, the problem seems to be
>solved
> by changing the first line and adding two:
> int compare(char *a,char *b) {
> becomes
> int compare(char *_a,char *_b) {
> unsigned char *a = (unsigned char *)_a; unsigned char *b = (unsigned
> char *)_b;
>
> I'm just going by my gcc implementation - I don't know whether the
> standard requires strcmp to behave this way...[/color]

strcmp() is defined to act on unsigned char values.

Lawrence

[websnarf@gmail.com]

Re: string comparison

yadurajj@yahoo. com wrote:[color=blue]
> Hello i am newbie trying to learn C..I need to know about string
> comparisons in C, without using a library function,...rec ently I was
> asked this in an interview..I can write a small program but I was told
> that wouldn't it be wise to first get the length of the strings..if it
> doesn't match then they are not the same..I agreed...then he said..but
> again that would be an overhead first measuring the length...[/color]

It is *highly* unlikely that this comment was carried to its logical
conclusion. If he's talking about "performanc e", then there is a lot
more to this question than this.
[color=blue]
> [...] and then
> doing a character by character comparison...I was confused and was
> wondering if anybody has an answer to this theory. I am only trying to
> undestand...[/color]

Ok, first of all, if the lengths are intrinsically available to you in
the first place (in most situations, when you are in control of all the
code and data formats, this is generally trivial to guarantee), then
sure, you can and perhaps should first compare the lengths, afterwhich
you want to perform the equivalent of a memcmp().

If you don't have the length, and your strings are just '\0' terminated
char * strings, then performing strlen()'s first and precomparing will
never be better in terms of performance. The reason is that the whole
cost of string comparison is the loop overhead, and memory traversal.
By calling strlen twice, you are basically (roughly) tripling the loop
overhead, and doubling the memory traversal cost.

In terms of amount of work done, the moment you have enough information
to know the two lengths are different, is the same moment you can know
that the substance of the two strings are different.

Ok, so here are some remaining questions:

1) How should one implement a standard strcmp? -- as I recall, this is
like 3 lines of code.

2) How might one implement a standard memcmp? (On the assumption that
lengths are always available to you, since it basically costs nothing
for this to be the case.) Doing this naively is easy; but trying to
take advantage of low-level hardware characteristics , such as
alignment, this can be hard if you are really intent on squeezing out
the maximum performance.

3) Is this string comparison isolated? For example, let us say that
you are performing a string comparison for the purpose of inserting
into a hash table to avoid inserting duplicates. Well in this case a
scalar "trace" of the string is precomputed anyways in the form of its
hash function mapping. So if you are store the hash values along with
each string then doing this pre-compare (like the length pre-compare,
except you should expect this to have far fewer false positives) will
improve average comparison performance.

--
Paul Hsieh

http://www.pobox.com/~qed/

http://bstring.sf.net/

[Lew Pitcher]

Re: string comparison

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Lew Pitcher wrote:[color=blue]
> SM Ryan wrote:
> [snip]
>[color=green][color=darkred]
>>>In ANSI C, a string comparison function can look something like
>>> int compare(char *a,char *b) {
>>> int cc = 0; while (cc==0 && *a && *b) cc = *a++ - *b++;
>>> if (cc!=0) ;
>>> else if (*a) cc = 1;
>>> else if (*b) cc = -1;
>>> return cc;
>>> }[/color][/color]
>
>
> Or even
>
> int compare_strings (char *a, char *b)
> {
> while (*a++ == *b++) ;
> return (int)(*a-*b);
> }[/color]

Gak!!

That's what I get for off-the-cuff coding when I'm tired.

That /should/ have been
int compare_strings (char *a, char *b)
{
while (*b && (*a++ == *b++)) ;
return (int)(*a-*b);
}

- --

Lew Pitcher, IT Specialist, Enterprise Data Systems
Enterprise Technology Solutions, TD Bank Financial Group

(Opinions expressed here are my own, not my employer's)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (MingW32)

iD8DBQFCuVG5agV FX4UWr64RAvPTAJ wKHRRb0JTB+zxtf 8iHgrAAfRUmpwCf Ym8O
QFVzBgyX10UnnW6 8nJ6iOeU=
=JwjB
-----END PGP SIGNATURE-----

[Netocrat]

Re: string comparison

On Wed, 22 Jun 2005 13:28:56 +0100, Lawrence Kirby wrote:
[color=blue]
> On Wed, 22 Jun 2005 20:48:09 +1000, Netocrat wrote:
>[color=green]
>> On Tue, 21 Jun 2005 22:54:11 -0700, Peter Nilsson wrote:
>>[color=darkred]
>>> Lew Pitcher wrote:
>>>> SM Ryan wrote:
>>>> [snip]
>>>> > In ANSI C, a string comparison function can look something like
>>>> > int compare(char *a,char *b) {
>>>> > int cc = 0; while (cc==0 && *a && *b) cc = *a++ - *b++; if (cc!=0)
>>>> > ; else if (*a) cc = 1;
>>>> > else if (*b) cc = -1;[/color][/color]
>
> These don't take into account the relative values of *a and *b so are
> wrong.[/color]

At the risk of sounding clueless... I'm uncertain of firstly what you are
referring to by 'these' and secondly in any event how the relative values
aren't being taken into account. Perhaps by the second you mean that *a
and *b need to be treated as unsigned char rather than char, as you
confirm is the case later in your post?
[color=blue][color=green][color=darkred]
>>>> > return cc;
>>>> > }
>>>> > }
>>>> Or even
>>>>
>>>> int compare_strings (char *a, char *b) {
>>>> while (*a++ == *b++) ;
>>>> return (int)(*a-*b);
>>>> }
>>>> }
>>> I'd mark both of these as wrong. Neither replicates strcmp(). ;)[/color]
>>
>> The bug in the second is easy to spot,[/color]
>
> Which of the bugs in the second are you referring to? :-)
>
> It will walk off the end of identical strings.[/color]

That's where I stopped looking...
[color=blue]
> There are 2 instances of an off-by-one index error in the return
> statement.
>
> C doesn't guarantee that char has a smaller range than int so *a-*b
> could overflow. You can usually get away with this in practice but at
> least a comment is in order.
>
> Since char values can be negative it has a curious property that a
> longer string can compare less than a shorter string that is a prefix of
> it (assuming a trivial fix for bug 2).[/color]

Here's a fix then (if this were for real-life code I'd rewrite it so the
parameters were a and b rather than _a and _b but this way involves
minimal change...):

int compare_strings (char *_a, char *_b) {
unsigned char *a = (unsigned char *)_a;
unsigned char *b = (unsigned char *)_b;
while (*a && *b && *a == *b) {
a++;
b++;
}
return (int)*a-(int)*b;
}
[color=blue][color=green]
>> and from what I can tell the first
>> compare() differs from strcmp() in that strcmp() treats its arguments
>> as unsigned char *, whereas compare() treats them as they are when
>> passed in: char *.[/color]
>
> True. And using unsigned char eliminates the "curious property".[/color]

Truth be told that "curious property" is the means by which I discovered
the bug. For any string of printable characters the original function is
fine but I didn't doubt that Peter had a reason for quibbling with it, so
I dug deeper...

[snip]
[color=blue]
> strcmp() is defined to act on unsigned char values.[/color]

Cheers for the confirmation.