C help, little efficiency problem

[Korialstrasza]

so, for school I have to write a program which uses a structure to store information on books like a library would have. My problem comes at the sorting part. I have to sort the books alphabetically by title, author, etc. I got it to work fine, but I have a sort function for each method, which the teacher isn't going to like. How can I compress it down to a single function (or two, one for ints (# of pages and rating of book) and one for strings (author names, titles, etc)?

Here's what I have now.

int index is the total number of books in the structure, btw.

the prototypes for the sorting functions:

void sortName(int, struct BOOKS[]);        // sort by name
void sortGenre(int, struct BOOKS[]);    // sort by genre (category)
void sortAuthor(int, struct BOOKS[]);    // sort by author
void sortRating(int, struct BOOKS[]);    // sort by rating
void sortPages(int, struct BOOKS[]);    // sort by pages

// structure for holding book information
struct BOOKS
{
    char name[50];
    char author[50];
    char category [50];
    int rating;
    int pages;
};

switch case in main() for the user's choice on what to sort

       switch (choice)
    {
        case 1: // sort by name
            sortName(index,info);
            break;
        case 2: // sort by author
            sortAuthor(index,info);
            break;
        case 3: // sort by genre
            sortGenre(index,info);
            break;
        case 4: // sort by rating
            sortRating(index,info);
            break;
        case 5: // sort by pages
            sortPages(index,info);
            break;
    }

all the sort functions

void sortGenre(int index, struct BOOKS info[])
{
    struct BOOKS temp;
    int x = 0, y = 0;
    for(x = 0; x < index; x++)
    for(y = 0; y < index-1; y++)
    if(strcmp(info[y].category, info[y+1].category) > 0)
    {
        temp = info[y];
        info[y] = info[y+1];
        info[y+1] = temp;
    }
    printf("\n\nSORTED!\n\n");
}

void sortName(int index, struct BOOKS info[])
{
    struct BOOKS temp;
    int x = 0, y = 0;
    for(x = 0; x < index; x++)
    for(y = 0; y < index-1; y++)
    
    if(strcmp(info[y].name, info[y+1].name) > 0)
    {
        temp = info[y];
        info[y] = info[y+1];
        info[y+1] = temp;
    }
    printf("\n\nSORTED!\n\n");
}

void sortAuthor(int index, struct BOOKS info[])
{
    struct BOOKS temp;
    int x = 0, y = 0;
    for(x = 0; x < index; x++)
        for(y = 0; y < index-1; y++)
            if(strcmp(info[y].author, info[y+1].author) > 0)
            {
                temp = info[y];
                info[y] = info[y+1];
                info[y+1] = temp;
            }
    printf("\n\nSORTED!\n\n");
}

void sortRating(int index, struct BOOKS info[])
{
    struct BOOKS rating;
    int x = 0, y = 0;
    for(x = 0; x < index; x++)
        for(y = 0; y < index-1; y++)
            if(info[y].rating > info[y+1].rating)
            {
                rating = info[y];
                info[y] = info[y+1];
                info[y+1] = rating;
            }
    printf("\n\nSORTED!\n\n");
}

void sortPages(int index, struct BOOKS info[])
{
    struct BOOKS pages;
    int x = 0, y = 0;
    for(x = 0; x < index; x++)
        for(y = 0; y < index-1; y++)
            if(info[y].pages > info[y+1].pages)
            {
                pages = info[y];
                info[y] = info[y+1];
                info[y+1] = pages;
            }
    printf("\n\nSORTED!\n\n");
}

Thanks guys.

 

[HHunt]

The only easy way I can think of that would let you program only one sorting loop, would be to use some form of offset to tell the sorting function which part of the struct to use. I'll see if I can come up with anything.

 

[Fryguy8]

use generics

 

[BillLeeLee]

Generics won't be terribly useful unless he can use C++ - from the sound of it, he's limited to using C only.

 

[HHunt]

Generics won't be terribly useful unless he can use C++ - from the sound of it, he's limited to using C only.

That's the impression I got too.
With that in mind, one option is to find out at what offset from the beginning of the struct the different arrays are, and send these offsets to the function.
edit: Slightly changed.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct test {
	char a[20];
	char b[20];
	char c[20];
};

