Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #161968 > unrolled thread
| Started by | dfs <nospam@dfs.com> |
|---|---|
| First post | 2021-07-19 12:50 -0400 |
| Last post | 2021-07-21 23:23 -0400 |
| Articles | 4 on this page of 24 — 11 participants |
Back to article view | Back to comp.lang.c
Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-19 12:50 -0400
Re: Allocate length of word vs fixed length Bart <bc@freeuk.com> - 2021-07-19 19:01 +0100
Re: Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-19 14:29 -0400
Re: Allocate length of word vs fixed length Bart <bc@freeuk.com> - 2021-07-19 19:49 +0100
Re: Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-19 18:01 -0400
Re: Allocate length of word vs fixed length Bart <bc@freeuk.com> - 2021-07-19 23:25 +0100
Re: Allocate length of word vs fixed length scott@slp53.sl.home (Scott Lurndal) - 2021-07-19 20:00 +0000
Re: Allocate length of word vs fixed length Branimir Maksimovic <branimir.maksimovic@gmail.com> - 2021-07-19 23:29 +0000
Re: Allocate length of word vs fixed length Real Troll <real.troll@trolls.com> - 2021-07-20 00:30 +0100
Re: Allocate length of word vs fixed length DFS <nospam@dfs.com> - 2021-07-19 20:40 -0400
Re: Allocate length of word vs fixed length Real Troll <real.troll@trolls.com> - 2021-07-20 17:00 +0000
Re: Allocate length of word vs fixed length Kaz Kylheku <563-365-8930@kylheku.com> - 2021-07-24 01:07 +0000
Re: Allocate length of word vs fixed length David Brown <david.brown@hesbynett.no> - 2021-07-19 21:35 +0200
Re: Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-19 18:02 -0400
Re: Allocate length of word vs fixed length Ike Naar <ike@rie.sdf.org> - 2021-07-19 21:11 +0000
Re: Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-19 18:03 -0400
Re: Allocate length of word vs fixed length Ike Naar <ike@sdf.org> - 2021-07-20 05:28 +0000
Re: Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-19 18:21 -0400
Re: Allocate length of word vs fixed length Bart <bc@freeuk.com> - 2021-07-19 23:29 +0100
Re: Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-19 18:40 -0400
Re: Allocate length of word vs fixed length Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> - 2021-07-20 11:44 +1000
Re: Allocate length of word vs fixed length Real Troll <real.troll@trolls.com> - 2021-07-20 22:15 +0000
Re: Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-20 20:22 -0400
Re: Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-21 23:23 -0400
Page 2 of 2 — ← Prev page 1 [2]
| From | Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> |
|---|---|
| Date | 2021-07-20 11:44 +1000 |
| Message-ID | <pcmhsh-pp1.ln1@aretha.foo> |
| In reply to | #161968 |
Groovy hepcat dfs was jivin' in comp.lang.c on Tue, 20 Jul 2021 02:50
am. It's a cool scene! Dig it.
> Loaded a list of words into an array.
>
> The 370103 words came from https://github.com/dwyl/english-words
> file = words_alpha.txt
>
> Tested a couple memory allocation 'strategies' during loading:
>
> 1. allocate the strlen() of each word
> 2. allocate a fixed length (len of longest word = 32)
>
> I figured getting strlen(word) each time would be slower than
> allocating a fixed amt of memory, but that wasn't the case.
>
> Strategy 2 is significantly slower, and uses nearly 3x the memory.
>
> Also, does anyone have any 'tricks' to make such a file load routine
> faster/more efficient? Thanks
That all depends on what you're actually trying to do. Reading in an
array of words is a means to some end, not an end in itself. What do
you want to do with these words?
> ===========================================================
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> #include <ctype.h>
>
> #define maxlen 32
If the longest word is 32 letters, then maxlen should be 33 to allow
for the string's terminating null character. (Ike advised you about
allowing for this null in his response to you, but you didn't seem to
understand. See below.) The way you're reading in words, your 32 letter
word will be truncated to 31 letters, and the 32nd letter will wind up
being the next word.
> //removes trailing isspaces and quote marks
> char *rtrim(char *str)
> {
> int len = strlen(str);
> while(len>0 && (isspace(str[len-1]) || str[len-1] == '\"')) {len--;}
> str[len] = '\0';
> return str;
> }
Why is this (above) function needed? Does your file contain white
space (other than newlines) and quotes? What about such characters at
the start of a word?
This could probably be done by some kind of script before feeding the
file to your program.
> int main(int argc, char *argv[])
> {
> //vars
A point on style: it's a bad idea to use pointless comments like this.
Comments should explain the working and reasoning for code that's not
immediately obvious. Comments that don't do that just clutter the code
and can, in many cases, make it harder to comprehend.
> int i = 0, lines = 0;
Another word or two on style here: I'd make i and lines type size_t.
The point of size_t is to represent sizes (lines, in this case), so it
is good to use it for that. And the counter (i) is used to access
elements over the length of the array, so to my mind it makes sense to
use the same type for that (though no doubt others may disagree).
Also, you aren't using i until way below here. It might be better to
declare (or at least "initialise") it just before using it.
> char word[maxlen] = "";
> char wordin[maxlen] = "";
Initialising these is pointless, since you're only overwriting them
anyhow.
> //open file, count lines
> FILE *fwords = fopen(argv[1],"r");
> while(fgets(wordin,sizeof wordin,fwords)!=NULL) {lines++;}
>
> //Geany adds a line feed to the very last line, so the true
> //line count is overstated
Now that's a better comment. :)
> lines -= 1;
>
> //mem
> char **words = malloc(sizeof(char*) * lines);
Another style point: it is bad style to hard wire the type in a
malloc() call. This can lead to problems in case the type of the thing
being allocated changes. It is better to use something like the
following:
type *ptr = malloc(sizeof *ptr * num);
That way the size is always right for the thing being allocated. I know
Ike touched on this too, but it bears repeating.
Also, always check the return from functions that can fail, like
malloc(). This is vital. Never leave out this important step.
> //add words to array
> int memoption = atoi(argv[2]);
Always check that you have enough command line args when attempting to
use them. Again, this is vital. It's arguably more important than
checking that malloc() succeeded, because command line args usually
come from a human user; and you know how unpredictable those creatures
can be!
Also, what about argv[1]? You're not going to use that too?
> int memlen = 0, memtotal = 0;
> rewind(fwords);
Again, check that this succeeded. Use ferror() for this.
> while(fgets(wordin,sizeof wordin,fwords)!=NULL)
> {
> strcpy(word,rtrim(wordin));
>
> //different memory allocations
> if(memoption==1)
> {memlen=strlen(word);}
Now, about what I alluded to above (and Ike told you about), this is a
classic "off by one" error. To store a 5 letter word (for example) as a
string, you need 6 bytes. strlen() will return 5, meaning you need to
add 1 here. Remember, strlen() returns the length of the string *not*
including the terminating null character. You need to add 1.
> else
> {memlen=maxlen;}
>
> words[i] = malloc(sizeof(char*) * memlen);
I think Ike also mentioned the problem here. Remember as a general
rule, allocate the size of the thing being allocated, not a hard wired
type. But when you're just getting space for a string, it's okay to
just leave out the type altogether. You just want to allocate enough
bytes for the string (memlen bytes, in this case).
words[i] = malloc(memlen);
And, again, check that it succeeded.
> memtotal += memlen;
>
> strcpy(words[i],word);
>
> //printf("%d. '%s' ",i,words[i]);
> i++;
> }
>
> fclose(fwords);
> printf("\nloaded %d words\n",i-1);
> printf("\nFirst and Last words = '%s', '%s'\n",words[0],words[i-1]);
> printf("malloc option %d, total memory %d\n",memoption,memtotal);
> free(words);
Here you're freeing the overall array, but you're not freeing all the
smaller arrays (strings).
> return(0);
You don't need the parentheses around the return value here; return is
not a function.
> }
--
----- Dig the NEW and IMPROVED news sig!! -----
-------------- Shaggy was here! ---------------
Ain't I'm a dawg!!
[toc] | [prev] | [next] | [standalone]
| From | Real Troll <real.troll@trolls.com> |
|---|---|
| Date | 2021-07-20 22:15 +0000 |
| Message-ID | <sd7ie7$3mj$1@gioia.aioe.org> |
| In reply to | #161968 |
> A lot depends on what you then want to do with those words.
>
As pointed by Stefan and others, If all you need to do is to find the
largest length of the words then a simple program such as this one will
also work.
<========================================================================================================>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
FILE *gitFile;
char line[32];
int max_len = 0;
int counter = 0;
if ((gitFile = fopen("words_alpha.txt", "r")) == NULL)
{
perror("Error: No such file or directory\n");
EXIT_FAILURE;
}
else
{
while (!feof(gitFile))
{
fscanf(gitFile, "%s", &line);
if (strlen(line) > max_len)
{
max_len = strlen(line);
}
counter += 1;
}
}
printf("Largest word size is: %zu\n", max_len);
printf("There are %d lines in the file \n", counter);
return EXIT_SUCCESS;
}
<========================================================================================================>
In such a situation speed of loading a file is not important because you
are trying to read each line one at a time.
I agree this is too simplistic but we don't know what exactly is the
purpose of the program.
[toc] | [prev] | [next] | [standalone]
| From | dfs <nospam@dfs.com> |
|---|---|
| Date | 2021-07-20 20:22 -0400 |
| Message-ID | <qNJJI.18502$0N5.3707@fx06.iad> |
| In reply to | #162003 |
On 7/20/21 6:15 PM, Real Troll wrote:
>
>> A lot depends on what you then want to do with those words.
>>
> As pointed by Stefan and others, If all you need to do is to find the
> largest length of the words then a simple program such as this one will
> also work.
I found the max word length of 31 before I posted, but I took the code out
----------------------------------------------------------
int wordlen = 0, maxwlen = 0;
while(fgets(wordin,sizeof wordin,fwords)!=NULL)
{
wordlen = strlen(rtrim(wordin));
if(wordlen > maxwlen) {maxwlen = wordlen;printf("%d ",maxwlen);}
lines++;
}
printf("Max word len = %d\n",maxwlen);
----------------------------------------------------------
> <========================================================================================================>
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
>
> int main()
> {
> FILE *gitFile;
> char line[32];
> int max_len = 0;
> int counter = 0;
>
> if ((gitFile = fopen("words_alpha.txt", "r")) == NULL)
> {
> perror("Error: No such file or directory\n");
> EXIT_FAILURE;
> }
> else
> {
> while (!feof(gitFile))
> {
> fscanf(gitFile, "%s", &line);
> if (strlen(line) > max_len)
> {
> max_len = strlen(line);
> }
> counter += 1;
> }
> }
> printf("Largest word size is: %zu\n", max_len);
> printf("There are %d lines in the file \n", counter);
>
> return EXIT_SUCCESS;
> }
>
> <========================================================================================================>
>
> In such a situation speed of loading a file is not important because you
> are trying to read each line one at a time.
>
> I agree this is too simplistic but we don't know what exactly is the
> purpose of the program.
A simple linear search of the array to do word search/count/filter when
you enter letter(s).
It's partly working.
Enter a value: z
Found 1386 matches in 0.004709 seconds
Enter a value : x
Found 507 matches in 0.009121 seconds
I say partly because for now it just matches on the first letter you
enter.
Enter a value: cat
That will return all words beginning with c, not just words beginning
with cat.
There are a boatload of string search algorithms, but 'brute force' is
good for now
//http://www-igm.univ-mlv.fr/~lecroq/string/index.html
I saw your other post on timing. I run an 11-year-old CPU
(i5-750@2.67GHz) that's nothing special, but all my C code just screams
here on Linux. Usually compiled with the standard:
gcc -Wall source -o executable
My timing is done like this:
----------------------------------------------------------------------
struct timespec start,stop;
double elapsedtime(struct timespec started)
{
const double B = 1e9;
clock_gettime(CLOCK_MONOTONIC_RAW,&stop);
return (stop.tv_sec-started.tv_sec)+
(stop.tv_nsec-started.tv_nsec)/B;
}
inside main()
clock_gettime(CLOCK_MONOTONIC_RAW, &start);
... code to search word array
printf ("\nFound %d matches in %f secs\n",matches,elapsedtime(start));
----------------------------------------------------------------------
I put in a sleep(3) in to test it:
Enter a value : z
Found 1386 matches in 3.006703 seconds
Put your CLOCKS_PER_SEC timing in my code and got:
Enter a value : a
Found 25416 matches in 0.005890 seconds
[toc] | [prev] | [next] | [standalone]
| From | dfs <nospam@dfs.com> |
|---|---|
| Date | 2021-07-21 23:23 -0400 |
| Message-ID | <Iw5KI.24867$bR5.9748@fx44.iad> |
| In reply to | #162004 |
On 7/20/21 8:22 PM, dfs wrote:
> On 7/20/21 6:15 PM, Real Troll wrote:
>> I agree this is too simplistic but we don't know what exactly is the
>> purpose of the program.
>
> A simple linear search of the array to do word search/count/filter when
> you enter letter(s).
That's what it started out as, but HGH took over and it bloated to the
below 450 lines.
Give it a try, please, and see if you can break it. There are a few
TODOs in there, so it's not quite done.
Use whatever word list text file you want. Most of my testing was done
with words_alpha.txt from https://github.com/dwyl/english-words
----------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <ctype.h> //used with tolower(val)
#include <sys/ioctl.h> //used with finding terminal width
#include <sys/resource.h> //used with finding terminal width
#include <unistd.h> //used with finding terminal width
#define maxlen 32
//removes trailing isspaces and quote marks
char *rtrim(char *str)
{
int len = strlen(str);
while(len>0 && (isspace(str[len-1]) || str[len-1] == '\"')) {len--;}
str[len] = '\0';
return str;
}
//timing
struct timespec start,stop;
double elapsedtime(struct timespec started)
{
const double B = 1e9;
clock_gettime(CLOCK_MONOTONIC_RAW,&stop);
return (stop.tv_sec-started.tv_sec)+
(stop.tv_nsec-started.tv_nsec)/B;
}
//width of screen - gets checked/set each time summary is run
int tcols = 50;
//set value of screen width in characters
void settcols()
{
struct winsize w = {0};
ioctl(STDOUT_FILENO, TIOCGWINSZ, &w);
tcols = w.ws_col;
}
//string compare function for qsort
int comparechar(const void *a, const void *b) {
return strcmp(*(char **) a, *(char **) b);
}
//print a separator line on screen
void printline(int linewidth, char *linechar)
{
for(int i=0;i<linewidth;i++) { printf(linechar); }
printf("\n");
}
void countdupes(char *words[],int linecnt)
{
//each time word matches prev word increase dupe cnt
int dupecnt = 0;
for(int i=0;i<linecnt-1;i++)
{
for (int j=i+1;j<linecnt;j++)
{
if (strcmp(words[j],words[i])==0)
{ dupecnt++;
//printf("%d. %s-%s (%d)\n",i, words[i],words[j], dupecnt);
}
else
{i=j-1;break;}
}
}
printf("%d dupes\n",dupecnt);
}
char *getmode(char *words[])
{
return "three words appear 4 times";
}
void printsummary(int linecnt, char *words[], int maxwlen, int
countarr[], char *infile)
{
settcols(); //set # of columns visible onscreen
printf("\n");
printline(tcols*.8,"=");
printf("Summary of %s\n",infile);
printline(tcols*.8,"=");
printf("%d words\n",linecnt);
countdupes(words,linecnt);
printf("\nFirst word is '%s'\n",words[0]);
printf("Last word is '%s'\n",words[linecnt-1]);
printf("Longest word is %d letters\n\n",maxwlen);
printf("Mean = \n");
printf("Median = %s\n",words[(int)linecnt/2]);
printf("Mode = %s\n\n",getmode(words));
//output data by rows and columns
int a=0,rows=5,cols=6;
//count words by length
int matches = 0;
int cnts[31]={0};
for(int i=1;i<=maxwlen;i++)
{
for(int j=0;j<linecnt;j++)
{
if(strlen(words[j]) == i) {matches++;}
}
//printf("%d. %d\n",i,matches);
cnts[i-1] = matches;
matches = 0;
}
printf("Word counts by length\n");
a=0;
for(int r=0;r<=rows;r++)
{
for (int c=0;c<=cols;c++)
{
if(a<maxwlen) {printf("%2d. %5d ",a+1,cnts[a]);}
a++;
}
printf("\n");
}
//count words by first letter
printf("\nWord counts by first letter\n");
a=0;
for(int r=0;r<=rows;r++)
{
for (int c=0;c<=cols;c++)
{
if(a<26) {printf("%c. %5d ",a+97,countarr[a]);}
a++;
}
printf("\n");
}
//count frequency of letters across all words
int freq[26]={0};
for(int i=0;i<linecnt;i++)
{
for(int j=0;j<strlen(words[i]);j++)
{
freq[words[i][j]-'a']++;
}
}
//copy array for use with descending frequency output
int freq2[26]={0};
memcpy(freq2,freq,sizeof(freq2));
//sort counts descending
int n=26;
for (int i = 0; i < n; ++i)
{ for (int j = i + 1; j < n; ++j)
{ if (freq[i] < freq[j])
{ a = freq[i];
freq[i] = freq[j];
freq[j] = a;
}
}
}
//output letter frequency in descending order
//TODO: if multiple letters have the same frequency the code prints
// the 1st letter over and over. Need to resolve ties and print
letters in order
printf("Descending frequency counts\n");
a=0;
for(int r=0;r<=rows;r++)
{ for (int c=0;c<=cols;c++)
{ if(a<26)
{ for(int s=0;s<sizeof(freq2);s++)
{ if(freq2[s]==freq[a])
{ {printf("%c. %6d ",s+97,freq[a]);}
break;
}
}
}
a++;
}
printf("\n");
}
printline(tcols*.8,"=");
}
int main(int argc, char *argv[])
{
//vars
char word[maxlen] = "";
char wordin[maxlen] = "";
int countarr[26]={0};
static char *offon[]= {"off","on"};
char fcmd[37];
//open file, count lines, get max word length
char filein[50];
strcpy(filein,argv[1]);
FILE *fwords = fopen(filein,"r");
int lines=0, blanks=0, wordlen=0, maxwlen=0;
while(fgets(wordin,sizeof wordin,fwords)!=NULL)
{
wordlen = strlen(rtrim(wordin));
if (wordlen>0) {
if(wordlen > maxwlen) {maxwlen = wordlen;}
lines++;
}
else
{blanks++;}
}
//printf("%d lines, including %d blanks\n",lines+blanks,blanks);
//mem
char **words = malloc(sizeof(char*) * lines);
if(words == NULL) {printf("malloc failed\n");exit(0);}
// load word list into array
rewind(fwords);
int i=0;
clock_gettime(CLOCK_MONOTONIC_RAW, &start);
while(fgets(wordin,sizeof wordin,fwords)!=NULL)
{
strcpy(word,rtrim(wordin));
if(strlen(word)>0) {
words[i] = malloc(sizeof(char*) * (strlen(word) +1));
strcpy(words[i],word);
countarr[word[0]-'a']++;
i++;
}
}
printf ("\nLoaded %d words in %.3f seconds\n\n",i,elapsedtime(start));
//close file
fclose(fwords);
//sort the array
qsort(words, lines, sizeof(char*), comparechar);
//program options:
int prt=0,lsch=0,sub=0,wsz=0,dic=0,timing=0;
char opt;
menu:
printf("\nMenu \n\n");
printf(" -l search by start of word\n");
printf(" -b search by substring\n");
printf(" -n find words of length L\n");
printf(" -s summary of word list\n");
printf(" -d definitions\n");
printf(" -p print results to screen (%s)\n",offon[prt]);
printf(" -m print this menu\n");
printf(" -t show search times (%s)\n",offon[timing]);
printf(" -x exit program\n");
//capture keyboard input
char str[32];
while (strcmp(str,"-x")!=0)
{
//startup
search:
if(lsch==0&&sub==0&&wsz==0&&dic==0)
{printf("\nEnter -option to start: ");}
if(lsch) {printf("\nEnter letters to search for: ");}
if(sub) {printf("\nEnter substring to search for: ");}
if(wsz) {printf("\nEnter size of word to search for: ");}
if(dic) {printf("\nEnter word to find definition: ");}
scanf("%s", str);
//printf("'%s'",str);
if(str[0]=='-')
{
opt = tolower(str[1]);
if(opt=='x') {exit(0);}
//search for letters at beginning
if(opt=='l')
{if(lsch==0) {lsch=1;sub=0;wsz=0;dic=0;}}
//search for substring anywhere cerin word
if(opt=='b')
{if(sub==0) {sub=1;lsch=0;wsz=0;dic=0;}}
//search for words of a size
if(opt=='n')
{
if(wsz==0) {wsz=1;lsch=0;sub=0;dic=0;}
printf("\nlook for words of size 1 to %d",maxwlen);
}
//print summary of imported words
if(opt=='s')
{
printsummary(lines, words, maxwlen, countarr, filein);
}
//use dict search
if(opt=='d')
{if(dic==0) {dic=1;lsch=0;sub=0;wsz=0;}}
//show menu
if(opt=='m') {goto menu;break;}
//print word search results to screen
if(opt=='p')
{
prt = (prt==0) ? 1 : 0;
printf("\nprint is %s",offon[prt]);
}
//show timing measures
if(opt=='t')
{
timing = (timing==0) ? 1 : 0;
printf("\ntiming is %s",offon[timing]);
}
goto search;
}
//validation
if(wsz)
{
int s = atoi(&str[0]);
if(s > maxwlen) {printf("Max = %d\n",maxwlen);goto search;}
}
//find word in dict
//TODO: handle errors
if(dic) {
memset(fcmd,'\0',sizeof(fcmd));
sprintf(fcmd,"dict %s",str);
//sprintf(fcmd,"%s","clear");
system(fcmd);
goto search;
}
if(timing) {clock_gettime(CLOCK_MONOTONIC_RAW, &start);}
//main word search routines
//TODO: maybe print results in columns based on terminal width
int matches = 0;
size_t slen = strlen(str); //length of string being sought
if(slen>maxlen-1) {
printf("Enter max of %d letters\n",maxwlen);
goto search;
}
char ss[maxlen]; //to hold first n characters of word
//match beginning letters of word
if(lsch)
{
for(i=0;i<lines;i++)
{
memcpy(ss, words[i], slen);
ss[slen] = '\0';
if(strcmp(ss,str)==0)
{
if(prt) {printf("%s ",words[i]);}
matches++;
}
}
}
//match substring anywhere in word
if(sub)
{
for(i=0;i<lines;i++)
{
strcpy(word,words[i]);
if(strstr(word,str) != NULL)
{
if(prt) {printf("%s ",words[i]);}
matches++;
}
}
}
//match size of word
if(wsz)
{
for(i=0;i<lines;i++)
{
if(strlen(words[i]) == atoi(&str[0]))
{
if(prt) {printf("%s ",words[i]);}
matches++;
}
}
}
if(timing)
{printf ("\nFound %d matches for %s in %.4f
seconds\n",matches,str,elapsedtime(start));}
else
{printf ("\nFound %d matches for %s\n",matches,str);}
} //end while
free(words);
return 0;
}
---------------------------------------------------------------------------------
[toc] | [prev] | [standalone]
Page 2 of 2 — ← Prev page 1 [2]
Back to top | Article view | comp.lang.c
csiph-web