Last active
August 29, 2015 13:57
-
-
Save pablq/9677964 to your computer and use it in GitHub Desktop.
help me improve this function please! i don't know what's slowing it down soo much!
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// NOTE: I HAVE FOUND A SOLUTION! | |
// I SOLVED MY CHECK FUNCTION WOES IN THREE WAYS: | |
// FIRST, I EXPANDED THE SIZE OF MY HASH TABLE BY A LOT ... TSIZE WAS 600 ... NOW IT IS 65557 | |
// SECOND, I ADJUSTED MY HASH FUNCTION TO DISPERSE ITEMS MORE EVENLY ACROSS ALL INDEXES OF THE TABLE -- and here-in discovered | |
// the true problem with the code below ---> the hash function is almost completely useless. the while loop's exiting condition | |
// is met (i != '\0') right away because i is initialized to 0. what i meant it to do was run while input[i] != '\0'. however, | |
// that syntax in the condition didn't work, so i changed the function to accept the string length as another variable. | |
// THIRD, WITH THE HELP OF EBOBTRON I ELIMINATED CALLS OF ISUPPER() AND TOLOWER() WHILE MAINTAINING CASE-INSENSITIVITY. | |
// Finally, THANK YOU to ebobtron, escarre, and dermot for helping me solve this one! | |
// It has really been fun and difficult! It's always a dumb minor syntax error that holds ya up huh?! Boy i was puzzled for | |
// a while... | |
/**************************************************************************************************************************** | |
* Here is the code for the function check that is giving me so much trouble. i would greatly appreciate feedback that will | |
* help to me to improve the performance of this code! Also, i included some extra stuff below it that might be related. | |
*************************************************************************************************************************** | |
*/ | |
int hash(const char* input); // prototype for the hash function | |
bool check(const char* word) // and onto check... | |
{ | |
char temp[LENGTH +1]; // initialize a temporary char array to store our case-insensitive version of the word parameter | |
int j = strlen(word); | |
for(int i = 0; i <= j; i++) // for each char in word | |
{ | |
if(isupper(word[i])) // if the char is upper case copy the lowercase version into temp | |
{ | |
temp[i] = tolower(word[i]); | |
} | |
else // else copy the char into the buffer | |
{ | |
temp[i] = word[i]; | |
} | |
} | |
node* cursor = table[hash(temp)]; // set the cursor pointer to the appropriate index in the hash table | |
while(cursor != NULL) // and as long as there is something there to look at... | |
{ | |
if(strcmp(temp, cursor->entry)==0) // check if the word stored in that node is the same as the input to check | |
{ | |
return true; // if so return true | |
} | |
cursor = cursor->next; // but if it isn't, move on to the next node in the line and compare again | |
} | |
return false; // if no match is found return false | |
} | |
int hash(const char* input) // simple multiplication method hash function using the first 3 available chars in string input | |
{ | |
long total = 1; | |
int i = 0; | |
while(i < 3 && i != '\0') | |
{ | |
total *= input[i]; | |
i++; | |
} | |
return total % TSIZE; | |
} | |
//************************************************************************************************************************* | |
* Below are a few (fairly disjointed) aspects of the program that might be related to my problems with the performance of | |
* the check function. obviously things are out order here, but i figure it might be helpful to see the type definition i | |
* used for my nodes and the declaration of the hash table. i threw in my load function too for good measure | |
************************************************************************************************************************* | |
*/ | |
#define TSIZE 600 | |
typedef struct node { | |
char entry[LENGTH + 1]; | |
struct node* next; | |
} node; | |
node* table[TSIZE]; | |
//************************************************below is the load function************************************************ | |
int words_loaded = 0; | |
bool load(const char* dictionary) | |
{ | |
for(int i = 0; i < TSIZE; i++) // set all the pointers in the hash table to NULL to start off. | |
{ | |
table[i] = NULL; | |
} | |
FILE* dict = fopen(dictionary, "r"); // open the file | |
if(dict == NULL) | |
{ | |
printf("Could not open %s.\n", dictionary); | |
return false; | |
} | |
char buffer[LENGTH +1]; | |
while(fscanf(dict, "%s", buffer) > 0) // scan one word at a time into buffer. while fscanf returns > 0, | |
{ // create a new node and store the word in buffer into the node's | |
node* new_node = malloc(sizeof(node)); // entry variable. | |
new_node->next = NULL; | |
strcpy(new_node->entry, buffer); | |
int index = hash(new_node->entry); // hash the word we just stored in the node | |
if(table[index] == NULL) // and direct the pointer in the appropriate index of the hash table to it | |
{ // if there is already something referenced by that pointer, add the new | |
table[index] = new_node; // node to the front of the linked list. | |
} | |
else | |
{ | |
new_node->next = table[index]; | |
table[index] = new_node; | |
} | |
words_loaded++; // update the variable keeping track of the words loaded | |
} | |
fclose(dict); | |
return true; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment