Skip to content

Instantly share code, notes, and snippets.

@pablq
Last active August 29, 2015 13:57
Show Gist options
  • Save pablq/9677964 to your computer and use it in GitHub Desktop.
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!
// 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