void print_val(struct test st[] , unsigned int offset) {
	printf("%s\n", (char*) &st[5] + offset);
}

int main(int argc, char **argv) {
	struct test st[10];
	unsigned int A_OFFSET, B_OFFSET, C_OFFSET;
	
	A_OFFSET = (unsigned int) st->a - (unsigned int) st;
	B_OFFSET = (unsigned int) st->b - (unsigned int) st;
	C_OFFSET = (unsigned int) st->c - (unsigned int) st;
	
	printf("a:%i b:%i c:%i\n", A_OFFSET, B_OFFSET, C_OFFSET);
	
	strlcpy(st[5].a, "a", sizeof(st->a));
	strlcpy(st[5].b, "b", sizeof(st->b));
	strlcpy(st[5].c, "c", sizeof(st->c));
	print_val(st, A_OFFSET);
	print_val(st, B_OFFSET);
	print_val(st, C_OFFSET);
	return 0;
}

It's quite arbitrary that I use element 5 in the array; I just wanted to show that it still works for indices > 0.


Output:

> gcc -Wall -ansi strukt.c -o st
> ./st
a:0 b:20 c:40
a
b
c

 

[1tbs4life]

Why not just use qsort() and pass in your own comparison function? Here's how you'd sort the array by author:

int authcmp(const void* a, const void* b) {
    return strcmp(((BOOKS*)a)->author, ((BOOKS*)b)->author);
}

int main() {
    struct BOOKS b[n] = { /* blah blah blah */ };
    qsort(b, n, sizeof(BOOKS), authcmp);
    return 0;
}

I didn't test it out but it should work fine. You can just make other functions (namecmp, pagecmp, etc.) to get the rest done. If your teacher is forcing you to use a crappy hand-written bubble sort then just forget what I said (or have your functions accept a function pointer as qsort() does).

 

[HHunt]

Why not just use qsort() and pass in your own comparison function? Here's how you'd sort the array by author:

int authcmp(const void* a, const void* b) {
    return strcmp(((BOOKS*)a)->author, ((BOOKS*)b)->author);
}

int main() {
    struct BOOKS b[n] = { /* blah blah blah */ };
    qsort(b, n, sizeof(BOOKS), authcmp);
    return 0;
}

I didn't test it out but it should work fine. You can just make other functions (namecmp, pagecmp, etc.) to get the rest done. If your teacher is forcing you to use a crappy hand-written bubble sort then just forget what I said (or have your functions accept a function pointer as qsort() does).

Incidentally, this works even if you can't use qsort, you just need to make your sorting routine accept and use a function pointer.

 

[Fryguy8]

Generics won't be terribly useful unless he can use C++ - from the sound of it, he's limited to using C only.

by generics I meant the functionality built into c, namely void*

the same way qsort() works

 

[HHunt]

by generics I meant the functionality built into c, namely void*
the same way qsort() works

As long as he's only sorting string fields, it would actually be better to stick with using the right types instead of casting everything to and from void*.
E.g.:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct test {
	char a[20];
	char b[20];
	char c[20];
};


void print_val(struct test st[] , char *(get_part)(struct test*) ) {
	printf("%s\n", get_part(&st[0]));
}

char *(get_a) (struct test *st) { return st->a; }
char *(get_b) (struct test *st) { return st->b; }
char *(get_c) (struct test *st) { return st->c; }

int main(int argc, char **argv) {
	struct test st[10];
		
	strlcpy(st[0].a, "a", sizeof(st->a));
	strlcpy(st[0].b, "b", sizeof(st->b));
	strlcpy(st[0].c, "c", sizeof(st->c));
	
	print_val(st, get_a);
	print_val(st, get_b);
	print_val(st, get_c);
	
	return 0;
}

Everything considered, I think this is a better solution than the offset hack I did above.
It ought to be a hair slower (you get the overhead of a function call), but that's unlikely to make any difference unless it's called an awful lot of times. Compared to the cost of a strcmp on two nontrivial strings, a function call in itself is practically free, anyway.

