optimizing loop (frequency counting)... HELP

okay. i am trying to make this loop run as quick as possible.

i am trying to collect all occurances of each ASCII character and put into table. i don't really care if ASCII char value equals it's position in the table.

Code:

for (;;) {
	c = fgetc(input_file);

	/* If symbol is already in table then increase frequency
	 * by one, otherwise put symbol into the table.
	 */
	for (i = 0; i < 256; i++) {
		if(c == i) {
			if (symbol[i].achar == c) {
				symbol[i].count++;
				break;
			}
			symbol[i].achar = c;
		}
	}

	nc++;

	if (feof(input_file))
		break;
}

Why it's bad to use feof() to control a loop

My suggestion:

Code:

char freq[256];
/* Initalize the array so everything is 0 */
int c;
for (;;)
{
  c = fgetc(input_file);
  if ( c == EOF )
    break;
  freq[c]++;
}

easist way IMO if you aren't worried about wasted space.

nope... no performance improvement from that. anything else? maybe hash tables, linked lists?

To get the most improvement you need to load as much of the file into memory as possible and then do it. Most of the loop's time is from reading the harddrive.

Example:

Code:

#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>

void init (int *, int);

int main (void)
{
  int size_read, fid, count;
  char buffer[1048576];
  int freq[256];


  init(freq, sizeof freq/sizeof freq[0]);

  fid=open("test.txt", O_RDONLY);
  if ( fid == -1 )
  {
    puts("Could not open file");
    return 1;
  }

  while ( (size_read = read(fid, buffer, sizeof buffer)) != 0 )
  {
    for(count=0; count<size_read; count++)
      freq[(int)buffer[count]]++;
  }

  for (count=0; count<sizeof freq/sizeof freq[0]; count++)
    printf("ASCII %3d:  %3d\n", count, freq[count]);
  return 0;
}

void init (int *x, int y)
{
  int count;
  for (count=0; count < y; count++)
    x[count] = 0;
}

okay... overnight i looked at the loop, and came up with this. running it with the old code on a 65MB file took 10 mintues (on a 233Mhz Cyrix).

now, on the same machine i get 1.5 minutes with this:

Code:

for (;;) {
	c = fgetc(input_file);

	if (feof(input_file))
		break;

	if (symbol[c].count > 0) {
		symbol[c].count++;
		continue;
	}
	symbol[c].count++;

	nc++;
}

haven't tried loading into fread(), but i think this is the best it's gunna get. but if anyone has any other suggestions... bring it on.

Well calling feof() every time is gonna hurt
Especially since fgetc also returns EOF

Code:

int c;
while ( (c = fgetc(input_file)) != EOF ) {
	if (symbol[c].count > 0) {
		symbol[c].count++;
		continue;
	}
	symbol[c].count++;

	nc++;
}

Using fread() with
char buff[BUFSIZ];
is likely to be a better bet

Slightly improved:

Code:

int c;
while ( (c = fgetc(input_file)) != EOF ) {
	if (symbol[c].count++ > 0) {
		continue;
	}
	nc++;
}

Seeing as you increment whatever the result of the test, might as well only access that variable once.

whoa! good stuff...

Skip the nc++ as well, since that's known by the file size (unless it's a text file with DOS newlines).

Other suggestions:
- use your OS's "raw" file I/O API
- read into a memory-page sized buffer at a time

gg

>>Skip the nc++ as well, since that's known by the file size (unless it's a text file with DOS newlines).<<
Based on the snippet last posted, nc looks like its counting the number of different characters in the file, not the total file size.

Allow me to continue my OS specific suggestions (in order to redeem myself)....

Under Windows and using the Win32 API, you could open the file with FILE_FLAG_NO_BUFFERING and FILE_FLAG_OVERLAPPED. Use a buffer size that is some multiple of the hard disk's sector size, but less than or equal to the systems memory page size. While the OS is working on a read operation, crunch the data of the previous read operation.

You can achieve similar results using asynchronous I/O under *nix (or a couple of threads, one to read and one to crunch).

gg

Using the method I posted on a 25 meg file it took about 6.5 seconds to read and print off the results.

i was omitting what "nc" was for...

[CODE}
while ( (c = fgetc(input_file)) != EOF ) {
symbol[i].position = symbol[i].position + nc; /* this is what the nc is for */
if (symbol[c].count++ > 0) {
continue;
}
nc++;
}
[/CODE]

oops.

Code:

while ( (c = fgetc(input_file)) != EOF ) {
	symbol[c].position = symbol[c].position + nc;
	if (symbol[c].count++ > 0) {
		continue;
	}
	nc++;
}

if just counting frequency... i got it down to just this!!!

Code:

while ((c = fgetc(input_file)) != EOF ) {
	symbol[c].count++;
}