CODEWITHSUNDEEP
calgorithmstring-matching
pcambre
pcambre

Reputation: 141

Compare two matching strings algorithms - Practical approach

I wrote two differents algorithms that resolve some particular case of strings matching (implemented in C). I know that the theoretical O of this algorithms are equals but I think that in practical, one is better than the oder. My question is, someone could recommend me some paper or some reading where shows how to compare algorithms with a practical approach? I have several test set, I'm interested in measure execute time and memory size. I need take this values as independently as possible of the operating system and others program that could be runing concurrently.

Thanks!!!

Upvotes: 1

Views: 188

Answers (3)

pcambre
pcambre

Reputation: 141

In order to complete all comments, I found a book called "A guide to experimental algorithmics" by Catherine C. Mcgeoch Amazon and a profesor recommend me a practical paper pdf.

Upvotes: 0

MOHAMED
MOHAMED

Reputation: 43528

you could compare your algorithms by generating the assembly code and compare them.

You could generate the assembly code with the gcc -S mycode.c command

Upvotes: 3

Mats Petersson
Mats Petersson

Reputation: 129374

I find that "looking at the code" is a good start. If one uses more variables and is more complicated than the other, it is probably slower.

However, there are of course clever tricks that can make a more complicated function actually run faster (for example code that reads 8 bytes at a time - but of course, once you find a difference, the code is more complex - for long strings that are largely similar, there is a big win tho').

So, in the end, there is no substitute for actually running the code, using clock-cycle timing (RDTSC instruction on x86 processors, for example), or running a large loop to execute the code many times to give a reasonable length runtime.

If your code isn't supposed to run on a single embedded target, you probably want to run the code on a set of different hardware to determine if the code that is faster on processor A is also faster on B, C and D type processors. Often this does work, but sometimes you can find that a particular processor model is faster for SOME operations, and another is faster for another (for example based on cache-size, etc).

It would also be very important, in the case of string operations, to try with different size inputs, different points of difference (e.g. a long string, but different "early", vs. long string with difference "late"). Sometimes, the different approaches will show different results for short/long strings or early/late point of difference (and of course "equal" strings that are long or short).

Upvotes: 1

Related Questions