on complexity [Was: on goto]
in [General Programming]
|
Prev: on complexity [Was: on goto]
Next: on complexity
From: Richard Heathfield on 12 May 2010 07:31 Nick Keighley wrote: <snip> > the files are faily small so i sent them anyway. Now that I've had a chance to look at these, I think I can see why the SEME graph is so simple, and it's this - the code doesn't actually work. Try this (tested) code instead: #include <stdio.h> #include <assert.h> #define XLIM 6 #define YLIM 7 #define ZLIM 8 struct point_ { int x; int y; int z; }; typedef struct point_ point; void point_assign(point *p, int x, int y, int z) { assert(p != NULL); p->x = x; p->y = y; p->z = z; } static int haystack[XLIM][YLIM][ZLIM]; /*hackhackhackblech*/ int seme_find(point *p, int needle) { int x; int y; int z; for(x = 0; x < XLIM; x++) { for(y = 0; y < YLIM; y++) { for(z = 0; z < ZLIM; z++) { if(haystack[x][y][z] == needle) { point_assign(p, x, y, z); return 1; } } } } return 0; } int sese_find(point *p, int needle) { int x; int y; int z; int found = 0; for(x = 0; !found && x < XLIM; x++) { for(y = 0; !found && y < YLIM; y++) { for(z = 0; !found && z < ZLIM; z++) { if(haystack[x][y][z] == needle) { point_assign(p, x, y, z); found = 1; } } } } return found; } int main(void) { point p = {0}; int needle = 42; haystack[3][4][5] = needle; if(seme_find(&p, needle)) { printf("seme: Found %d at %d, %d, %d\n", needle, p.x, p.y, p.z); } else { printf("seme: Not found.\n"); } if(sese_find(&p, needle)) { printf("sese: Found %d at %d, %d, %d\n", needle, p.x, p.y, p.z); } else { printf("sese: Not found.\n"); } return 0; } -- Richard Heathfield <http://www.cpax.org.uk> Email: -http://www. +rjh@ "Usenet is a strange place" - dmr 29 July 1999 Sig line vacant - apply within
From: Nick Keighley on 12 May 2010 08:03 On 12 May, 12:31, Richard Heathfield <r...(a)see.sig.invalid> wrote: > Nick Keighley wrote: > > <snip> > > > the files are faily small so i sent them anyway. > > Now that I've had a chance to look at these, I think I can see why the > SEME graph is so simple, and it's this - the code doesn't actually work. > > Try this (tested) code instead: <snip code> what'd I do wrong? Your code compiles and runs and gives the same answers for both functions. But it still says they both have a complexity of 5 Ah, but the graphs look much more similar. Near identical. Pictures on their way
From: Richard Heathfield on 12 May 2010 08:26 Nick Keighley wrote: > On 12 May, 12:31, Richard Heathfield <r...(a)see.sig.invalid> wrote: >> Nick Keighley wrote: >>> the files are faily small so i sent them anyway. >> Now that I've had a chance to look at these, I think I can see why the >> SEME graph is so simple, and it's this - the code doesn't actually work. >> >> Try this (tested) code instead: > > <snip code> > > what'd I do wrong? Well, for one thing, you missed a semicolon! :-) Also, you didn't provide any mechanism for the "found" status to be reported to the caller. -- Richard Heathfield <http://www.cpax.org.uk> Email: -http://www. +rjh@ "Usenet is a strange place" - dmr 29 July 1999 Sig line vacant - apply within
From: Daniel T. on 12 May 2010 09:18 Richard Heathfield <rjh(a)see.sig.invalid> wrote: > Nick Keighley wrote: > > On 12 May, 12:31, Richard Heathfield <r...(a)see.sig.invalid> wrote: > > > Nick Keighley wrote: > > > > > > > the files are faily small so i sent them anyway. > > > Now that I've had a chance to look at these, I think I can see why > > > the SEME graph is so simple, and it's this - the code doesn't > > > actually work. > > > > > > Try this (tested) code instead: > > > > <snip code> > > > > what'd I do wrong? > > Well, for one thing, you missed a semicolon! :-) > > Also, you didn't provide any mechanism for the "found" status to be > reported to the caller. Now compare the complexity of both to: // cyclomatic complexity of 2, maybe 3 depending on the tool. int one_loop_find(point* p, int needle) { int i = 0; while (i < XLIM * YLIM * ZLIM && ((int*)haystack)[i] != needle) ++i; return i; } int main(void) { //... if (one_loop_find(&p, needle) != XLIM * YLIM * ZLIM) { printf("one_loop_find: Found %d at %d, %d, %d\n", needle, p.x, p.y, p.z); } else { printf("sese: Not found.\n"); } return 0; }
From: Richard Heathfield on 13 May 2010 07:11
Nick Keighley wrote: <snip> > > Your code compiles and runs and gives the same answers for both > functions. > > But it still says they both have a complexity of 5 > Ah, but the graphs look much more similar. Near identical. > Pictures on their way And now they're on the Web. Please note that, as the URL suggests... <http://www.cpax.org.uk/scratch/seseseme.php> ....I'm liable to reclaim that scratch space at any time. (In practice, I'll probably be too lazy, though, so the link should be good for a little while yet.) Personally, I find the SESE (right-hand) version to be visually simpler. -- Richard Heathfield <http://www.cpax.org.uk> Email: -http://www. +rjh@ "Usenet is a strange place" - dmr 29 July 1999 Sig line vacant - apply within |