edit: Here is a true worst case.

int main(int argc, char **argv) {
	struct test st[10];
	unsigned int i;
	char b;
	strlcpy(st[0].b, "*", sizeof(st->b));
	for(i=0; i<10000000; ++i) b = get_b(&st[0])[0];
	for(i=0; i<10000000; ++i) b = ( (char*) ((unsigned int) &st[0] + 20) ) [0];
	printf("%c\n", b);
	return 0;
}

When compiled with the upper for-loop (function pointer that gets a usable pointer), I get this:

> time ./st2
*
        0.07 real         0.06 user         0.00 sys

The lower for-loop (add the right offset) looks like this:

> time ./st2
*
        0.03 real         0.02 user         0.00 sys

Normally, you shouldn't think about this. It's much more important to write readable and understandable code than to wring every last bit of speed out of everything. However, now and then you might have to speed up a very hot loop, and that's where things like this come into play. Another solution is move the specialisation out a step, so the most intensive parts don't have to use anything generic.

(I tend to ramble, don't I.)

 

[mikeblas]

C implements a simple form of generics: function pointers. Look at the way that the qsort() runtime library function takes a pointer to a comparison function. That usually uses QuickSort, which will be faster than your exchange sort.

You can call qsort() in a switch with pointers to functions that do the different comparisons you'd like.

Using an efficient sorting algorithm is going to be your big speed-up, I think.

LATER: Sorry; I got on the phone, and didn't post or refresh. Looks like 1tbs4life already made the point about qsort().

As long as he's only sorting string fields, it would actually be better to stick with using the right types instead of casting everything to and from void*.

Better for performance? Not really. Better for readability? Probably not; this is C, and not C++.

When compiled with the upper for-loop (function pointer that gets a usable pointer), I get this:

You're using an awful coarse timer to measure a very fine difference. Even so, you've found that the pointer-offset method is about 3 faster slower than the function call approach.

By the way, this doesn't look right:

	strlcpy(st[0].b, "*", sizeof(st->b));

You're copying 20 bytes from "*", which is only two bytes, into a buffer of 20 bytes.

 

[HHunt]

(regarding using void* or not)
Better for performance? Not really. Better for readability? Probably not; this is C, and not C++.

Better for not throwing away type checking at compile time and removing a few casts.

You're using an awful coarse timer to measure a very fine difference. Even so, you've found that the pointer-offset method is about 3 faster slower than the function call approach.

Regarding "doesn't look right".
And, yes, the function call method was about three times slower. I had to use a silly amount of iterations to get measurable results, though, so a better summary might be that neither adds a notable overhead.

By the way, this doesn't look right:

	strlcpy(st[0].b, "*", sizeof(st->b));

You're copying 20 bytes from "*", which is only two bytes, into a buffer of 20 bytes.

No, I'm not. According to the manpage:

size_t strlcpy(char *dst, const char *src, size_t size);
The strlcpy() function copies up to size - 1 characters from the NUL-terminated string src to dst, NUL-terminating the result.
(...)
The strlcpy() and strlcat() functions return the total length of the string they tried to create. For strlcpy() that means the length of src.

 

[mikeblas]

And, yes, the function call method was about three times slower. I had to use a silly amount of iterations to get measurable results, though, so a better summary might be that neither adds a notable overhead.

Well, you only need to sort 750,000 elements to call the comparison function ten million times, so I think that 3x overhead on such small problems is very notable.

No, I'm not.

Oh, up to? That is, the count is a limit on the destination and not a specification of the source? Then that makes sense, you're right -- I guess I was thinking of strncpy.

 

[HHunt]

Well, you only need to sort 750,000 elements to call the comparison function ten million times, so I think that 3x overhead on such small problems is very notable.

Compared to ten million calls to strcmp(), it's merely statistical noise ... I think. Now I almost have to write a test case.
edit, I thought about something.
Given N elements, and his implementation of bubble sort:
Every iteration of bubble sort does N comparisations, and there are N iterations. Classic O(N²), and to pass 10 000 000, you only need 3 163 elements.
750 000 would net you a slightly scary 562 500 000 000.
Or have I forgotten something?

Oh, up to? That is, the count is a limit on the destination and not a specification of the source? Then that makes sense, you're right -- I guess I was thinking of strncpy.

Exactly.
I'm rather fond of strlcpy, shame it's not implemented in GNU libc.

 

[mikeblas]

Compared to ten million calls to strcmp(), it's merely statistical noise ... I think. Now I almost have to write a test case.

There's two questions here.

One is of "efficiency", which Korialstrasza seems to think means writing less code. Compactnes of expression, or something -- sure. I guess I can agree with that, but I'm not sure that I'd assert writing understandable code is more important than fining performance. I'd rather implement a readable version of a faster algorithm that's hard to understand than cater to the lowest common demoninator and write simple code that leaves something on the table for my users.

The other question is of efficiency in the time it'll take this code to run.

The original algorithm is pretty inefficient. As a poor implementation of bubblesort, it's going to do n^2 comparisons on n elements. We've suggested using qsort(), which is usually implemented with quick sort, which we can expect to use n*log if properly implemented. Solving 10000000 = n*log for n gives 740-something-thousand for n.

750 000 would net you a slightly scary 562 500 000 000.

Indeed, this is correct, for bubble sort--particularly one that doesn't exit early.

Fixing the buble sort implementation will result in a win, though it'll depend on the data. (Failing to exit early means we run n*n iterations even on sorted data; we might run only n comapres with fixing

Fixing the algorithm to use QuickSort will probably be the biggest win, cutting the running time to n*log.

But when analysing algorithms, we have to realize that these iteration and "order" estimates are multiplied by a constant. We really mean C*N*N, or C*N*Log(N). We can gain performance by reducing either the order or the coeficient.

strcmp() is only expensive if the strings involved are long and nearly equal. A good implementation of strcmp() on an x86 machine will compare four characters at a time. On the same architecture, calling involves pushing arguments, burning a register for the function's use and return values, and disrupts the execution pipline. Function calls, in the scheme of the application's execution, aren't cheap.

Perhaps the most expensive operation in the original implementation of the sort shown here is swapping; each swap will memcpy sizeof(struct) elements three times. Using pointers to the structures can realize a win, then.

Further, coming up with an implementation that doesn't use strucutres can help; packing the data structure in this way isn't friendly to the processor cache.

 

[Adak]

so, for school I have to write a program which uses a structure to store information on books like a library would have. My problem comes at the sorting part. I have to sort the books alphabetically by title, author, etc. I got it to work fine, but I have a sort function for each method, which the teacher isn't going to like. How can I compress it down to a single function (or two, one for ints (# of pages and rating of book) and one for strings (author names, titles, etc)?

Thanks guys.

I'm not sure how your instructor wants you to deal with this, but my answer is to NEVER sort/re-sort the Title, Author, etc. Leave them alone, in unsorted order.

You use an Index array, and you sort it, according to the order of the book's authors, title, etc. If you have to have just book title and author, then one or two separate int arrays for the indexing, may be fine. Any more than two, I'd make the index array an array of stucts:

Index.name, Index.title, Index.etc. I tend to use i.name, i.title, i.etc., for brevity.
The reason is not just for speed (although it helps a lot), but data integrity. Imagine you're constantly updating the book list with new books, lost books, damaged books, etc., If you're constantly re-reading and re-writing the data, any power loss or disk crash could ruin your data. And let's be honest - backups are almost NEVER up to date. So that's to be avoided, completely.

You're going to re-sort just the index. entries for each book lost, stolen, or purchased. A book that's lost, for instance, will have an index number which indicates that the record's fields can be over-written by new data, until then, it's in the database, but marked with the index number meanings "don't show me, don't count me, I'm a place holder only."

The sort of choice would be quicksort, but at some point, your data will exceed the memory of the computer. Mergesort, or a combination of Quicksort and Mergesort, will then be needed. For a homework assignment, either should suffice.

So to briefly illustrate:

Capote, "In Cold Blood", 1974 i.name == 1 , i.title == 1, i.date == 1
Shakespeare, "Hamlet", 1329 i. name == 2, i.title == 0, i.date == 0
Brown, "The Da Vinci Code", 2003 i.name == 0, i.title == 2, i.date == 2

I.name now lists the authors:

i.name [0] == array[2], or Brown,
i.name [1] == array[0], or Capote
i.name [2] == array[1] or Shakespeare

You compare and call up the array entries, through the proper index (i.name, i.title, i.date)
and you NEVER move the original data - you just re-sort the index(indicies), as needed, when books are bought or lost, etc. If you have a disk crash or power loss during a re-sort, you could laugh all day, because you haven't lost a thing - you just start re-sorting the index array, again. No original data has been touched.

If you have students in a stable school, or something, and there aren't a ton of them, then re-sorting the original data isn't so bad. Even if worst comes about and you have to re-enter all 500 students - well, it's a pain, but not anything to cry about.

With 750,000 books, however, constantly going out to borrowers and back in, new purchases weekly, and lost/damaged books as well, that's a whole different matter, and deserves a different approach to the program's design and implementation, imo.

Adak

 

[CodeX]

If you read the original post he is not talking about code efficiency, he simply wants to combine all of his sorting functions into one function.

Each of your sort functions takes the same parameters. All you would need to do to combine them is add one additional parameter indicating which sort type to use, then use a switch or if else structure to do the appropriate sort.

You guys are making this harder then it is, the question that he asked is simple to solve.

#define NAME 0
#define GENRE 1
#define AUTHOR 2
#define RATING 3
#define PAGES 4

void sort(int index, struct BOOKS[], int type)
{
  struct BOOKS temp;
  int x, y;

  for(x = 0; x < index; x++)
  {
    for(y = 0; y < index-1; y++)  
    {
      if((type==GENRE && strcmp(info[y].category, info[y+1].category) > 0) ||
         (type==NAME && strcmp(info[y].name, info[y+1].name) > 0) ||
         (type==AUTHOR && strcmp(info[y].author, info[y+1].author) ||
         (type==RATING && info[y].rating > info[y+1].rating) ||
         (type==PAGES && info[y].pages > info[y+1].pages))
      {
        temp = info[y];
        info[y] = info[y+1];
        info[y+1] = temp;
      }
    } //for y
  } //for x
} //sort

//Instead of this:
switch (choice)
{
...
}

//Do this:
sort(index, info, choice-1); 
//choice-1 because your original switch goes from 1-5, not 0-4

Simple (but untested, lol)

You actually don't even need the defines at the top if you implement it like above, I just think they make it more readable.

*edit* condensed...

 

[Adak]

If you read the original post he is not talking about code efficiency, he simply wants to combine all of his sorting functions into one function.

Each of your sort functions takes the same parameters. All you would need to do to combine them is add one additional parameter indicating which sort type to use, then use a switch or if else structure to do the appropriate sort.

You guys are making this harder then it is, the question that he asked is simple to solve.

Anyone who recommends a bubble sort for a library's book program, on the working data, instead of an index, clearly needs other guidance.

He's not just getting the answer to his question, because he's not asking the right question.

I don't think doing his program for him, showing a bubble sort (and a long bubble sort, at that), is quite as helpful as you seem to believe.

Strictly speaking, you're right as rain, and get an "A", but in RL, this idea flunks.

Adak

 

[CodeX]

As a student I feel that your approaches (while excellent, and certaintly deserving of an 'A' themselves) are a bit beyond the scope of the class. He is probably using a bubble sort because he is SUPPOSED to use a bubble sort, thats probably the entire point of this homework.

If you are helping a student, think like a student. If you were helping a professional your suggestion would be excellent.

Also, when I help someone, students especially, I like to keep as much of their original code in tact as possible. It's less overwhelming when they see their own code, just reorganized, then when they see a completely different approach to the problem.

 

[HHunt]

As a student I feel that your approaches (while excellent, and certaintly deserving of an 'A' themselves) are a bit beyond the scope of the class. He is probably using a bubble sort because he is SUPPOSED to use a bubble sort, thats probably the entire point of this homework.

If you are helping a student, think like a student. If you were helping a professional your suggestion would be excellent.

Also, when I help someone, students especially, I like to keep as much of their original code in tact as possible. It's less overwhelming when they see their own code, just reorganized, then when they see a completely different approach to the problem.

True, that. (I'm still a student, for what it's worth.)
However, solving the problem he has in a general way requires some somewhat advanced methods. Your monstrous if-clause does solve what he asked, but it's not exactly elegant. Function pointers or offsets can be implemented in a way that won't require changing the sorting method to add more fields, and in fewer lines. Thus he should consider it.

Function pointers are the neatest solution, not the least because moving the comparisation itself out to other functions makes it trivial to add sorting on non-string fields. (Like qsort.)
Offsets might be easier to understand (if you're familiar with pointers in C, at least) and a bit faster, but you're limited to using them on fields of the same type.

I deliberately wrote programs that are not direct solutions because he'll learn more from extracting the interesting parts from an example than from merely using my code.
(I did, however, try to do the things he would need to do. That's why I'm e.g. using an array of structs even though I'm only working with one element of it.)

Adak:
Using index arrays is a wonderful idea, and should be used in any serious solution, but it is probably a bit overkill for solving "sort these structs with a bubble sort" or whatever his task was. Then again, that goes for most other suggestions here as well, including mine.
Besides, he'd still need to sort, so the above discussion still applies.

 

[CodeX]

LOL, yeah, I am anything but elegant.

The sad thing is in the real world with such hectic time tables the emphasis is on "get it done" not "get it done well/elegant/effeciently". Consumers don't see your beautifully constructed algorithms, they see the end result. If the end result is the same either way and one way takes an hour less to implement, thats the way I would go for. Gotta meet those deadlines...

 

[HHunt]

LOL, yeah, I am anything but elegant.

The sad thing is in the real world with such hectic time tables the emphasis is on "get it done" not "get it done well/elegant/effeciently". Consumers don't see your beautifully constructed algorithms, they see the end result. If the end result is the same either way and one way takes an hour less to implement, thats the way I would go for. Gotta meet those deadlines...

On the other hand, a more elegant solution (e.g. function pointers) might make changing the code later on faster and less prone to adding bugs, which could be worth it.
Imagine adding another field, and having to change a whole lot of if clauses like that. Adding another getter-function or comparisation-function or sending another offset is easier.

(I like making black box-style code, where a function can be left alone when I get it working.)

 

[CodeX]

On the other hand, a more elegant solution (e.g. function pointers) might make changing the code later on faster and less prone to adding bugs, which could be worth it.
Imagine adding another field, and having to change a whole lot of if clauses like that. Adding another getter-function or comparisation-function or sending another offset is easier.

(I like making black box-style code, where a function can be left alone when I get it working.)

Of course it depends on where your priorities lie and what type of program you are working on...

 

[HHunt]

Of course it depends on where your priorities lie and what type of program you are working on...

True. Writing -everything- in a reusable, elegant, way would be a waste of time.

 

[mikeblas]

Simple (but untested, lol)

Not simple enough; you managed to get it wrong. Even if corrected, it's not so elegant or efficient. For every iteration, you're evaluating the if condition, even though the if is invariant throughout the operation.

Making indexes for sorts by the different fields is interesting, but there are situations where it's not appropriate. It requires a ton of memory, for example; and isn't going to appear to be so simple when the list itself becomes larger than memory. The indirection is cache-unfriendly, and might preclude use in some scan-intensive cases.

Presuming the student wishes to limit his learning only to the scope of the class seems a diservice.

 

[HHunt]

Regarding said student, I think we scared him away.

 

[mikeblas]

Regarding said student, I think we scared him away.

It's not uncommon in this form for someone to post a question and get a bunch of responses—from clarification questions to complete solutions—and never appear again; even just to say thank you.

 

[CodeX]

Not simple enough; you managed to get it wrong. Even if corrected, it's not so elegant or efficient. For every iteration, you're evaluating the if condition, even though the if is invariant throughout the operation

How is it invariant? The index of the info array(?) is being changed each iteration...
Not that I don't believe you, I have a lot of respect for you, I just don't see it. Mind showing me how you would do it?

 

[CodeX]

Presuming the student wishes to limit his learning only to the scope of the class seems a diservice.

Answering questions that were never asked seems presumptuous

 

[mikeblas]

Answering questions that were never asked seems presumptuous

Sure; I'm presuming a student wants to learn and is curious. It's encouraging and enriching. The questioner gets more insight and the responder gets to think through a problem and try to explain it, which is a valuable exercise. I think this is a safe bet.

I don't think it's good for either party to presume that a student doesn't want to learn, or only wants to learn an arbitrarily limited amount.

Point is: it feels funny to be faulted for trying to give as much information, insight, and help as possible.

How is it invariant? The index of the info array(?) is being changed each iteration...
Not that I don't believe you, I have a lot of respect for you, I just don't see it. Mind showing me how you would do it?

How I'd do it would depend on a lot of parameters that aren't specified here. Those unspecified parameters are part of the reason some of us are guessing at which solution might be the one desired.

type is invariant through all m*n iterations of the array. The code you have is testing type every single iteration. The compiler has enough information to hoist the tests out of the loop, and I haven't seen if the compiler I use will do so or not. But at such an optimization level, I'd rather code explicitly what I want.

That would mean either having different sort functions and calling them based on the desired key, or having different comparison functions and calling through a pointer to the function. If the record format was fixed (eg, this was really just a homework problem) I'd probably code the prior. If the record format was flexible (or I wanted to show off to the prof) I'd code the latter.

Calling through a function pointer isn't cheap at all, so I'd want a good reason to do it.

Thank you for your kind words.

 

[CodeX]

Right, the 'type' variable is, but the rest isn't. So you would suggest something like this over what I first posted:

void sort(int index, struct BOOKS[], int type)
{
  struct BOOKS temp;
  int x, y;

  if(type==GENRE)
  {
    for(x = 0; x < index; x++)
      for(y = 0; y < index-1; y++)  
        if(strcmp(info[y].category, info[y+1].category) > 0))
        {
          temp = info[y];
          info[y] = info[y+1];
          info[y+1] = temp;
        }
  }

  else if(type==NAME)
  {
    for(x = 0; x < index; x++)
      for(y = 0; y < index-1; y++)  
        if(strcmp(info[y].name, info[y+1].name) > 0))
        {
          temp = info[y];
          info[y] = info[y+1];
          info[y+1] = temp;
        }
  }

  //etc
}

This way the type variable isn't being checked over and over, but it looks like garbage in code. How much efficiency is really gained here?

 

[mikeblas]

So you would suggest something like this over what I first posted

Nope; that implements neither of my suggestions. My first suggestion was more like what Korialstrasza originally posted; getting the conditional completely out of the sort function. My second suggsetion was to use function pointers for the comparison routine.

But let's examine what you have, since it is an improvement over the ten-term if statement version.

This way the type variable isn't being checked over and over, but it looks
like garbage in code. How much efficiency is really gained here?

How interesting: I think the five-line if() statement looks like garbage, particularly at the inside of two nested loops.

You're doing up to five comparisons each iteration just on type. You're doing two branches per comparison; one conditional and one unconditional. In your fixed example, you're doing zero comparisons per iteration.

Branching is expensive. The expense is mitigated if the processor can predict the branches accurately, but it seems like as soon as you get things lined-up for good prediction on one processor, there's some other processor that predicts differently.

In the big conditional; it probably compiles to about 100 bytes of code; more if the compiler makes strcmp() intrinsic. strcmp() is an expense for the other versions so it comes out; we'll assume the compiler can fold the terms and only do it once, after the arguments to it are calculated. I'd expect 80% of that 100 estimate to be just branching and testing.

I'm not sure how you want me to answer your "how much" question. I asserted that it could be more efficiently rewritten, and I'm very sure that it is. But let me give it a whirl:

How much more efficient will depend on the compiler used and processor where it's running. The size of the workload matters a lot; since we're so foolishly doing N*M comparisons, this fix is going to be of exponential value. The answer will also vary depending on what key you're using, since one key is going to be checked against 'type' first, before other keys. Chosing the "lucky" key number will result in less branching.

Say you implement this fix and you get rid of 150 cycles; which is a reasonable straw man -- 100 bytes, 3 instructions per byte, 30 instructions at 5 cycles each.

With 750,000 books, you're executing 562,500,000,000 iterations of this loop. That's 84,375,000,000,000 cycles. That's 35,156.25 seconds on the 2.4 GHz machine I'm using to write this message. Just a few minutes less than ten hours!

Going the other way, keeping the 150 cycles estimate and the 2.4 GHz rig, you only need 4000 books before shaving those 150 cycles per iteration lets you save one second of run time.

So it's not as much as you'd save by picking a better algorithm. Maybe it's not as much as you'd save by swapping pointers instead of memcyping 3*160 == 480 bytes every time. But it is a savings, and it's one I would want to implement.

 

[Korialstrasza]

Regarding said student, I think we scared him away.

No... I'm here. Just trying to make sense of it all.

We just now were introduced to structures, so as much as I appreciate it, a lot of this is way over my head.

I really do appreciate all the help you guys are providing, and am at the moment trying to conjure up the "right" questions.

p.s. this is a high school CS class, so as much as the teacher would like super professional and efficient code, we're all noobs. He just doesn't want to see too much copy/pasting/renaming functions, and wants us to try to compact it all as much as possible.

 

[Adak]

No... I'm here. Just trying to make sense of it all.

We just now were introduced to structures, so as much as I appreciate it, a lot of this is way over my head.

I really do appreciate all the help you guys are providing, and am at the moment trying to conjure up the "right" questions.

p.s. this is a high school CS class, so as much as the teacher would like super professional and efficient code, we're all noobs. He just doesn't want to see too much copy/pasting/renaming functions, and wants us to try to compact it all as much as possible.

Thanks for putting the whole problem back into perspective. As you can tell, this is a VERY deep subject. You could spend an entire class just on database programming, and still not know everything you might want to know about it.

For a HS class of noobs, I'd certainly sort the raw data (which I'd never do in a RL program), and if you don't know a better sort - bubble sort is OK, too. If the instructor wanted you to use a good sort algo, he/she would have taught you one, imo.

Looking back through the posts, I'm unclear if you ever got the answer you were looking for. Did you find the answer to combining your searches, yet?

I believe several of us have "dove in over your head" with our replies. That's good sometimes, but I would like to direct us back to the OP's exact question, and stay at that level for a while.

What's the status of the program, now?

Adak

 

[mikeblas]

and wants us to try to compact it all as much as possible.

Why is that?

 

[HHunt]

Why is that?

It does hint at doing things generically (instead of writing an almost-identical special case for every possibility), and that's generally (sorry) a good thing.

 

[mikeblas]

It does hint at doing things generically (instead of writing an almost-identical special case for every possibility), and that's generally (sorry) a good thing.

Up until the point where it hurts performance--then you have to figure out if the tradeoff is worth it. So is our teacher teaching that? Or sticking to write less code and not encouraging (or allowing!) his students to think it through?

 

[CodeX]

Mike, my highschool CS teacher was a math teacher and didn't know a damn thing about programming, she was learning it as she went. Point is this is a highschool kid in a highschool class, if he decides to pursue programming he will have plenty of time to learn to do things the "right" way, but for now he just needs to get it done. That is why I chose to help him the way I did, which should be all the help he would need for this problem...

 

[mikeblas]

Point is this is a highschool kid in a highschool class, if he decides to pursue programming he will have plenty of time to learn to do things the "right" way, but for now he just needs to get it done.

You're scaring me.

 

[HHunt]

You're scaring me.

I've almost got to agree with you.
I do see the point of doing things the easy way when you're teaching stuff, because getting bogged down in details will keep the students from getting the neccesary overview. Details can be filled in later.
However, things should be done the right way from the start if it's not too impractical. Bad habits last a while.

As for how to combine those two, well, that's part of what makes a good teacher.

 

[CodeX]

You're scaring me.

It's an introductory class, he is learning the basic fundamentals of the language, there is only so much he can learn in a 15 week semester.... If you go into such depth with every topic you won't cover half of your supposed to