Sharon Shelton Ответов: 2

Как я могу эффективно подсчитать частоту каждого слова в файле?


Я пишу код, чтобы найти вхождение каждого слова в файл. Я пришел к выводу, что хэш-таблицы-это лучший способ реализовать эту программу. Моя программа отлично работает для небольших файлов. Есть ли какой-нибудь способ сделать мой код лучше? Просто любопытно узнать :) Спасибо

Что я уже пробовал:

#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#define TABLE_SIZE 1000

struct node
{
	char word[1000];
	int count;
	struct node *next;
};

struct node hashtable[TABLE_SIZE];

int main()
{
	char newword[1000],path[100];
	int i;
	FILE *fptr;
	
	printf("Enter file path: ");
    scanf("%s",&path);
    fptr = fopen(path, "r");
    if (fptr == NULL)
    {
        printf("Unable to open file.\n");
        exit(0);
    }
    
    // init hashtable
    for (i = 0; i < TABLE_SIZE; i++) {
    	hashtable[i].word[0] = '\0';
    	hashtable[i].count = 0;
    	hashtable[i].next = NULL;
	}
    
    int wordCursor = 0, sum = 0, key, wordCnt = 0;
	while (1)
	{
		char ch = fgetc(fptr);
		int c=ch;
		//printf("%d",c);
	//	printf("%c",ch);
		if (ch ==EOF) // on file end break the loop
			break;

		// find the word boundary with other than
		if (isalpha(ch) || isdigit(ch)) {
			if (wordCursor < 1000-1) {
				newword[wordCursor++] = ch;
				sum=sum+c;
			}
			continue;
		} else newword[wordCursor] = '\0';	// null byte termination of word
		if (wordCursor == 0)
			continue;
		wordCursor=0;

		strlwr(newword);
	  //  printf("%s (%d)",newword, wordCnt);

		key=sum%TABLE_SIZE;
	  //  printf("%d\n",key);
	    sum = 0;

	    // is the hashtable location for key is free?
	    if (hashtable[key].count == 0) {
	    	hashtable[key].count++;
	    	strcpy(hashtable[key].word, newword);
	    	wordCnt++;
		} else {	// hash table already has some entry(ies)
			struct node *head = &hashtable[key];
			int isFound = 0;
			while(1) {	// traverse the list to locate the right node
				if(strcmp(head->word, newword) == 0) {
					head->count++;
					isFound = 1;
					break;
				}
				if (head->next == NULL) break;
				head = head->next;
			}
			if (isFound == 0) {	// insert a node at the end of the list
				head->next = (struct node *)malloc(sizeof(struct node));
				if (head->next == NULL) {
			        printf("Unable to allocate memory.\n");
    			    exit(0);
				}
				head->next->next = NULL;
				head->count = 1;
				strcpy(head->word, newword);
				wordCnt++;
			}
		}
	}
	
//	printf("No of Words:%d\n", wordCnt);
	for(i = 0; i < TABLE_SIZE; i++)
	{
		if (hashtable[i].count != 0) 
			printf("%s : %d\n",hashtable[i].word,hashtable[i].count);
	}
}

2 Ответов

Рейтинг:
2

KarstenK

Код выглядит хорошо, поэтому оптимизация существующего кода может только немного помочь, но вы можете изменить свое хранилище слов, как в двоичное дерево balamced что повышает скорость поиска.

Использование некоторого хэш-ключа строки в качестве критерия сортировки-это всегда лучшая идея.

Лучшая оптимизация-это делать меньше Мои советы-избегать операций поиска и сравнения строк.


Рейтинг:
0

Patrice T

Цитата:
Моя программа отлично работает для небольших файлов. Есть ли какой-нибудь способ сделать мой код лучше?

Если вы не хотите волшебных ответов, первое, что нужно сделать, это понять, как программа тратит время и почему.
Инструмент выбора-это профилировщик.
Профилирование (компьютерное программирование) - Википедия[^]
Как только вы увидите, какая часть кода потребляет время, вы можете использовать отладчик чтобы посмотреть как.

Кстати, сколько слов арии до 1000 символов ? или 500 ? или 100 ? или даже 50 символов?
слова размером 1000-это только пустая трата ресурсов.